A compression technique to materialize transitive closure

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 comparision. 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.

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 , Shaul Dar , H. V. Jagadish, Direct transitive closure algorithms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.15 n.3, p.427-458, Sept. 1990 [doi>10.1145/88636.88888]
• 3: R. Agrawal , H. V. Jagadish, Multiprocessor transitive closure algorithms, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.56-66, December 05-07, 1988, Austin, Texas, United States
• 4: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 5: Rakesh Agrawal , H. V. Jagadish, Materialization and Incremental Update of Path Information, Proceedings of the Fifth International Conference on Data Engineering, p.374-383, February 06-10, 1989
• 6: BANCILHON, F. Naive evaluation of recursively defined relations. Tech. Rep. DB-004-85, MCC, Austin, Tex., 1985.
• 7: 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
• 8: J. Banerjee , W. Kim , S.-J. Kim , J. F. Garza, Clustering a DAG for CAD Databases, IEEE Transactions on Software Engineering, v.14 n.11, p.1684-1699, November 1988 [doi>10.1109/32.9055]
• 9: C. Beeri , P. Kanellakis , F. Bancilhon , R. Ramakrishnan, Bounds on the propagation of selection into logic programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-226, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28683]
• 10: Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
• 11: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 12: BRACHMAN, R. J., AND SCHMOLZE, J.G. An overview of the KL-ONE knowledge representation system. Cognitive Sci. 92. (April-June 1985), 171-216.
• 13: Rakesh Agrawal , Premkumar T. Devanbu, Moving Selections into Linear Least Fixpoint Queries, Proceedings of the Fourth International Conference on Data Engineering, p.452-461, February 01-05, 1988
• 14: DILWORTH, R.P. A decomposition theorem for partially ordered sets. Ann. Math. 5I, (1950), 161-166.
• 15: DINIC, E.A. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Dokl. 11 (1970), 1277-1280.
• 16: Antonin Guttman, New features for a relational database system to support computer aided design, 1984
• 17: Eric N. Hanson, A performance analysis of view materialization strategies, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.440-453, May 27-29, 1987, San Francisco, California, United States
• 18: Richard Hull , Roger King, Semantic database modeling: survey, applications, and research issues, ACM Computing Surveys (CSUR), v.19 n.3, p.201-260, Sept. 1987 [doi>10.1145/45072.45073]
• 19: 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
• 20: Yannis E. Ioannidis , Raghu Ramakrishnan, Efficient Transitive Closure Algorithms, Proceedings of the 14th International Conference on Very Large Data Bases, p.382-394, August 29-September 01, 1988
• 21: G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, v.48 n.2-3, p.273-281, Dec., 1986
• 22: 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
• 23: H. V. Jagadish, Incorporating hierarchy in a relational model of data, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.78-87, June 1989, Portland, Oregon, United States
• 24: FORD, L. R., JR., AND FULKERSON, D. R. Flows ia Networks. Princeton University Press, Princeton, N.J., 1962.
• 25: KARZANOV, A.V. Determining the maximal flow in a network by the method of preflows. Soviet Math. Dokl. 15 (1974), 434-437.
• 26: Michael Kifer , Eliezer L Lozinskii, Filtering data flow in deductive databases, Proceedings on International conference on database theory, p.186-202, December 1986, Rome, Italy
• 27: KOENIG, S., AND PAIGE, R. A transformational framework for the automatic control of derived data. In Proceedings 7th International Conference on Very Large Data Bases (1981), 306-318
• 28: 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
• 29: MALHOTRA, V. M., PaAMODH KUMAR, M., AND MAHESHWARI, S.N. An 0(! V{3) Algorithm for finding maximum flow in networks. Inf. Process. Lett. 7, 6 (Oct. 1978), 277-278.
• 30: Kurt Mehlhorn, Graph algorithms and NP-completeness, Springer-Verlag New York, Inc., New York, NY, 1984
• 31: 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
• 32: TARJAN, R. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2 (June 1972), 146-160.
• 33: David S. Touretzky, The mathematics of inheritance systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• 34: VALDURIEZ, P., AND BORAL, H. Evaluation of recursive queries using join indices. In Proceedings 1st International Conference on Expert Database Systems (Charleston, S.C., April 1986), 197-208.
• 35: Patrick Valduriez , Setrag Khoshafian, Parallel evaluation of the transitive closure of a database relation, International Journal of Parallel Programming, v.17 n.1, p.19-42, Feb. 1988 [doi>10.1007/BF01379321]
• 36: Ingrid M. Walter , Peter C. Lockemann , Hans-Hellmut Nagel, Database Support for Knowledge-Based Image Evaluation, Proceedings of the 13th International Conference on Very Large Data Bases, p.3-11, September 01-04, 1987
• 37: ZLOOF, M.M. Query-by-example: Operations on the transitive closure. Tech. Rep. RC 5526, IBM, Yorktown Heights, N. Y., 1975.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Performance