Efficient Processing of Relational Calculus Expressions Using Range Query Theory.

@inproceedings{DBLP:conf/sigmod/Willard84,
  author    = {Dan E. Willard},
  editor    = {Beatrice Yormark},
  title     = {Efficient Processing of Relational Calculus Expressions Using
               Range Query Theory},
  booktitle = {SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts,
               June 18-21, 1984},
  publisher = {ACM Press},
  year      = {1984},
  pages     = {164-175},
  ee        = {http://doi.acm.org/10.1145/602259.602281, db/conf/sigmod/Willard84.html},
  crossref  = {DBLP:conf/sigmod/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1984 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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• 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/smod7592 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/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[Ab74]

...

[ABU79]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX

[AHU74]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[BC81]

Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX

[Be75]

Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX

[Be80]

Jon Louis Bentley: Multidimensional Divide-and-Conquer. Commun. ACM 23(4): 214-229(1980) BibTeX

[BFMMUY81]

Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX

[BFMY83]

Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX

[BG81a]

Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX

[BG81b]

Philip A. Bernstein, Nathan Goodman: The power of inequality semijoins. Inf. Syst. 6(4): 255-265(1981) BibTeX

[BM80]

Jon Louis Bentley, Hermann A. Maurer: Efficient Worst-Case Data Structures for Range Searching. Acta Inf. 13: 155-168(1980) BibTeX

[BS77]

...

[BS80]

Jon Louis Bentley, James B. Saxe: Decomposable Searching Problems I: Static-to-Dynamic Transformation. J. Algorithms 1(4): 301-358(1980) BibTeX

[Ch76]

Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX

[CH80]

D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX

[CH83]

Bernard Chazelle: Filtering Search: A New Approach to Query-Answering. FOCS 1983: 122-132 BibTeX

[Co70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[CY83]

Richard Cole, Chee-Keng Yap: Geometric Retrieval Problems. FOCS 1983: 112-121 BibTeX

[Da83]

Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136 BibTeX

[Ed81]

...

[EO83]

...

[EW83]

...

[Fa83]

Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX

[FKS82]

Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with O(1) Worst Case Access Time. FOCS 1982: 165-169 BibTeX

[Fr81]

Michael L. Fredman: A Lower Bound on the Complexity of Orthogonal Range Queries. J. ACM 28(4): 696-705(1981) BibTeX

[GP84]

...

[GS82]

Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982) BibTeX

[HK80]

...

[HS81a]

...

[HS81b]

Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. Computer Science Press 1978
BibTeX

[Hu83]

Richard Hull: Acyclic Join Dependency and Data Base Projections. J. Comput. Syst. Sci. 27(3): 331-349(1983) BibTeX

[JK83]

Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206 BibTeX

[Kn73]

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

[KP81]

Shaye Koenig, Robert Paige: A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306-318 BibTeX

[KTY82]

Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) BibTeX

[Li82]

Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX

[LST81]

Y. Edmund Lien, Jonathan E. Shopiro, Shalom Tsur: DSIS - A Database System with Interrelational Semantics. VLDB 1981: 465-477 BibTeX

[LW77]

D. T. Lee, C. K. Wong: Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees. Acta Inf. 9: 23-29(1977) BibTeX

[LW80]

D. T. Lee, C. K. Wong: Quintary Trees: A File Structure for Multidimensional Database Systems. ACM Trans. Database Syst. 5(3): 339-353(1980) BibTeX

[MSY82]

David Maier, Yehoshua Sagiv, Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695(1981) BibTeX

[MU82]

David Maier, Jeffrey D. Ullman: Connections in Acyclic Hypergraphs. PODS 1982: 34-39 BibTeX

[OL82]

Mark H. Overmars, Jan van Leeuwen: Dynamic Multi-Dimensional Data Structures Based on Quad- and K - D Trees. Acta Inf. 17: 267-285(1982) BibTeX

[Pa79]

...

[Pa81]

Christos H. Papadimitriou: On the Power of Locking. SIGMOD Conference 1981: 148-154 BibTeX

[Pa84]

Robert Paige: Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. Advances in Data Base Theory 1982: 171-209 BibTeX

[PK82]

Robert Paige, Shaye Koenig: Finite Differencing of Computable Expressions. ACM Trans. Program. Lang. Syst. 4(3): 402-454(1982) BibTeX

[RND77]

...

[RSL78]

Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX

[Sh81]

David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX

[Sk77]

...

[SLR76]

Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

[Ul82]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Wi78a]

...

[Wi78b]

Dan E. Willard: New Data Structures for Orthogonal Range Queries. SIAM J. Comput. 14(1): 232-253(1985) BibTeX

[Wi78c]

...

[Wi82]

Dan E. Willard: Polygon Retrieval. SIAM J. Comput. 11(1): 149-165(1982) BibTeX

[Wi83a]

...

[Wi83b]

...

[Wi83c]

...

[Wi83d]

Dan E. Willard: Log-Logarithmic Worst-Case Range Queries are Possible in Space Theta(N). Inf. Process. Lett. 17(2): 81-84(1983) BibTeX

[Wi84a]

Dan E. Willard: Sampling Algorithms for Differential Batch Retrieval Problems (Extended Abstract). ICALP 1984: 514-526 BibTeX

[Wi84b]

Dan E. Willard: Log-Logarithmic Protocols for Resolving Ethernet and Semaphore Conflicts (Preliminary Report). STOC 1984: 512-521 BibTeX

[Wi84c]

Dan E. Willard: New Trie Data Structures Which Support Very Fast Search Operations. J. Comput. Syst. Sci. 28(3): 379-394(1984) BibTeX

[WL84]

...

[WY76]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

[Ya81]

Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

[Ya83]

F. Frances Yao: A 3-Space Partition and Its Applications (Extended Abstract). STOC 1983: 258-263 BibTeX

[Yo79]

...

[Za76]

...

[Ya82]

Andrew Chi-Chih Yao: Space-Time Tradeoff for Answering Range Queries (Extended Abstract). STOC 1982: 128-136 BibTeX

Referenced by

1. Dan E. Willard: Quasilinear Algorithms for Processing Relational Calculus Expressions. PODS 1990: 243-257
2. Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)
3. Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985)