Quasilinear algorithms for processing relational calculus expressions (preliminary report)

ABSTRACT

Throughout this paper q will denote a query such that I is the number of tuples inputted 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 logdI) 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 logdI) 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.

REFERENCES

• BFMU83: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• Be75: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• Be80: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• BC81: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• BG81: P.A. Bernstein and N. Goodman, "The power of natural semijoins", SIAM J. Comp 10(1981) 751-771.
• Ch86a: B. Chazelle, "Lower Bounds on Complexity of Multidimension Search", 27th IEEE Syrup. on Foundatiorts of Computer Science, 87-96 (1987).
• Ch86b: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• Ch88: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• CP87: J. Cai , R. Paige, Binding performance at language design time, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.85-97, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41633]
• EO85: H. Edelsbrunner and M. Overmars, "Batch Solutions to Decomposable Search Problems", Journal of Algorithms, 6, 515-543 (1985).
• 81: Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
• FKS84: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• FW90: M.L. Fredman and D.E. Willard, "Sublogarithmic Retrieval and Faster than NlogN Sorting With Fusion Trees", Technical Report, to appear.
• FMN85: O. Fries , K. Mehlhorn , St. Näher, Dynamization of geometric data structures, Proceedings of the first annual symposium on Computational geometry, p.168-176, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323256]
• GS82: Nathan Goodman , Oded Shmueli, Tree queries: a simple class of relational queries, ACM Transactions on Database Systems (TODS), v.7 n.4, p.653-677, Dec. 1982 [doi>10.1145/319758.319775]
• GS83: Nathan Goodman , Oded Shmueli, Syntactic Characterization of Tree Database Schemas, Journal of the ACM (JACM), v.30 n.4, p.767-786, Oct. 1983 [doi>10.1145/2157.322405]
• Gr79: M.H. Graham, "On the Universal Relation", University of Toronto technical report, 1979.
• KP81: S. Koenig and R. Paige, "A Transformational Framework for the Automatic Control of Derived Data", 7th Int. Conf. on VLDB, 306-318 (Sept. 1981).
• LW77: D.T. Lee and C.K. Wong, "Worst-case Analysis of Region and Partial Region Searches in Multidimensional Binary Search Trees and Quad Trees", Acts Informatica 9, 23-29 (1977).
• NT88: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• Ov88: Mark H. Overmars, Efficient data structures for range searching on a grid, Journal of Algorithms, v.9 n.2, p.254-275, June 1988 [doi>10.1016/0196-6774(88)90041-7]
• OS88: Mark H. Overmars , Michiel H. M. Smid, Maintaining Range Trees in Secondary Memory (Extended Abstract), Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.38-51, February 11-13, 1988
• Pa79: R. Paige, UMI Research Press, Ann Arbor, Mich., 1981. Revision of Ph.D. thesis, NYU, (June 1979).
• Pa84: R. Paige, "Applications of Finite Differencing to Database Integrity Control and Query Translation Optimization", published in Advances in Database Theory, editors J.H. Minker, J.M. Nicolas and H. Gullaire, Plenum Press, 1984.
• PH86: R. Paige and F. Hengleim, "Mechanical Translation of Set-Theoretic Problem Specification into Efficient RAM Code", IBM Report RC 12169, (1986).
• PK82: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• Ul89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Wi78: D.E. Willard, Predicate-Oriented Database Search Algorithms Harvard Ph.D. dissertation May 1978, published in the Garland Publishing Home's series of Outstanding Dissertations in Computer Science under the abbreviated title of "Search Algorithms".
• Wi83: D.E. Willard, "Predicate Retrieval Theory", 21-st Allerton Conference on Communications, Control and Computing (1983) pp. 663-674 and more details in SUNY Albany TR 83-3 (78 pages).
• Wi84: Dan E Willard, Efficient processing of relational calculus expressions using range query theory, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• Wi85: Dan E. Willard, New data structures for orthogonal range queries, SIAM Journal on Computing, v.14 n.1, p.232-253, Feb. 1985 [doi>10.1137/0214019]
• Wi86: D E Willard, On the application of sheared retrieval to orthogonal range queries, Proceedings of the second annual symposium on Computational geometry, p.80-89, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10524]
• Wi87: Dan E. Willard, Multidimensional search trees that provide new types of memory reductions, Journal of the ACM (JACM), v.34 n.4, p.846-858, Oct. 1987 [doi>10.1145/31846.42228]
• Wi89a: D.E. Willard, "Application of Range Query Theory to Relational Database Selection and Join Operations", Technical Report, Department of Computer Science, University at Albany (1989).
• Wi89b: Dan E. Willard, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, Information and Computation, v.82 n.1, p.45-64, July 1989 [doi>10.1016/0890-5401(89)90064-3]
• Wi90: Dan E. Willard, Optimal sample cost residues for differential database batch query problems, Journal of the ACM (JACM), v.38 n.1, p.104-119, Jan. 1991 [doi>10.1145/102782.102786]
• WL85: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]
• Ya81: M. Yannakakis, "Algorithms for acyclic database schemes", Proc. lml. Conf. on VLDB, 82-94 (1981).
• YO79: C.T. Yu and M. Z. Ozsoyoglu, "An Algorithm for Tree Membership of a Distributed Query", Proceeding of IEEE Comp~ac 1979, 306-312.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Design, Management, Performance, Theory, Verification