TITLE: ``Constraint Databases''

ABSTRACT:

Until very recently, databases were restricted to the storage and the manipulation of finite collections of data items. New applications such as those involving temporal and spatial data (e.g., geographical databases) lead very naturally to more general data models allowing infinite collections of items to be stored in the database. A new generation of data models, allowing the representation of infinite collections is now emerging in the literature. Various classes of infinite databases have been considered. The choice of an adequate data model is governed by two fundamental principles: (i) infinite databases should admit a finite representation (finite memory), and (ii) a reasonable set of queries should be tractable on the infinite databases (efficiency).

The finitely representable databases, considered in this talk, are definable by means of first-order formulas, following the trend opened by Kanellakis, Kuper and Revesz in PODS'90, where they introduced the constraint query languages. The basic idea is to generalize the relations of the relational model by defining generalized tuples as conjunctions of constraints. For instance, (x^2 + y^2 = 1) AND (x <= 0) defines a binary generalized tuple. We will address various fundamental issues such as query languages, expressive power and efficiency, and a few implementation problems.

Joint work with Jianwen Su, UCSB, and Christophe Tollu, LIPN.

Everyone is welcome to attend.