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 .
Search WWH ::




Custom Search