ACM SIGMOD Anthology TODS dblp.uni-trier.de

A Compression Technique to Materialize Transitive Closure.

H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990)
@article{DBLP:journals/tods/Jagadish90,
  author    = {H. V. Jagadish},
  title     = {A Compression Technique to Materialize Transitive Closure},
  journal   = {ACM Trans. Database Syst.},
  volume    = {15},
  number    = {4},
  year      = {1990},
  pages     = {558-598},
  ee        = {http://doi.acm.org/10.1145/99935.99944, db/journals/tods/Jagadish90.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

An important feature of database support for expert systems is the ability of the database to answer queries regarding the existence of a path from one node to another in the directed graph underlying some database relation. Given just the database relation, answering such a query is time-consuming, but given the transitive closure of the database relation a table look-up suffices. We present an indexing scheme that permits the storage of the pre-computed transitive closure of a database relation in a compressed form. The existence of a specified tuple in the closure can be determined from this compressed store by a single look-up followed by an index comparison. We show how to add nodes and arcs to the compressed closure incrementally. We also suggest how this compression technique can be used to reduce the effort required to compute the transitive closure.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

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, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990) BibTeX
[3]
Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66 BibTeX
[4]
Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262 BibTeX
[5]
Rakesh Agrawal, H. V. Jagadish: Materialization and Incremental Update of Path Information. ICDE 1989: 374-383 BibTeX
[6]
...
[7]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[8]
Jay Banerjee, Won Kim, Sung-Jo Kim, Jorge F. Garza: Clustering a DAG for CAD Databases. IEEE Trans. Software Eng. 14(11): 1684-1699(1988) BibTeX
[9]
Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX
[10]
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX
[11]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[12]
...
[13]
Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. ICDE 1988: 452-461 BibTeX
[14]
...
[15]
...
[16]
Antonin Guttman: New Features for Relational Database Systems to Support CAD Applications. Ph.D. thesis, University of California, Berkeley 1984
BibTeX
[17]
Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453 BibTeX
[18]
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
[19]
Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX
[20]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 BibTeX
[21]
Giuseppe F. Italiano: Amortized Efficiency of a Path Retrieval Data Structure. Theor. Comput. Sci. 48(3): 273-281(1986) BibTeX
[22]
H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 BibTeX
[23]
H. V. Jagadish: Incorporating Hierarchy in a Relational Model of Data. SIGMOD Conference 1989: 78-87 BibTeX
[24]
...
[25]
...
[26]
Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202 BibTeX
[27]
Shaye Koenig, Robert Paige: A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306-318 BibTeX
[28]
Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 BibTeX
[29]
Vishv M. Malhotra, M. Pramodh Kumar, S. N. Maheshwari: An O(|V|³) Algorithm for Finding Maximum Flows in Networks. Inf. Process. Lett. 7(6): 277-278(1978) BibTeX
[30]
...
[31]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[32]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
[33]
...
[34]
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX
[35]
...
[36]
Ingrid M. Walter, Peter C. Lockemann, Hans-Hellmut Nagel: Database Support for Knowledge-Based Image Evaluation. VLDB 1987: 3-11 BibTeX
[37]
...

Referenced by

  1. Ismail H. Toroslu, Ghassan Z. Qadah: The Strong Partial Transitive-Closure Problem: Algorithms and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 8(4): 617-629(1996)
  2. Jukka Teuhola: Path Signatures: A Way to Speed Up Recursion in Relational Databases. IEEE Trans. Knowl. Data Eng. 8(3): 446-454(1996)
  3. Sakti Pramanik, Sungwon Jung: Description and Identification of Distributed Fragments of Recursive Relations. IEEE Trans. Knowl. Data Eng. 8(6): 1002-1016(1996)
  4. Chris Clifton, Hector Garcia-Molina, David Bloom: HyperFile: A Data and Query Model for Documents. VLDB J. 4(1): 45-86(1995)
  5. H. V. Jagadish: The INCINERATE Data Model. ACM Trans. Database Syst. 20(1): 71-110(1995)
  6. Rakesh Agrawal, H. V. Jagadish: Algorithms for Searching Massive Graphs. IEEE Trans. Knowl. Data Eng. 6(2): 225-238(1994)
  7. Qi Yang, Clement T. Yu, Chengwen Liu, Son Dao, Gaoming Wang, Tracy Pham: A Hybrid Transitive Closure Algorithm for Sequential and Parallel Processing. ICDE 1994: 498-505
  8. Jukka Teuhola: An Efficient Relational Implementation of Recursive Relationships using Path Signatures. ICDE 1994: 348-355
  9. Rakesh Agrawal, Jerry Kiernan: An Access Structure for Generalized Transitive Closure Queries. ICDE 1993: 429-438
  10. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:09 2008