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.00021917638
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.00022480767
330
Fast and Practical Indexing and Querying of Very Large Graphs 2007
SIGMOD
0.00020828552
382
TEDI: Efficient Shortest Path Query Answering on Graphs 2010
SIGMOD
0.00019477423
453
Stack-based Algorithms for Pattern Matching on DAGs 2005
VLDB
0.00017963727
693
GRAIL: Scalable Reachability Index for Large Graphs 2010
VLDB
0.00014727433
776
Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008
SIGMOD
0.00014076975
1,329
A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011
SIGMOD
0.00010994864
1,563
TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013
SIGMOD
0.00010219537
1,850
Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014
SIGMOD
9.502574e-05
2,535
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
8.3296282e-05
2,563
SCARAB: Scaling Reachability Computation on Large Graphs 2012
SIGMOD
8.2895644e-05
2,566
Stratified Computation of Skylines with Partially-Ordered Domains 2005
SIGMOD
8.2845085e-05
2,606
K-Reach: Who is in Your Small World 2012
VLDB
8.2264537e-05
2,848
On Maintaining Priorities in a Production Rule System 1991
VLDB
7.9393628e-05
3,348
Simple, Fast, and Scalable Reachability Oracle 2013
VLDB
7.3891319e-05
4,050
Reachability Querying: An Independent Permutation Labeling Approach 2014
VLDB
6.8270039e-05
4,291
Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008
SIGMOD
6.6795809e-05
5,339
Prefix Based Numbering Schemes for XML: Techniques, Applications and Performances 2008
VLDB
6.1721633e-05
5,456
Distributed Transitive Closure Computations: The Disconnection Set Approach 1990
VLDB
6.1215612e-05
5,585
Efficient Main Memory Data Management Using the DBGraph Storage Model 1990
VLDB
6.0735021e-05
5,718
Microblog Entity Linking with Social Temporal Context 2015
SIGMOD
6.0162555e-05
5,749
An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010
SIGMOD
6.0051184e-05
6,205
On Querying Historical Connectivity in Temporal Graphs 2024
SIGMOD
5.8483206e-05
7,641
Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008
VLDB
5.475997e-05
7,730
Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024
VLDB
5.4646635e-05
7,777
Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012
VLDB
5.4532403e-05
7,844
DAG Reduction: Fast Answering Reachability Queries 2017
SIGMOD
5.4402574e-05
8,201
Labeling Recursive Workflow Executions On-the-Fly 2011
SIGMOD
5.3778252e-05
8,945
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5.2534908e-05
11,546
Constant-time Connectivity Querying in Dynamic Graphs 2024
SIGMOD
4.9769913e-05
11,592
On Reducing Space Amplification with Multi-Column Compaction in Apache IoTDB 2024
VLDB
4.9769913e-05
12,649
Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012
VLDB
4.9769913e-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,535
Computing Label-Constraint Reachability in Graph Databases 2010
SIGMOD
2
7,583
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,945
A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990
VLDB
5
8,203
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,364
Efficient Transitive Closure Algorithms 1988
VLDB
10
1,110
New Strategies for Computing the Transitive Closure of a Database Relation 1987
VLDB