Database Reference
In-Depth Information
use the revisited fixpoint semantics described in [
11
], based on the fact that, after
some point, the new tuples added into a canonical model insert only new Skolem
constants which are not useful in order to obtain
certain
answers true in all mod-
els of a database (note that this criterion was introduced in the (FRF) rules for the
foreign key constraints, defined previously in this section). In fact, the Skolem con-
stants are not part of any certain answer to conjunctive query. Consequently, we are
able to obtain a
finite subset
of a canonical
database
, which is large enough to obtain
all certain answers as follows:
Suppose that the retrieved global database stores a single tuple
a,b
in
r
and
with empty relation
s
, that is,
. Then,
by applying the above rule 1, we insert the tuple
(b,ω
0
)
in
s
and, successively, by
applying the rule 2, we add
(b,ω
1
)
in
r
and hence we can not apply more these rules
from the fact that
ω
1
/
r
ret(
I
,D)
={
a,b
}
and
s
ret(
I
,D)
={}
dom
and we cannot apply more the rule 1.
The following table represents the computation of the finite canonical instance
database
can
F
(
∈
I
,D)
:
r
can
F
(
I
,
D
)
s
can
F
(
I
,
D
)
a,b
b,ω
0
b,ω
1
Obviously, this finite database
can
F
(
I
,
D
)
does not satisfy the foreign key con-
straint 1, represented by the SOtgds
∃
f
1
(
∀
x
∀
y(r(x,y)
⇒
s(y,f
1
(x,y))))
(while
the constraint 2 by the SOtgd
∃
f
2
(
∀
x
∀
z(s(x,z)
⇒
r(x,f
2
(x,z))))
) with two
Skolem functions
f
1
and
f
2
.
The satisfaction of both FK integrity constraints, for the retrieved database
ret(
I
,D)
defined above (by
), will pro-
duce the following
infinite
canonical model
can(
I
,D)
of the global schema,
for the Tarski interpretation of Skolem functions
I
T
(f
1
),I
T
(f
2
)
:
U
r
ret(
I
,D)
={
a,b
}
,
s
ret(
I
,D)
={}
2
SK
such that
I
T
(f
1
)(a,b)
=
ω
0
and
I
T
(f
2
)(b,I
T
(f
1
)(a,b))
=
ω
1
for the two fresh
Skolem constants
ω
0
,ω
1
∈
→
SK
, in order to satisfy the monomorphism
α
∗
(
M
G
T
G
)
:
can
F
(
I
,D)
→
can(
I
,D)
of the diagram above, as follows:
r
can(
I
,
D
)
s
can(
I
,
D
)
a,b
b,ω
0
b,ω
1
ω
1
,ω
2
ω
1
,ω
3
ω
3
,ω
4
...
...
where
ω
0
=
f
1
(a,b)
,
ω
1
=
f
2
(b,ω
0
)
,
ω
2
=
f
1
(b,ω
1
)
,
ω
3
=
f
2
(ω
1
,ω
2
)
,
ω
4
=
f
1
(ω
1
,ω
3
)
,etc.
Consequently, instead of the infinite database
can(
I
,D)
we can materialize the
finite instance-database
can
F
(
,D)
, as a finite least fixpoint of the immediate-
consequence monotonic operator
T
B
applied to the retrieved database
ret(
I
,D)
and
use it in order to obtain the certain answers to lifted queries without query-rewriting.
This technique was used also in the case for the queries with negation [
12
], when it
is not possible to use the query-rewriting method described in the previous section.
I
