Skip to main content

Maintaining Transitive Closure of Graphs in SQL

01 January 1999

New Image

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 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 the acyclic graphs, of the undirected graphs, and of the arbitrary directed graphs. Interestingly, these examples also allow us to show the relationship between power and cost in the incremental maintenance of database queries.