Document Type
Article
Publication Date
1999
Abstract
It is common knowledge that relational calculus and even SQL are not expressive enough to express recursive queries such as the transitive closure. In a real database system, one can overcome this problem by storing a graph together with its transitive closure and maintaining the latter whenever updates to the former occur. This leads to the concept of an incremental evaluation system, or IES.
Much is already known about the theory of IES but very little has been translated into practice. The purpose of this paper is to fill in this gap by providing a gentle introduction to and an overview of some recent theoretical results on IES.
The introduction is through the translation into SQL of three interesting positive maintenance results that have practical importance the maintenance of the transitive closure of acyclic graphs, of undirected graphs, and of arbitrary directed graphs. Interestingly, these examples also allow us to show the relationship between power and cost in the incremental maintenance of database queries.
Repository Citation
Dong, G.,
Libkin, L.,
Su, J.,
& Wong, L.
(1999). Maintaining Transitive Closure of Graphs in SQL. International Journal of Information Technology, 51 (1), 46-78.
https://corescholar.libraries.wright.edu/knoesis/399
Included in
Bioinformatics Commons, Communication Technology and New Media Commons, Databases and Information Systems Commons, OS and Networks Commons, Science and Technology Studies Commons
