skip to main content
10.1145/1141277.1141385acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
Article

On the transitive closure representation and adjustable compression

Published: 23 April 2006 Publication History

Abstract

A composite object represented as a directed graph (digraph for short) is an important data structure that requires efficient support in CAD/CAM, CASE, office systems, software management, web databases, and document databases. It is cumbersome to handle such objects in relational database systems when they involve ancestor-descendant relationships (or say, recursive relationships). In this paper, we present a new encoding method to label a digraph, which reduces the footprints of all previous strategies. This method is based on a tree labeling method and the concept of branchings that are used in graph theory for finding the shortest connection networks. A branching is a subgraph of a given digraph that is in fact a forest, but covers all the nodes of the graph. On the one hand, the proposed encoding scheme achieves the smallest space requirements among all previously published strategies for recognizing recursive relationships. On the other hand, it leads to a new algorithm for computing transitive closures for DAGs (directed acyclic graph) in O(e·b) time and O(n·b) space, where n represents the number of the nodes of a DAG, e the numbers of the edges, and b the DAG's breadth. The method can also be extended to graphs containing cycles. Especially, based on this encoding method, a multi-level compression is developed, by means of which the space for the representation of a transitive closure can be reduced to O((b/dk)·n), where k is the number of compression levels and d is the average outdegree of the nodes.

References

