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 SQLlike 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 aritybased 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 sigma11 hierarchy.
For example, whenever a kary Boolean query has a FOIES,
it is in (k+1)ary sigma11. Furthermore, whenever a kary Boolean query
has a FOIES with Boolean auxiliary relations, it is in kary
sigma11.
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 Sigma11 Arity Hierarchies.
Bulletin of the EATCS, 61:7279, 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, 222238.
PS

Guozhu Dong, Leonid Libkin, Jianwen Su, Limsoon Wong.
Maintaining Transitive Closure of Graphs in SQL.
International Journal of Information Technology,
5(1):4678, October 1999. (Reviewed invited paper.)
PS

Guozhu Dong, Leonid Libkin, Limsoon Wong.
Incremental Recomputation in Local Languages.
Information and Computation, 181:8898, 2003.
PS
Acknowledgements
This project is supported in part by the Japan Real World Computing
Partnership (Wong).
Last updated: 10/8/06, Limsoon Wong.