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
2508
Venue
SIGMOD
Year
1989
Pagerank
0.0002242162
Overall Rank
282 | 98.07%
DOI
10.1145/67544.66950
Incoming Non-self Citations Over Time
BibTeX Citation
@inproceedings{agrawal_sigmod89,
title = {{Efficient Management of Transitive Relationships in Large Data and Knowledge Bases}},
author = {Agrawal, Rakesh and Borgida, Alexander and Jagadish, H. V.},
series = {{SIGMOD} '89},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/67544.66950},
url = {https://dl.acm.org/doi/10.1145/67544.66950},
year = {1989}
}
Incoming Citations (Sorted by Pagerank)
Showing 32 of 32 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
269
3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009
SIGMOD
0.00022786599
322
Fast and Practical Indexing and Querying of Very Large Graphs 2007
SIGMOD
0.00021275303
370
TEDI: Efficient Shortest Path Query Answering on Graphs 2010
SIGMOD
0.00019937972
444
Stack-based Algorithms for Pattern Matching on DAGs 2005
VLDB
0.00018350865
679
GRAIL: Scalable Reachability Index for Large Graphs 2010
VLDB
0.00015055389
746
Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008
SIGMOD
0.00014402233
1,301
A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011
SIGMOD
0.00011255351
1,533
TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013
SIGMOD
0.00010467148
1,796
Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014
SIGMOD
9.7380494e-05
2,490
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
8.5090456e-05
2,516
Stratified Computation of Skylines with Partially-Ordered Domains 2005
SIGMOD
8.4773324e-05
2,575
K-Reach: Who is in Your Small World 2012
VLDB
8.3982298e-05
2,820
On Maintaining Priorities in a Production Rule System 1991
VLDB
8.0911708e-05
3,021
SCARAB: Scaling Reachability Computation on Large Graphs 2012
SIGMOD
7.8401031e-05
3,278
Simple, Fast, and Scalable Reachability Oracle 2013
VLDB
7.5712342e-05
3,979
Reachability Querying: An Independent Permutation Labeling Approach 2014
VLDB
6.9754185e-05
4,221
Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008
SIGMOD
6.8233111e-05
5,209
Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances 2008
VLDB
6.3163287e-05
5,341
Distributed Transitive Closure Computations: The Disconnection Set Approach 1990
VLDB
6.2602701e-05
5,495
Efficient Main Memory Data Management Using the DBGraph Storage Model 1990
VLDB
6.1987657e-05
5,590
Microblog Entity Linking with Social Temporal Context 2015
SIGMOD
6.1557283e-05
5,724
An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010
SIGMOD
6.108728e-05
6,075
On Querying Historical Connectivity in Temporal Graphs 2024
SIGMOD
5.9853864e-05
7,494
Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008
VLDB
5.6043267e-05
7,578
Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024
VLDB
5.5927377e-05
7,622
Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012
VLDB
5.5806644e-05
7,707
DAG Reduction: Fast Answering Reachability Queries 2017
SIGMOD
5.5636745e-05
8,049
Labeling Recursive Workflow Executions On-the-Fly 2011
SIGMOD
5.500317e-05
8,775
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5.3766157e-05
11,198
Constant-time Connectivity Querying in Dynamic Graphs 2024
SIGMOD
5.093636e-05
11,257
On Reducing Space Amplification with Multi-Column Compaction in Apache IoTDB 2024
VLDB
5.093636e-05
12,352
Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012
VLDB
5.093636e-05
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.
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
2,490
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
2
7,438
A Generalized Transitive Closure for Relational Queries 1988
PODS
3
1,301
A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011
SIGMOD
4
8,775
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5
8,035
On Tree-Based Techniques for Query Evaluation 1992
PODS
6
1,259
On the Computation of the Transitive Closure of Relational Operators 1986
VLDB
7
1,382
Estimating the Size of Generalized Transitive Closures 1989
VLDB
8
1,114
Direct Algorithms for Computing the Transitive Closure of Database Relations 1987
VLDB
9
1,330
Efficient Transitive Closure Algorithms 1988
VLDB
10
1,086
New Strategies for Computing the Transitive Closure of a Database Relation 1987
VLDB