[1]
S. Abdeddaim, On Incremental Computation of Transitive Closure and Greedy Alignment, in: Proc. 8th Symp. Combinatorial Pattern Matching, ed. Alberto Apostolico and Jotun Hein, 1997, pp. 167--179.]]
[2]
R. Agrawal, A. Borgida and H. V. Jagadish, "Efficient management of transitive relationships in large data and knowledge bases," Proc. of the 1989 ACM SIGMOD Intl. Conf. on Management of Data, Oregon, 1989, pp. 253--262.]]
[3]
R. Agrawal, S. Dar, H. V. Jagadish, "Direct transitive closure algorithms: Design and performance evaluation," ACM Trans. Database Syst. 15, 3 (Sept. 1990), pp. 427--458.]]
[4]
R. Agrawal and H. V. Jagadish, "Materialization and Incremental Update of Path Information," in: Proc. 5th Int. Conf. Data Engineering, Los Angeles, 1989, pp. 374--383.]]
[5]
R. Agarawal and H. V. Jagadish, "Hybrid transitive closure algorithms," In Proc. of the 16th Int. VLDB Conf., Brisbane, Australia, Aug. 1990, pp. 326--334.]]
[6]
M. F. van Bommel and T. J. Beck, "Incremental Encoding of Multiple Inheritance Hierarchies Supporting Lattice Operations, Linkoping Electronic Articles in Computer and Information Science, http://www.ep.liu.se/ea/cis/2000/001.]]
[7]
J. Banerjee, W. Kim, S. Kim and J. F. Garza, "Clustering a DAG for CAD Databases," IEEE Trans. on Knowledge and Data Engineering, Vol. 14, No. 11, Nov. 1988, pp. 1684--1699.]]
[8]
K. S. Booth and G. S. Leuker, "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms," J. Comput. Sys. Sci., 13(3):335--379, Dec. 1976.]]
[9]
F. Bancihon and R. Ramakrishnan, "An Amateurs Introduction to Recursive Query Processing Strategies," in: Proc. ACM SIGMOD Conf., Washington D. C., 1986, pp. 16--52.]]
[10]
M. Carey et al., "An Incremental Join Attachment for Star-burst," in: Proc. 16th VLDB Conf., Brisbane, Australia, 1990, pp. 662--673.]]
[11]
Y. Chen, K. Aberer, "Layered Index Structures in Document Database Systems," Proc. 7th Int. Conference on Information and Knowledge Management (CIKM), Bethesda, MD, USA: ACM, 1998, pp. 406--413.]]
[12]
Y. Chen and K. Aberer, "Combining Pat-Trees and Signature Files for Query Evaluation in Document Databases," in: Proc. of 10th Int. DEXA Conf. on Database and Expert Systems Application, Florence, Italy: Springer Verlag, Sept. 1999. pp. 473--484.]]
[13]
Y. Chen, "On the Graph Traversal and Linear Binary-chain Programs," IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3, May 2003, pp. 573--596.]]
[14]
N. H. Cohen, "Type-extension tests can be performed in constant time," ACM Transactions on Programming Languages and Systems, 13:626--629, 1991.]]
[15]
R. G. G. Cattell and J. Skeen, "Object Operations Benchmark," ACM Trans. Database Systems, Vol. 17, no. 1, pp. 1--31, 1992.]]
[16]
P. Dadam et al., "A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies," Proc. ACM SIGMOD Conf., Washington D.C., 1986, pp. 356--367.]]
[17]
S. Dar and R. Ramarkrishnan, "A Performance Study of Transitive Closure Algorithm," in Proc. of SIGMOD Int. Conf., Minneapolis, Minnesota, USA, 1994, pp. 454--465.]]
[18]
J. Dzikiewicz, "An Algorithm for Finding the Transitive Closure of a Digraph," Computing 15, 75--79, 1975.]]
[19]
J. Ebert, "A Sensitive Transitive closure Algorithm," Inf. Process Letters 12, 5 (1981).]]
[20]
J. Eve and R. Kurki-Suonio, "On Computing the Transitive Closure of a Relation," Acta Informatica 8, 303--314, 1977.]]
[21]
M. Fredman and R. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, proc. 25th IEEE Symp. on Foundations of Computer Science, pp. 338--346, 1984.]]
[22]
R. L. Haskin and R. A. Lorie, "On Extending the Functions of a Relational Database System," Proc. ACM SIGMOD Conf., Orlando, Fla., 1982, pp. 207--212.]]
[23]
T. Ibaraki and N. Katoh, On-line Computation of transitive closure for graphs, Information Processing Letters, 16:95--97, 1983.]]
[24]
G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, 48:273--281, 1986.]]
[25]
Y. E. Ioannidis, R. Ramakrishnan and L. Winger, "Transitive Closure Algorithms Based on Depth-First Search," ACM Trans. Database Syst., Vol. 18. No. 3, 1993, pp. 512--576.]]
[26]
H. V. Jagadish, "A Compression Technique to Materialize Transitive Closure," ACM Trans. Database Systems, Vol. 15, No. 4, 1990, pp. 558--598.]]
[27]
T. Keller, G. Graefe and D. Maier, "Efficient Assembly of Complex Objects," Proc. ACM SIGMOD conf. Denver, Colo., 1991, pp. 148--157.]]
[28]
W. Kim, "Object-Oriented Database Systems: Promises, Reality, and Future," Proc. 19th VLDB conf., Dublin, Ireland, 1993, pp. 676--687.]]
[29]
D. E. Knuth, The Art of Computer Programming, Vol.1, Addison-Wesley, Reading, 1969.]]
[30]
H. A. Kuno and E. A. Rundensteiner, "Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation," IEEE Transactions on Knowledge and Data Engineering, vol. 10. No. 5, 1998, pp. 768--792.]]
[31]
J. A. La Poutre and J. van Leeuwen, Maintenance of Transitive closure and transitive reduction of graphs, in Proc. Workshop on Graph-Theoretic Concepts in Computer Science, pp. 106--120. Lecture Notes in Computer Science 314, Springer-Verlag, 1988.]]
[32]
W. C. Lee and D. L Lee, "Path Dictionary: A New Access Method for Query Processing in Object-Oriented Databases," IEEE Transactions on Knowledge and Data Engineering, vol. 10. No. 3, 1998, pp. 371--388.]]
[33]
B. Lindsay, J. McPherson and H. Pirahesh, "A Data Management Extension Architecture," Proc. ACM SIGMOD conf., 1987, pp. 220--226.]]
[34]
K. Mehlhorn, "Graph Algorithms and NP-Completeness: Data Structure and Algorithm 2" Springer-Verlag, Berlin, 1984.]]
[35]
P. Purdom, "A Transitive Closure Algorithm," BIT 10, 76--94, 1970.]]
[36]
R. Ramakrishnan and J. D. Ullman, "A Survey of Research in Deductive Database Systems," J. Logic Programming, May, 1995, pp. 125--149.]]
[37]
L. Schmitz, "An Improved Transitive Closure Algorithm," Computing 30, 359--371 (1983).]]
[38]
M. Stonebraker, L. Rowe and M. Hirohama, "The Implementation of POSTGRES," IEEE Trans. Knowledge and Data Eng., vol. 2, no. 1, 1990, pp. 125--142.]]
[39]
L. D. Shapiro, "Join Processing in Database Systems with Large Main Memories," ACM Trans. Database Systems, vol. 11, no. 3, 1986, pp. 239--264.]]
[40]
M. A. Schubert and J. Taugher, "Determing type, part, colour, and time relationship," 16 (special issue on Knowledge Representation):53--60, Oct. 1983.]]
[41]
D. D. Sleator and R. Tarjan, Amortized efficiency of list update rules, Proc. 16th ACM Symp. on Theory of Computing, pp.488--492, 1984.]]
[42]
R. Tarjan: Depth-first Search and Linear Graph Algorithms, SIAM J. Compt. Vol. 1. No. 2. June 1972, pp. 146--140.]]
[43]
R. Tarjan: Finding Optimum Branching, Networks, 7. 1977, pp. 25--35.]]
[44]
R. Tarjan, Amortized computational complexity, SIAM J. Algebraic Discrete Methods 6, pp. 306--318, 1985.]]
[45]
J. Teuhola, "Path Signatures: A Way to Speed up Recursion in Relational Databases," IEEE Trans. on Knowledge and Data Engineering, Vol. 8, No. 3, June 1996, pp. 446--454.]]
[46]
S. Warshall, "A Theorem on Boolean Matrices," JACM, 9. 1(Jan. 1962), 11--12.]]
[47]
H. S. Warren, "A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations," Commun. ACM 18, 4 (April 1975), 218--220.]]
[48]
P. Valduriez and H. Boral, "Evaluation of Recursive Queries Using Join Indices," in: Proc. 1st Workshop on Expert Database Systems, Charleston, S. C., 1986, pp. 197--208.]]
[49]
P. Valduriez, S. Khoshafian and G. Copeland, "Implementation Techniques of Complex Objects," Proc. 12th VLDB Conf., Kyoto, Japan, 1986, pp. 101--109.]]
[50]
Y. Zibin and J. Gil, "Efficient Subtyping Tests with PQ-Encoding," Proc. of the 2001 ACM SIGPLAN conf. on Object-Oriented Programming Systems, Languages and Application, Florida, October 14--18, 2001, pp. 96--107.]]

