Querying Constraint Databases

Participants: Guozhu Dong, Leonid Libkin, Limsoon Wong


A relational database is traditionally formalized as a collection of finite relations. But this has limitation in some applications such as representing and querying spatial data. Thus, Kanellakis, Kuper, and Revesz in their famous PODS'90 paper introduce the idea of constraint databases and query languages for dealing with this type of data and queries. The original idea of constraint query languages is that quantifiers in a query can range over (say) the entire universe of real numbers, as opposed to only over those real numbers that occur in the underlying database. That is, constraint query languages permit the use of quantifiers under the ``natural domain semantics'' interpretation, while traditional database query languages interpret quantifiers strictly under the ``active domain semantics''. This ability to quantify over an infinite universe gives rise to two problems: (i) Queries now may have input/output that are infinite, so how would you represent them? (ii) How would you compute the queries if variables range over an infinite universe? These problems are solved by choosing an infinite universe with an underlying structure that allows an infinite set (on the universe) to be finitely representable and effectively computable. In this project, we study issues relating to constraint query languages where the underlying universe is the real closed field. The constraint query languages we study include extensions (with infinite sets and quantification over the real closed field) of relational calculus, SQL, and nested relational calculus. Towards the end of this project, we also venture into the ``embedded'' model theory of infinitary logics.


The research above also got us interested in ``embedded'' finite model theory in the context of query languages...

Selected Publications


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

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