A generalized transitive closure for relational queries

ABSTRACT

We augment relational algebra with a generalized transitive closure operator that allows for the efficient evaluation of a subclass of recursive queries. The operator is based on a composition operator which is as general as possible when the operator is required to be associative and when only relational algebra operators are used in its definition. The closure of such a composition can be computed using the well-known efficient algorithms designed for the computation of the usual transitive closure. Besides the case in which complete materialization of recursive relations are required, our strategy also yields an efficient solution in the case in which a selection is applied to the closure.

REFERENCES

• 1: Rakesh Agrawal, Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries, Proceedings of the Third International Conference on Data Engineering, p.580-590, February 03-05, 1987
• 2: Rakesh Agrawal , H. V. Jagadish, Direct Algorithms for Computing the Transitive Closure of Database Relations, Proceedings of the 13th International Conference on Very Large Data Bases, p.255-266, September 01-04, 1987
• 3: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 4: Francois Bancilhon, Naive evaluation of recursively defined relations, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• 5: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 6: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• 7: Yannis E. Ioannidis, On the Computation of the Transitive Closure of Relational Operators, Proceedings of the 12th International Conference on Very Large Data Bases, p.403-411, August 25-28, 1986
• 8: Ioannidis,Y.E, and E.Wong, An algebrmc approach to reeursive inference, Proc 1st International Conterence on Expert Database Systems, 1986, pp 209- 223
• 9: H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.331-344, May 27-29, 1987, San Francisco, California, United States
• 10: Hongjun Lu, New Strategies for Computing the Transitive Closure of a Database Relation, Proceedings of the 13th International Conference on Very Large Data Bases, p.267-274, September 01-04, 1987
• 11: Hongjun Lu , Krishna P. Mikkilineni , James P. Richardson, Design and Evaluation of Algorithms to Compute the Transitive Closure of a Database Relation, Proceedings of the Third International Conference on Data Engineering, p.112-119, February 03-05, 1987
• 12: J. F. Naughton, One-sided recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.340-348, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28695]
• 13: Maier, D, Relational Database Theory, Computer Science Press, Rockvdle, Md, 1983
• 14: Arnon Rosenthal , Sandra Heiler , Umeshwar Dayal , Frank Manola, Traversal recursion: a practical approach to supporting recursive applications, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.166-176, May 28-30, 1986, Washington, D.C., United States
• 15: Tarjan,R E, Depth first search and hnear graph algontl~ms, S/AM J Comput 1'2 (146-160), 1972
• 16: Ullman,J D, PrmcJples of Database Systems, 2nd EdztJon, Computer Science Press, Rockvllle, Md, 1982.
• 17: Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]
• 18: Valduriez,P, and H.Boral, EvaJuatlon of recurmve queries using join radices, Proc let Internatlonal Conference on Expert Database Systems, 1986, pp 197-208.
• 19: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]