by R Agrawal, A Borgida, H V Jagadish
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.
Reference:
Efficient management of transitive relationships in large data and knowledge bases (R Agrawal, A Borgida, H V Jagadish), In Proc ACM Symp on Management of Data SIGMOD, ACM, volume 18, 1989.
Bibtex Entry:
@inproceedings{Agrawal1989,
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.},
author = {Agrawal, R and Borgida, A and Jagadish, H V},
booktitle = {Proc ACM Symp on Management of Data SIGMOD},
doi = {10.1145/67544.66950},
isbn = {0897913175},
keywords = {SML-LIB-BIBLIO,lang:ENG},
mendeley-tags = {SML-LIB-BIBLIO,lang:ENG},
number = {2},
pages = {253--262},
publisher = {ACM},
title = {{Efficient management of transitive relationships in large data and knowledge bases}},
url = {http://portal.acm.org/citation.cfm?id=66950\&dl=GUIDE\&coll=GUIDE\&CFID=52216502\&CFTOKEN=82264087},
volume = {18},
year = {1989}
}