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