Introduction

In the relational model of databases a database state is thought of as a finite collection of relations between elements. The database relations (tables) are always going to be finite.

However, it is often convenient to assume that there is an infinite domain − for example, the integer or rational numbers or the strings − such that the data elements are chosen from this domain. Sometimes, the domain is called the universe. Functions and relations defined over the entire domain, like + and < , may also be used in querying. The domain functions and relations are infinite by their nature.

For example, if the language FO of first-order logic is used as the query language, its formulas may use the database relations as well as the domain relations, while variables range over the entire domain.

Speaking informally, for querying, the restricted query language uses stored information only but the extended one also uses a general knowledge, for example, the knowledge of the addition of the natural numbers in the case when the universe is
( N, <, +).


A database scheme r is a finite collection of relational symbols of fixed arities. A database state (over U ) of scheme r (in symbols, r-state) is an assignment to these relational symbols of concrete relations of corresponding arities over U. These relations are called database relations.

A database state is called a finite database state if all the relations are finite.

A r-state s over an L-structure W is said to be pseudo-finite in W if (W,s) is a model of the first-order
L(r)-theory of all (W,p), where p is a finite r-state over W.

Previous page
Next page