Incremental SQL Queries

Participants: Guozhu Dong, Leonid Libkin, Limsoon Wong

Background

Many queries such as transitive closure cannot be computed by SQL from scratch. However, many such queries can be maintained using SQL, given a previous answer and new record to be inserted or deleted. This phenomenon has an important practical implication, because the designer of a database application can plan for these type of queries by allocating some extra tables to stored their answers and maintaining these tables as records are inserted or deleted from the base tables. This project makes a thorough study of the expressive power of SQL and related query languages in such an ``incremental'' mode.

Achievements

We showed that queries such as transitive closure cannot be maintained, when records are deleted from the base table, in SQL-like query languages without using auxiliary relations. In fact, even ``deterministic'' transitive closure cannot be maintained under this situation. We further generalized this result to all query languages that are ``local'' in the sense of Gaifman.
On the other hand, we showed that transitive closure, alternating paths, same generation, and other recursive queries, can be maintained in SQL if some auxiliary relations are allowed. In fact, they can all be maintained using at most auxiliary relations of arity 2. This is in contrast to maintenance in relational algebra, a.k.a. FOIES, which admits a strict arity-based hierarchy.
We also proved a number of interesting connections between FOIES (i.e., relational algebra in ``incremental'' mode, possibly with some auxiliary relations) and the sigma-1-1 hierarchy. For example, whenever a k-ary Boolean query has a FOIES, it is in (k+1)-ary sigma-1-1. Furthermore, whenever a k-ary Boolean query has a FOIES with Boolean auxiliary relations, it is in k-ary sigma-1-1.

Selected Publications

Guozhu Dong, Leonid Libkin, Limsoon Wong. On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL. Springer Electronic Workshop in Computing: Proceedings of 5th International Workshop on Database Programming Languages, Gubbio, Italy, 8, September 1995. PS
Guozhu Dong, Limsoon Wong. Some Relationships between the FOIES and Sigma-1-1 Arity Hierarchies. Bulletin of the EATCS, 61:72--79, February 1997. PS
Leonid Libkin, Limsoon Wong. Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. Proceedings of 6th International Workshop on Database Programming Languages, Estes Park, Colorado, August 1997, 222--238. PS
Guozhu Dong, Leonid Libkin, Jianwen Su, Limsoon Wong. Maintaining Transitive Closure of Graphs in SQL. International Journal of Information Technology, 5(1):46--78, October 1999. (Reviewed invited paper.) PS
Guozhu Dong, Leonid Libkin, Limsoon Wong. Incremental Recomputation in Local Languages. Information and Computation, 181:88--98, 2003. PS

Acknowledgements

This project is supported in part by the Japan Real World Computing Partnership (Wong).

Last updated: 10/8/06, Limsoon Wong.