Cited By

View all

Index Terms

  1. On the transitive closure representation and adjustable compression

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SAC '06: Proceedings of the 2006 ACM symposium on Applied computing
    April 2006
    1967 pages
    ISBN:1595931082
    DOI:10.1145/1141277
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 April 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. branchings
    2. databases
    3. directed acyclic graphs
    4. graph decomposition
    5. topological order
    6. transitive closures

    Qualifiers

    • Article

    Conference

    SAC06
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

    Upcoming Conference

    SAC '25
    The 40th ACM/SIGAPP Symposium on Applied Computing
    March 31 - April 4, 2025
    Catania , Italy

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 12 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2011)Decomposing DAGs into spanning treesProceedings of the 2011 IEEE 27th International Conference on Data Engineering10.1109/ICDE.2011.5767832(1007-1018)Online publication date: 11-Apr-2011
    • (2009)Graph Encoding and Transitive Closure RepresentationEncyclopedia of Information Science and Technology, Second Edition10.4018/978-1-60566-026-4.ch267(1696-1707)Online publication date: 2009
    • (2007)Decomposing DAGs into disjoint chainsProceedings of the 18th international conference on Database and Expert Systems Applications10.5555/2395856.2395889(243-253)Online publication date: 3-Sep-2007
    • (2007)Tree Encoding and Transitive Closure CompressionProceedings of the 11th International Conference Information Visualization10.1109/IV.2007.116(765-770)Online publication date: 4-Jul-2007
    • (2007)Decomposing DAGs into Disjoint ChainsDatabase and Expert Systems Applications10.1007/978-3-540-74469-6_25(243-253)Online publication date: 2007

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media