Join Indices.

@article{DBLP:journals/tods/Valduriez87,
  author    = {Patrick Valduriez},
  title     = {Join Indices},
  journal   = {ACM Trans. Database Syst.},
  volume    = {12},
  number    = {2},
  year      = {1987},
  pages     = {218-246},
  ee        = {http://doi.acm.org/10.1145/22952.22955, db/journals/tods/Valduriez87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1987 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[2]

Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983) BibTeX

[3]

Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX

[4]

Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX

[5]

Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX

[6]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[7]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[8]

George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279 BibTeX

[9]

S. Misbah Deen: An Implementation of Impure Surrogates. VLDB 1982: 245-256 BibTeX

[10]

David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX

[11]

Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 BibTeX

[12]

John V. Guttag: Abstract Data Type and the Development of Data Structures. Commun. ACM 20(6): 396-404(1977) BibTeX

[13]

Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) BibTeX

[14]

...

[15]

Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264 BibTeX

[16]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[17]

Michele Missikoff: A Domain Based Internal Schema for Relational Database Machines. SIGMOD Conference 1982: 215-224 BibTeX

[18]

Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982) BibTeX

[19]

Eric Simon, Patrick Valduriez: Design and Implementation of an Extendible Integrity Subsystem. SIGMOD Conference 1984: 9-17 BibTeX

[20]

Dennis Tsichritzis: LSL: A Link and Selector Language. SIGMOD Conference 1976: 123-133 BibTeX

[21]

Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) BibTeX

[22]

Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX

[23]

Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110 BibTeX

[24]

S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX

Referenced by

1. Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
2. Christophe Bobineau, Luc Bouganim, Philippe Pucheral, Patrick Valduriez: PicoDMBS: Scaling Down Database Techniques for the Smartcard. VLDB 2000: 11-20
3. Lucian Popa, Alin Deutsch, Arnaud Sahuguet, Val Tannen: A Chase Too Far? SIGMOD Conference 2000: 273-284
4. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter: A Unified Approach for Indexed and Non-Indexed Spatial Joins. EDBT 2000: 413-429
5. Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999)
6. Peter A. Boncz, Martin L. Kersten: MIL Primitives for Querying a Fragmented World. VLDB J. 8(2): 101-119(1999)
7. H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava: What can Hierarchies do for Data Warehouses? VLDB 1999: 530-541
8. Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999: 459-470
9. Peter A. Boncz, Stefan Manegold, Martin L. Kersten: Database Architecture Optimized for the New Bottleneck: Memory Access. VLDB 1999: 54-65
10. Ho-Hyun Park, Chan-Gun Lee, Yong-Ju Lee, Chin-Wan Chung: Early Separation of Filter and Refinement Steps in Spatial Query Optimization. DASFAA 1999: 161-168
11. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
12. Ming-Ling Lo, Chinya V. Ravishankar: The Design and Implementation of Seeded Trees: An Efficient Method for Spatial Joins. IEEE Trans. Knowl. Data Eng. 10(1): 136-152(1998)
13. Wang-Chien Lee, Dik Lun Lee: Dictionary: A New Access Method for Query Processing in Object-Oriented Databases. IEEE Trans. Knowl. Data Eng. 10(3): 371-388(1998)
14. Nick Roussopoulos: Materialized Views and Data Warehouses. SIGMOD Record 27(1): 21-26(1998)
15. Sven Helmer, Till Westmann, Guido Moerkotte: Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships. VLDB 1998: 98-109
16. Reinhard Braumandl, Jens Claußen, Alfons Kemper: Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases. VLDB 1998: 110-122
17. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581
18. Oliver Günther, Vincent Oria, Philippe Picouet, Jean-Marc Saglio, Michel Scholl: Benchmarking Spatial Joins À La Carte. SSDBM 1998: 32-41
19. Yannis Kotidis, Nick Roussopoulos: An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees. SIGMOD Conference 1998: 249-258
20. Ming-Chuan Wu, Alejandro P. Buchmann: Encoded Bitmap Indexing for Data Warehouses. ICDE 1998: 220-230
21. Giansalvatore Mecca, Alberto O. Mendelzon, Paolo Merialdo: Efficient Queries over Web Views. EDBT 1998: 72-86
22. Laura M. Haas, Michael J. Carey, Miron Livny, Amit Shukla: Seeking the Truth About ad hoc Join Costs. VLDB J. 6(3): 241-256(1997)
23. Chee Yong Chan, Beng Chin Ooi: Efficient Scheduling of Page Access in Index-Based Join Processing. IEEE Trans. Knowl. Data Eng. 9(6): 1005-1011(1997)
24. Lars Bækgaard, Leo Mark: Incremental Computation of Set Difference Views. IEEE Trans. Knowl. Data Eng. 9(2): 251-261(1997)
25. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
26. Nick Koudas, Kenneth C. Sevcik: Size Separation Spatial Join. SIGMOD Conference 1997: 324-335
27. Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB J. 5(2): 101-118(1996)
28. John Mylopoulos, Vinay K. Chaudhri, Dimitris Plexousakis, Adel Shrufi, Thodoros Topaloglou: Building Knowledge Base Management Systems. VLDB J. 5(4): 238-263(1996)
29. Theo Härder, Joachim Reinert: Access Path Support for Referential Integrity in SQL2. VLDB J. 5(3): 196-214(1996)
30. Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270
31. Boris Shidlovsky, Elisa Bertino: A Graph-Theoretic Approach to Indexing in Object-Oriented Databases. ICDE 1996: 230-237
32. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
33. Arun K. Thakore, Stanley Y. W. Su, Herman Lam: Algorithms for Asynchronous Parallel Processing of Object-Oriented Databases. IEEE Trans. Knowl. Data Eng. 7(3): 487-504(1995)
34. Arie Segev, J. Leon Zhao: A Framework for Join Pattern Indexing in Intelligent Database Systems. IEEE Trans. Knowl. Data Eng. 7(6): 941-947(1995)
35. Chiang Lee, Zue-An Chang: Utilizing Page-Level Join Index for Optimization in Parallel Join Execution. IEEE Trans. Knowl. Data Eng. 7(6): 900-914(1995)
36. Elisa Bertino, Paola Foscoli: Index Organizations for Object-Oriented Database Systems. IEEE Trans. Knowl. Data Eng. 7(2): 193-209(1995)
37. Tor Didriksen, César A. Galindo-Legaria, Eirik Dahle: Database De-Centralization - A Practical Approach. VLDB 1995: 654-665
38. Adel Shrufi, Thodoros Topaloglou: Query Processing for Knowledge Bases Using Join Indices. CIKM 1995: 158-166
39. Elisa Bertino, S. Salerno, Boris Shidlovsky: Enhanced Nested-Inherited Index for OODBMS. CIKM 1995: 58-65
40. Byung Suk Lee, Gio Wiederhold: Efficiently Instantiating View-Objects From Remote Relational Databases. VLDB J. 3(3): 289-323(1994)
41. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
42. Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)
43. Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533
44. Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378
45. Ambuj Shatdal, Chander Kant, Jeffrey F. Naughton: Cache Conscious Algorithms for Relational Query Processing. VLDB 1994: 510-521
46. Christoph Kilger, Guido Moerkotte: Indexing Multiple Sets. VLDB 1994: 180-191
47. Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220
48. Sunil Choenni, Elisa Bertino, Henk M. Blanken, Thiel Chang: On the Selection of Optimal Index Configuration in OO Databases. ICDE 1994: 526-537
49. Chung-Min Chen, Nick Roussopoulos: The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994: 323-336
50. Nick Roussopoulos, Nikos Economou, Antony Stamenas: ADMS: A Testbed for Incremental Access Methods. IEEE Trans. Knowl. Data Eng. 5(5): 762-774(1993)
51. Gultekin Özsoyoglu, Aladdin Hafez: Near-Optimum Storage Models for Nested Relations Based on Workload Information. IEEE Trans. Knowl. Data Eng. 5(6): 1018-1038(1993)
52. Marguerite C. Murphy, Doron Rotem: Multiprocessor Join Scheduling. IEEE Trans. Knowl. Data Eng. 5(2): 322-338(1993)
53. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
54. Chiang Lee, Zue-An Chang: Workload Balance and Page Access Scheduling For Parallel Joins In Shared-Nothing Systems. ICDE 1993: 411-418
55. Kien A. Hua, Jeffrey X. W. Su, Chau M. Hua: Efficient Evaluation of Traversal Recursive Queries Using Connectivity Index. ICDE 1993: 549-558
56. Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59
57. Ludger Becker, Klaus Hinrichs, Ulrich Finke: A New Algorithm for Computing Joins with Grid Files. ICDE 1993: 190-197
58. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
59. Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies. SIGMOD Conference 1992: 256-265
60. Wei Lu, Jiawei Han: Distance-Associated Join Indices for Spatial Range Search. ICDE 1992: 284-292
61. Bin Jiang: I/O-Efficiency of Shortest Path Algorithms: An Analysis. ICDE 1992: 12-19
62. Philippe Pucheral, Jean-Marc Thévenin: Pipelined Query Processing in the DBGraph Storage Model. EDBT 1992: 516-533
63. Jenn-Yang Tien, Wei-Pang Yang: Comments on 'Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers'. IEEE Trans. Knowl. Data Eng. 3(3): 387-389(1991)
64. Arie Segev, J. Leon Zhao: Data Management for Large Rule Systems. VLDB 1991: 297-307
65. Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157
66. Arie Segev, J. Leon Zhao: Evaluation of Rule Processing Strategies In Expert Databases. ICDE 1991: 404-412
67. Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509
68. William Perrizo, James Gustafson, Daniel Thureen, David Wenberg: Domain Vector Accelerator for Relational Operations. ICDE 1991: 491-498
69. Josephine M. Cheng, Donald J. Haderle, Richard Hedges, Balakrishna R. Iyer, Ted Messinger, C. Mohan, Yun Wang: An Efficient Hybrid Join Algorithm: A DB2 Prototype. ICDE 1991: 171-180
70. Jong-Jin Sung, Jong-Tae Park: Semantic Query Processing in Object-Oriented Database Systems. DASFAA 1991: 11-20
71. Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990)
72. Philippe Pucheral, Jean-Marc Thévenin, Patrick Valduriez: Efficient Main Memory Data Management Using the DBGraph Storage Model. VLDB 1990: 683-695
73. Alfons Kemper, Guido Moerkotte: Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990: 290-301
74. Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673
75. Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311
76. Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
77. Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88
78. John Sieg Jr., Edward Sciore: Extended Relations. ICDE 1990: 488-494
79. José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263
80. Andreas Heuer, Jürgen Fuchs, U. Wiebking: OSCAR: An Object-Oriented Database System with a Nested Relational Kernel. ER 1990: 95-110
81. Yuki Kusumi, Shojiro Nishio, Toshiharu Hasegawa: File Access Level Optimization Using Page Access Graph on Recursive Query Evaluation. EDBT 1990: 136-152
82. Edward Omiecinski, Eileen Tien Lin: Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers. IEEE Trans. Knowl. Data Eng. 1(3): 329-343(1989)
83. Farshad Fotouhi, Sakti Pramanik: Optimal Secondary Storage Access Sequence for Performing Relational Join. IEEE Trans. Knowl. Data Eng. 1(3): 318-328(1989)
84. Marguerite C. Murphy, Doron Rotem: Effective Resource Utilization for Multiprocessor Join Execution. VLDB 1989: 67-75
85. Elisabetta Grazzini, Fabio Pippolini: A Strategy for Executing Complex Queries. MFDBS 1989: 207-221
86. Marguerite C. Murphy, Doron Rotem: Processor Scheduling for Multiprocessor Joins. ICDE 1989: 140-148
87. Jean-Pierre Cheiney, Christophe de Maindreville: Relational Storage and Efficient Retrieval of Rules in a Deductive DBMS. ICDE 1989: 644-651
88. Rakesh Agrawal, H. V. Jagadish: Materialization and Incremental Update of Path Information. ICDE 1989: 374-383
89. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
90. Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330
91. Aladdin Hafez, Gultekin Özsoyoglu: The Partial Normalized Storage Model of Nested Relations. VLDB 1988: 100-111
92. Anand Deshpande, Dirk Van Gucht: An Implementation for Nested Relational Databases. VLDB 1988: 76-87
93. Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
94. Don S. Batory: Concepts for a Database System Compiler. PODS 1988: 184-192
95. Setrag Khoshafian, Patrick Valduriez, George P. Copeland: Parallel Query Processing for Complex Objects. ICDE 1988: 202-209
96. Pankaj Goyal, H. F. Li, E. Regener, Fereidoon Sadri: Scheduling of Page Fetches in Join Operations Using Bc-Trees. ICDE 1988: 304-310
97. Bruce G. Lindsay, John McPherson, Hamid Pirahesh: A Data Management Extension Architecture. SIGMOD Conference 1987: 220-226
98. Setrag Khoshafian, George P. Copeland, Thomas Jagodis, Haran Boral, Patrick Valduriez: A Query Processing Strategy for the Decomposed Storage Model. ICDE 1987: 636-643
99. Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110
100. Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541