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
h5e7632a93f2a4a96
Venue
SIGMOD
Year
1989
Pagerank
0.00021927874
Overall Rank
294 | 98.03%
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
274
3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009
SIGMOD
0.00022490994
330
Fast and Practical Indexing and Querying of Very Large Graphs 2007
SIGMOD
0.00020838159
382
TEDI: Efficient Shortest Path Query Answering on Graphs 2010
SIGMOD
0.00019485934
453
Stack-based Algorithms for Pattern Matching on DAGs 2005
VLDB
0.00017972038
693
GRAIL: Scalable Reachability Index for Large Graphs 2010
VLDB
0.00014734389
774
Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008
SIGMOD
0.00014083518
1,329
A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011
SIGMOD
0.00011000029
1,563
TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013
SIGMOD
0.00010224369
1,849
Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014
SIGMOD
9.5068688e-05
2,534
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
8.3335732e-05
2,563
SCARAB: Scaling Reachability Computation on Large Graphs 2012
SIGMOD
8.2934229e-05
2,566
Stratified Computation of Skylines with Partially-Ordered Domains 2005
SIGMOD
8.288424e-05
2,604
K-Reach: Who is in Your Small World 2012
VLDB
8.2302549e-05
2,848
On Maintaining Priorities in a Production Rule System 1991
VLDB
7.9429561e-05
3,348
Simple, Fast, and Scalable Reachability Oracle 2013
VLDB
7.3926236e-05
4,049
Reachability Querying: An Independent Permutation Labeling Approach 2014
VLDB
6.8302372e-05
4,291
Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008
SIGMOD
6.6827339e-05
5,334
Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances 2008
VLDB
6.1750849e-05
5,451
Distributed Transitive Closure Computations: The Disconnection Set Approach 1990
VLDB
6.1243992e-05
5,584
Efficient Main Memory Data Management Using the DBGraph Storage Model 1990
VLDB
6.0763134e-05
5,717
Microblog Entity Linking with Social Temporal Context 2015
SIGMOD
6.0191048e-05
5,748
An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010
SIGMOD
6.0079624e-05
6,200
On Querying Historical Connectivity in Temporal Graphs 2024
SIGMOD
5.8510904e-05
7,635
Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008
VLDB
5.4785904e-05
7,724
Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024
VLDB
5.4672516e-05
7,768
Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012
VLDB
5.4558207e-05
7,840
DAG Reduction: Fast Answering Reachability Queries 2017
SIGMOD
5.442834e-05
8,193
Labeling Recursive Workflow Executions On-the-Fly 2011
SIGMOD
5.3803708e-05
8,937
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5.2559789e-05
11,540
Constant-time Connectivity Querying in Dynamic Graphs 2024
SIGMOD
4.9793485e-05
11,586
On Reducing Space Amplification with Multi-Column Compaction in Apache IoTDB 2024
VLDB
4.9793485e-05
12,643
Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012
VLDB
4.9793485e-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,534
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
2
7,576
A Generalized Transitive Closure for Relational Queries 1988
PODS
3
1,329
A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011
SIGMOD
4
8,937
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5
8,195
On Tree-Based Techniques for Query Evaluation 1992
PODS
6
1,287
On the Computation of the Transitive Closure of Relational Operators 1986
VLDB
7
1,416
Estimating the Size of Generalized Transitive Closures 1989
VLDB
8
1,140
Direct Algorithms for Computing the Transitive Closure of Database Relations 1987
VLDB
9
1,363
Efficient Transitive Closure Algorithms 1988
VLDB
10
1,110
New Strategies for Computing the Transitive Closure of a Database Relation 1987
VLDB