Constraint Databases

Main Idea Constraints are natural to describe temporal, spatial and geographic data.  Since time and space are infinite, spatial and temporal objects are commonly expressed over rational or real variables using linear or polynomial inequalities.  For example, a rectangle can be described by the following constraint tuple: Rectangle(x, y) :- x >= 0,  x <= 10,   y >= 0,  y <= 20. Each constraint tuple is a conjunction of inequalities using the same set of variables. In the rectangle example the spatial variables are x and y.  The Rectangle(x, y) constraint tuple means the set of (x, y) points that satisfy all the four inequalities.  There are an infinite number of such points.  A constraint relation is a finite set of constraint tuples. A constraint database is a finite set of constraint relations.  In 1990, Kanellakis, Kuper, and Revesz introduced constraint query languages that accept constraint databases as input and give constraint databases as output. This constraint data model is a natural generalization of the relational data model in which relational query languages accept relational databases as input and give relational databases as output.   When writing constraint database queries, one needs to keep in mind only the schemes of the relations and not the actual constraints within the relations. At query time the constraint relations can be viewed as only an infinite size relation. Hence it is as simple to write constraint database queries as to write relational database queries. Nevertheless, one can do more with SQL and constraint databases than with SQL and relational databases because the infinite size relations are more expressive than finite size relations. It seems a little magic to be able to do more without actually doing more effort in writing queries. However, there is some extra work needed inside by the constraint query evaluation engine. In general, the constraint query evaluation engine needs to work harder and smarter than a relational query evaluation engine. The constraint database systems listed below are only a start of implementation efforts. Interested in contributing to this area? Learn more about constraint databases from the references below and contact us in email.
Bibliography A bibliography with links to on-line publications.	Contact Peter Revesz revesz AT cse.unl.edu · Shasha Wu swu AT arbor.edu
Conferences on Constraint Databases Workshop in Dagstuhl, Germany, May 2007 CDB'04 in Paris, France, June 2004. CDB'98 in Seattle, WA, USA, May 1998. CDB'97 in Delphi, Greece, January 1997. CDB'96 in Cambridge, MA, USA, August 1996. CDB'95 in Friedrichshafen, Germany, September 1995.	Constraint Database Systems CQA/CDB CCUBE DEDALE MLPQ
Books Gabriel Kuper, Leonid Libkin, and Jan Paredaens, editors Constraint Databases. Springer Verlag, 2000. Peter Revesz Introduction to Constraint Databases. Springer Verlag, 2002. Peter Revesz Introduction to Databases: From Biological to Spatio-Temporal Springer Verlag 2010.

Copyright 2010. Peter Revesz, Shasha Wu