Database Paper Browser

Back to papers

Efficient Management of Transitive Relationships in Large Data and Knowledge Bases

Summary: Efficient access to transitive closure in large data and knowledge bases; advocates explicit, compressed, local storage with incremental propagation of base-relations updates. Proposes transitive-closure compression via labeling spanning trees with numeric intervals; offers analytic and empirical validation and a proof of optimality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2446
Venue
SIGMOD
Year
1989
Pagerank
0.00030949575
Overall Rank
246 | 98.30%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank Citing Paper Year Venue Pagerank
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027081079
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025097452
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023598882
733 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00017460741
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
1,553 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011402871
1,777 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.00010589591
1,880 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010226347
2,148 On Maintaining Priorities in a Production Rule System 1991 VLDB 9.4295586e-05
2,756 K-Reach: Who is in Your Small World 2012 VLDB 8.1682536e-05
2,866 Stratified Computation of Skylines with Partially-Ordered Domains 2005 SIGMOD 7.9844444e-05
2,957 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8198686e-05
3,127 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 7.5046522e-05
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
4,143 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.4129418e-05
4,478 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.1506256e-05
4,852 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8764777e-05
5,004 Efficient Main Memory Data Management Using the DBGraph Storage Model 1990 VLDB 5.76478e-05
5,161 Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances 2008 VLDB 5.6558914e-05
5,479 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 5.4850984e-05
5,802 An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010 SIGMOD 5.3209459e-05
6,657 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 4.9720132e-05
7,367 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 4.7514687e-05
7,584 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.7041255e-05
7,596 DAG Reduction: Fast Answering Reachability Queries 2017 SIGMOD 4.7016964e-05
7,716 Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024 VLDB 4.6696364e-05
8,054 Labeling Recursive Workflow Executions On-the-Fly 2011 SIGMOD 4.5947587e-05
8,572 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4937074e-05
10,985 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.1945683e-05
11,049 On Reducing Space Amplification with Multi-Column Compaction in Apache IoTDB 2024 VLDB 4.1945683e-05
12,156 Comments on “Stack-based Algorithms for Pattern Matching on DAGs” 2012 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
55 Efficiently Updating Materialized Views 1986 SIGMOD 0.00065762967
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
363 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025715157
653 A Performance Analysis of View Materialization Strategies 1987 SIGMOD 0.00018626606
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
3,984 CLASSIC: A Structural Data Model for Objects 1989 SIGMOD 6.5634369e-05
4,428 Database Support for Knowledge-Based Image Evaluation 1987 VLDB 6.1961267e-05
12,942 Incorporating Hierarchy in a Relational Model of Data 1989 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,957 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8198686e-05
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
1,553 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011402871
8,572 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4937074e-05
7,293 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7740089e-05
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109