A Generalized Transitive Closure for Relational Queries.

Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332

@inproceedings{DBLP:conf/pods/SippuS88,
  author    = {Seppo Sippu and
               Eljas Soisalon-Soininen},
  title     = {A Generalized Transitive Closure for Relational Queries},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {325-332},
  ee        = {http://doi.acm.org/10.1145/308386.308467, db/conf/pods/SippuS88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. 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
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. 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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]: Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 BibTeX
[2]: Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 BibTeX
[3]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[4]: ...
[5]: François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[6]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[7]: Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX
[8]: Yannis E. Ioannidis, Eugene Wong: An Algebraic Approach to Recursive Inference. Expert Database Conf. 1986: 295-309 BibTeX
[9]: H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 BibTeX
[10]: Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 BibTeX
[11]: Hongjun Lu, Krishna P. Mikkilineni, James P. Richardson: Design and Evaluation of Algorithms to Compute the Transitive Closure of a Database Relation. ICDE 1987: 112-119 BibTeX
[12]: Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX
[13]: David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[14]: Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[15]: Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
[16]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[17]: Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[18]: Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX
[19]: Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) BibTeX

Referenced by

Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334
Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]