Quasilinear Algorithms for Processing Relational Calculus Expressions.

@inproceedings{DBLP:conf/pods/Willard90,
  author    = {Dan E. Willard},
  title     = {Quasilinear Algorithms for Processing Relational Calculus Expressions},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {243-257},
  ee        = {http://doi.acm.org/10.1145/298514.298570, db/conf/pods/Willard90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Throughout this paper q will denote a query such that I is the number of tuples inputed into the query, and U is the number of tuples in its output. We will say that q has quasi-linear complexity iff for some constant d, it is executable in time O(U + I log^dI) and space O(I+U). This article will define a large subset of the relational calculus, called RCS, and show that all RCS queries are executable by quasi-linear algorithms.

Our algorithm does not require the maintenance of any complex index, as it builds all the needed data structures during the course of the executing algorithm. Its exponent d can be large for some particular queries q, but it is a quite nice constant equal to 1 or 0 in most practical cases. Our algorithm is intended for data bases stored in main memory, and its time O(U + I log^dI) should amount to only a few seconds of CPU time in many practical applications.

Chapter 10 of this paper lists some open questions for further investigation.

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

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[BFMU83]

Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) 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

[BC81]

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

[BG81]

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

[Ch86a]

Bernard Chazelle: Lower Bounds on the Complexity of Multidimensional Searching (Extended Abstract). FOCS 1986: 87-96 BibTeX

[Ch86b]

Bernard Chazelle: Filtering Search: A New Approach to Query-Answering. SIAM J. Comput. 15(3): 703-724(1986) BibTeX

[Ch88]

Bernard Chazelle: A Functional Approach to Data Structures and Its Use in Multidimensional Searching. SIAM J. Comput. 17(3): 427-462(1988) BibTeX

[CP87]

Jiazhen Cai, Robert Paige: Binding Performance at Language Design Time. POPL 1987: 85-97 BibTeX

[EO85]

Herbert Edelsbrunner, Mark H. Overmars: Batched Dynamic Solutions to Decomposable Searching Problems. J. Algorithms 6(4): 515-542(1985) BibTeX

[Fr81]

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

[FKS84]

Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31(3): 538-544(1984) BibTeX

[FW90]

...

[FMN85]

...

[GS82]

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

[GS83]

Nathan Goodman, Oded Shmueli: Syntactic Characterization of Tree Database Schemas. J. ACM 30(4): 767-786(1983) BibTeX

[Gr79]

...

[KP81]

Shaye Koenig, Robert Paige: A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306-318 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

[NT88]

Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX

[Ov88]

Mark H. Overmars: Efficient Data Structures for Range Searching on a Grid. J. Algorithms 9(2): 254-275(1988) BibTeX

[OS88]

Mark H. Overmars, Michiel H. M. Smid: Maintaining Range Trees in Secondary Memory (Extended Abstract). STACS 1988: 38-51 BibTeX

[Pa79]

...

[Ps84]

...

[PH86]

...

[PK82]

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

[Ul89]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[Wi78]

...

[Wi83]

...

[Wi84]

Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175 BibTeX

[Wi85]

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

[Wi86]

...

[Wi87]

Dan E. Willard: Multidimensional search trees that provide new types of memory reductions. J. ACM 34(4): 846-858(1987) BibTeX

[Wi89a]

...

[Wi89b]

Dan E. Willard: Lower Bounds for the Addition-Subtraction Operations in Orthogonal Range Queries and Related Problems. Inf. Comput. 82(1): 45-64(1989) BibTeX

[Wi90]

Dan E. Willard: Optimal Sample Cost Residues for Differential Database Batch Query Problems. J. ACM 38(1): 104-119(1991) BibTeX

[WL85]

Dan E. Willard, George S. Lueker: Adding Range Restriction Capability to Dynamic Data Structures. J. ACM 32(3): 597-617(1985) BibTeX

[Ya81]

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

[YO79]

...