Maintaining the transitive closure of graphs in SQL

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 ll 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. Inter-estingly, these examples also allow us to show the relationship between power and cost in the incremental maintenance of database queries.