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.00021884281
Overall Rank
293 | 98.04%
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.00022625826
331
Fast and Practical Indexing and Querying of Very Large Graphs 2007
SIGMOD
0.00020800828
376
TEDI: Efficient Shortest Path Query Answering on Graphs 2010
SIGMOD
0.00019655871
456
Stack-based Algorithms for Pattern Matching on DAGs 2005
VLDB
0.00017946233
694
GRAIL: Scalable Reachability Index for Large Graphs 2010
VLDB
0.00014681018
779
Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008
SIGMOD
0.00014049427
1,341
A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011
SIGMOD
0.00010960707
1,564
TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013
SIGMOD
0.00010186448
1,859
Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014
SIGMOD
9.4722343e-05
2,541
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
8.3021057e-05
2,568
SCARAB: Scaling Reachability Computation on Large Graphs 2012
SIGMOD
8.2649684e-05
2,573
Stratified Computation of Skylines with Partially-Ordered Domains 2005
SIGMOD
8.2576057e-05
2,617
K-Reach: Who is in Your Small World 2012
VLDB
8.2001569e-05
2,858
On Maintaining Priorities in a Production Rule System 1991
VLDB
7.9141449e-05
3,357
Simple, Fast, and Scalable Reachability Oracle 2013
VLDB
7.3652047e-05
4,076
Reachability Querying: An Independent Permutation Labeling Approach 2014
VLDB
6.8048601e-05
4,307
Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008
SIGMOD
6.6581902e-05
5,354
Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances 2008
VLDB
6.1517601e-05
5,472
Distributed Transitive Closure Computations: The Disconnection Set Approach 1990
VLDB
6.10153e-05
5,596
Efficient Main Memory Data Management Using the DBGraph Storage Model 1990
VLDB
6.054203e-05
5,732
Microblog Entity Linking with Social Temporal Context 2015
SIGMOD
5.9963673e-05
5,748
An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010
SIGMOD
5.9914851e-05
6,209
On Querying Historical Connectivity in Temporal Graphs 2024
SIGMOD
5.8323161e-05
7,655
Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008
VLDB
5.4578901e-05
7,743
Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024
VLDB
5.4465939e-05
7,793
Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012
VLDB
5.4352151e-05
7,861
DAG Reduction: Fast Answering Reachability Queries 2017
SIGMOD
5.4225547e-05
8,216
Labeling Recursive Workflow Executions On-the-Fly 2011
SIGMOD
5.3600428e-05
8,965
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5.2361195e-05
11,595
Constant-time Connectivity Querying in Dynamic Graphs 2024
SIGMOD
4.9605343e-05
11,640
On Reducing Space Amplification with Multi-Column Compaction in Apache IoTDB 2024
VLDB
4.9605343e-05
12,692
Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012
VLDB
4.9605343e-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,541
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
2
7,599
A Generalized Transitive Closure for Relational Queries 1988
PODS
3
1,341
A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011
SIGMOD
4
8,965
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5
8,218
On Tree-Based Techniques for Query Evaluation 1992
PODS
6
1,292
On the Computation of the Transitive Closure of Relational Operators 1986
VLDB
7
1,423
Estimating the Size of Generalized Transitive Closures 1989
VLDB
8
1,142
Direct Algorithms for Computing the Transitive Closure of Database Relations 1987
VLDB
9
1,368
Efficient Transitive Closure Algorithms 1988
VLDB
10
1,112
New Strategies for Computing the Transitive Closure of a Database Relation 1987
VLDB