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
2447
Venue
SIGMOD
Year
1989
Pagerank
0.00030342925
Overall Rank
255 | 98.23%
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
280 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029092277
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027077424
377 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025074538
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023592024
727 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00017462279
784 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016648392
1,551 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011395294
1,776 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.0001058029
1,879 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010227906
2,152 On Maintaining Priorities in a Production Rule System 1991 VLDB 9.4201789e-05
2,762 K-Reach: Who is in Your Small World 2012 VLDB 8.1614818e-05
2,873 Stratified Computation of Skylines with Partially-Ordered Domains 2005 SIGMOD 7.9777806e-05
2,958 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8126329e-05
3,130 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 7.5054361e-05
3,676 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8500097e-05
4,143 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.4096394e-05
4,478 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.1452192e-05
4,855 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8698466e-05
5,005 Efficient Main Memory Data Management Using the DBGraph Storage Model 1990 VLDB 5.7599923e-05
5,160 Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances 2008 VLDB 5.650425e-05
5,488 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 5.4798261e-05
5,816 An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010 SIGMOD 5.3158435e-05
6,660 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 4.9672425e-05
7,362 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 4.7469116e-05
7,588 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.6996269e-05
7,595 DAG Reduction: Fast Answering Reachability Queries 2017 SIGMOD 4.6980168e-05
7,714 Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024 VLDB 4.6651585e-05
8,056 Labeling Recursive Workflow Executions On-the-Fly 2011 SIGMOD 4.5903524e-05
8,569 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4893996e-05
10,988 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.1905499e-05
11,052 On Reducing Space Amplification with Multi-Column Compaction in Apache IoTDB 2024 VLDB 4.1905499e-05
12,164 Comments on “Stack-based Algorithms for Pattern Matching on DAGs” 2012 VLDB 4.1905499e-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.00065687017
157 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.0004048407
364 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025657601
658 A Performance Analysis of View Materialization Strategies 1987 SIGMOD 0.00018566555
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.0001629507
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
3,986 CLASSIC: A Structural Data Model for Objects 1989 SIGMOD 6.5574084e-05
4,467 Database Support for Knowledge-Based Image Evaluation 1987 VLDB 6.1545735e-05
12,952 Incorporating Hierarchy in a Relational Model of Data 1989 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,958 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8126329e-05
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05
1,551 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011395294
8,569 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4893996e-05
7,289 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7692311e-05
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.0001629507
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866