Database Reference
In-Depth Information
ple
a
n
,
must be distinct: if we use two equal domains for different attributes then we
denote them by
a
i
(
1
),...,a
i
(k)
(
a
i
equals to
a
i
(
0
)
). Each index (“column”)
i
,
1
=
atr(r)
=
atr
r
(
1
),..., atr
r
(n)
where all
a
i
=
atr
r
(m)
∈
att
,
1
≤
m
≤
≤
i
≤
ar(r)
, has a distinct column name
nr
r
(i)
∈
SN
where
SN
is the set of
names with
nr(r)
can be used as an
atom
r(
x
)
of FOL with variables in
x
assigned to its columns, so that
Σ
A
de-
notes a set of sentences (FOL formulae without free variables) called
integrity
constraints
of the sorted FOL with sorts in
att
. We denote the empty schema
by
=
nr
r
(
1
),...,nr
r
(n)
. A relation
r
∈ R
is the relation with empty set of attributes (
truth
propositional letter in FOL, Definition
1
), and we denote the set of all database
schemas for a given (also infinite) set
A
∅
=
(
{
r
∅
}
,
∅
)
, where
r
∅
R
by
S
.
•
An
instance-database
of a nonempty schema
A
is given by
A
=
(
A
,I
T
)
={
R
=
where
I
T
is a Tarski's FOL interpretation in Definition
1
which satisfies
all
integrity constraints in
Σ
A
and maps a relational symbol
r
r
=
I
T
(r)
|
r
∈
S
A
}
A
. Thus, an instance-database
A
is a
set of
n
-ary relations, managed by relational database systems (DBMSs). Let
A
and
A
=
∈
S
A
into an
n
-ary relation
R
=
r
∈
,I
T
)
be two instances of
A
is a
homo-
(
A
A
, then a function
h
:
A
→
morphism
from
A
into
A
if for every
k
-ary relational symbol
r
∈
S
A
and every
tuple
is a tuple of the
same symbol
r
in
A
.If
A
is an instance-database and
φ
is a sentence then we
write
A
v
1
,...,v
k
of this
k
-ary relation in
A
,
h(v
1
),...,h(v
k
)
φ
to mean that
A
satisfies
φ
.If
Σ
is a set of sentences then we write
A
|=
Σ
to mean that
A
|=
φ
for every sentence
φ
∈
Σ
. Thus the set of all in-
stances of
|=
A
is defined by
Inst(
A
)
={
A
|
A
|=
Σ
A
}
. We denote the set of all
values in
A
by
val(A)
⊆
U
. Then 'atomic database' J
A
={{
v
i
}|
v
i
∈
val(A)
}
is infinite iff
SK
⊆
val(A)
. Note that for each
a
∈
atr(r)
, a subset
dom(a)
⊆
dom
is finite, and any introduction of Skolem constants is ordered
ω
0
,ω
1
,...
.
•
We consider a rule-based
conjunctive query
over a database schema
A
as an
←−
≥
expression
q(
x
)
r
1
(
u
1
),...,r
n
(
u
n
)
, with finite
n
0,
r
i
are the relational
symbols (at least one) in
A
or the built-in predicates (e.g.,
≤
,
=
,etc.),
q
is a
relational symbol not in
and
u
i
are free tuples (i.e., one may use either vari-
ables or constants). Recall that if
v
A
(v
1
,...,v
m
)
then
r(
v
)
is a shorthand for
r(v
1
,...,v
m
)
. Finally, each variable occurring in
x
is a
distinguished
variable
that must also occur at least once in
u
1
,...,
u
n
. Rule-based conjunctive queries
(called rules) are composed of a subexpression
r
1
(
u
1
),...,r
n
(
u
n
)
that is the
body
, and the
head
of this rule
q(
x
)
.The
Ye s/No
conjunctive queries are the
rules with an empty head. If we can find values for the variables of the rule,
such that the body is logically satisfied, then we can deduce the head-fact. This
concept is captured by a notion of “valuation”. The deduced head-facts of a con-
junctive query
q(
x
)
defined over an instance
A
(for a given Tarski's interpreta-
tion
I
T
of schema
=
k
A
) are equal to
q(x
1
,...,x
k
)
A
={
v
1
,...,v
k
∈
U
|
A
|=
I
T
(
∃
r
n
(
u
n
)))
, where
y
is a set of variables which are not in the head of query. We recall that the conjunc-
tive queries are monotonic and satisfiable, and that a (Boolean) query is a class
of instances that is closed under isomorphism [
12
]. Each conjunctive query cor-
responds to a “select-project-join” term
t(
x
)
of SPRJU algebra obtained from
the formula
y
(r
1
(
u
1
)
∧···∧
r
n
(
u
n
))
[
x
i
/v
i
]
1
≤
i
≤
k
}=
∃
y
(r
1
(
u
1
)
∧···∧
∃
y
(r
1
(
u
1
)
∧···∧
r
n
(
u
n
))
, as explained in Sect.
5.1
.