Efficient management of transitive relationships in large data and knowledge bases

Rakesh Agrawal, Alexander Borgida, H. V. Jagadish

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

We argue that accessing the transitive closure of relationships is an important component of both databases and knowledge representation systems in Artificial Intelligence. The demands for efficient access and management of large relationships motivate the need for explicitly storing the transitive closure in a compressed and local way, while allowing updates to the base relation to be propagated incrementally. We present a transitive closure compression technique, based on labeling spanning trees with numeric intervals, and provide both analytical and empirical evidence of its efficacy, including a proof of optimality.

Original languageEnglish (US)
Title of host publicationProceedings of the 1989 ACM SIGMOD International Conference on Management of Data, SIGMOD 1989
PublisherAssociation for Computing Machinery
Pages253-262
Number of pages10
ISBN (Electronic)0897913175
DOIs
StatePublished - Jun 1 1989
Event1989 ACM SIGMOD International Conference on Management of Data, SIGMOD 1989 - Portland, United States
Duration: May 31 1989Jun 2 1989

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
VolumePart F130127
ISSN (Print)0730-8078

Other

Other1989 ACM SIGMOD International Conference on Management of Data, SIGMOD 1989
Country/TerritoryUnited States
CityPortland
Period5/31/896/2/89

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems

Fingerprint

Dive into the research topics of 'Efficient management of transitive relationships in large data and knowledge bases'. Together they form a unique fingerprint.

Cite this