Database Reference
In-Depth Information
order to define this language, we assume that the target schema R
t
is enriched with a way
to distinguish constants from nulls. That is, we assume that there is a unary relation symbol
C, such that for every target instance
T
the interpretation of C in
T
is precisely the set of
constants in the domain of
T
. This is a very realistic assumption: practical languages allow
testing for nulls (e.g., the
IS NULL
condition in SQL; its negation thus defines constants).
Definition 7.6 (D
ATALOG
C(
=)
programs) A
constant-inequality
D
ATALOG
rule
is one of
the form:
S
(
x
)
←
S
1
(
x
1
)
,...,
S
(
x
)
,
C(
y
1
)
,...,
C(
y
m
)
,
u
1
=
v
1
,...,
u
n
=
v
n
,
(7.4)
such that:
(1)
S
,
S
1
,
...
,
S
are (not necessarily distinct) relation symbols,
(2) every variable in
x
is mentioned in some tuple
x
i
,for1
≤
i
≤
,
(3) every variable
y
j
,for1
≤
j
≤
m
, is mentioned in some tuple
x
i
,for1
≤
i
≤
,
≤
≤
(4) every variable
u
j
and every variable
v
j
,for1
j
n
, is equal to some variable
y
i
,for
≤
≤
1
i
m
.
A
constant-inequality
D
ATALOG
program
(D
ATALOG
C(
=)
program)
is a finite set of
constant-inequality D
ATALOG
rules. A D
ATALOG
program is a D
ATALOG
C(
=)
program
without inequalities.
Π
That is, D
ATALOG
C(
=)
programs are just the usual D
ATALOG
programs enriched with
inequalities which can only be checked for constants, and not nulls. This is syntactically
enforced by condition (4) in the definition of a D
ATALOG
C(
=)
=
y
appears in a D
ATALOG
C(
=)
rule, then the atoms C(
x
) and C(
y
), binding
x
and
y
to the set
of constants, must also appear in it.
The following is an example of a constant-inequality D
ATALOG
program:
rule: if the inequality
x
R
(
x
,
y
)
←
T
(
x
,
z
)
,
S
(
z
,
y
)
,
C(
x
)
,
C(
z
)
,
x
=
z
S
(
x
)
←
U
(
x
,
u
,
v
,
w
)
,
C(
u
)
,
C(
v
)
,
u
=
v
.
For a rule of the form
(7.4)
, we say that
S
(
x
) is its head. The set of predicates of a
D
ATALOG
C(
=)
program
Π
, denoted by
Pred
(
Π
), is the set of predicate symbols mentioned
in
Π
, while the set of intensional predicates of
Π
, denoted by
IPred
(
Π
), is the set of pred-
icates symbols
R
∈
Pred
(
Π
) such that
R
(
x
) appears as the head of some rule of
Π
.
Fix a D
ATALOG
C(
=)
program
Π
and let
I
be a database instance of the relational schema
Pred
(
Π
).Then
T
(
I
) is an instance of
Pred
(
Π
) such that for every
R
∈
Pred
(
Π
) and every
R
T
(
I
)
tuple
t
, it holds that
t
∈
if and only if there exists a rule
R
(
x
)
←
R
1
(
x
1
)
,...,
R
(
x
)
,
C(
y
1
)
,...,
C(
y
m
)
,
u
1
=
v
1
,...,
u
n
=
v
n
in
Π
and a variable assignment
σ
such that:
(
x
)=
t
,
1.
σ
R
i
,forevery1
2.
σ
(
x
i
)
∈
≤
i
≤
,
