Lectures in Honor of Paris Kanellakis

       Dina Q Goldin, Brown University
       Constraint Databases 

Paris Kanellakis's pioneering paper in 1990 provided a 
framework for constraint databases by combining
concepts from constraint logic programming and 
relational databases. The principal idea is to generalize a
tuple (or record) data type to a conjunction of 
constraints from an appropriate language; for example,
order constraints or linear arithmetic constraints. 
Such a tuple can be seen as representing a large, possibly
even infinite, set of points in a compact way (e.g., 
for spatial databases and GIS). Constraint databases
have since become a very active area of database research. 

After a brief introduction to relational databases, 
we explain the semantics of constraint database
relations and queries, providing complexity results for 
several specific constraint classes. We consider the
various relational querying paradigms (declarative, 
procedural, and logic programming) and their
reinterpretation in the presence of constraints as 
first-class data. We highlight the basic design principles
for constraint databases, such as query closure and safety, 
efficiency of data representation and data access,
and query optimization. 

We discuss Paris Kanellakis's more recent work, 
including work on indexing, and constraint query algebras,
and survey other developments in the area (aggregation, 
complex objects, expressive power). The ultimate
goal of Paris Kanellakis's research was to enable 
commercial-quality implementations of constraint
databases. We look at some possible applications for 
constraint databases, and at the implementational
efforts currently under way. We conclude by considering 
the issues and the challenges that lay ahead.