L-rigid Databases and the Expressibility of Incomplete Relational Query Languages

Abstract

The class of Computable Queries (CQ) was de ned by Chandra and Harel in 1980, as functions on structures rather than functions on numbers (as recursive functions). With this formulation of the notion of a query to a relational database (db), the field of Finite Model Theory became a suitable theoretical framework for relational databases. In this framework the notion of local expressibility of a given logic is the class of queries which can be expressed in that logic. On the other hand, in 1991, Abiteboul and Vianu de fined the Generic Machine, denoted as GMloose, which they proved to be strictly included in CQ. They also proved that this class of machines behaves as complete w.r.t. the whole class CQ when working on classes of ordered db. If we consider the structures as db instances, and if we are using a GMloose machine, it means that we will not be able to compute queries such as \give me the names of the salesmen who sell to an even number of clients unless our db is ordered. In the present Thesis, we study some properties of relational db which can increase the expressive power of relational languages or formalisms which are incomplete in the general case, when working on classes of db which satisfy that properties.