Database Reference
In-Depth Information
PKs
ICs
Complexity
no
GEN
PTIME/PSPACE
yes
no
PTIME/NP
yes
FK
PTIME/PSPACE
yes
NKC
PTIME/PSPACE
yes
GEN
undecidable
where GEN stands for general ICs, and NKC for non-key-conflicting ICs (in [ 2 ]).
The FK is in the class of NKC, so that its complexity is PTIME/PSPACE (PTIME
in data complexity, and PSPACE w.r.t. the size of the query), and consequently, in
the next section we will use this case of IC.
4.2.3 Query Rewriting in GAV with (Foreign) Key Constraints
This system provided in [ 2 ] has the following characteristics of the components of
a data integration system
I = G
,
S
,
M
:
The global schema is expressed in the relational model with the key and foreign
key integrity constraints Σ G =
Σ eg G
Σ tgd
G
. We assume that in such a global
schema
(S G G ) there is exactly one key constraint for each relation.
1. ( Key constraints ) Given a relational symbol r in the schema with arity n ,akey
constraint over r is expressed in the form key(r)
G =
,
the subset of key-attribute indexes. We denote the ordered sequence of indexes
in key(r) by K and define its complement set
={
i 1 ,...,i k }⊂{
1 , 2 ,...,n
}
{
j 1 ,...,j n k }={
1 , 2 ,...,n
}\
key(r)
so that
is a tuple of a subset of key-attributes of r . Such a con-
straint is satisfied in an instance-database A if for each t 1 , t 2 r A , t 1 =
x i 1 ,...,x i k
t 2
iff π K ( {
t 1 } ) = π K ( {
t 2 } ) , where π K is the projection over attributes with in-
dexes in K .
Such a key constraint can be represented by the egd
z r( y )
(y 1 1 =
z 1 k )
(P K)
y
r( z )
z 1 1 )
∧···∧
(y 1 k =
(y j 1 =
z j n k )
Σ egd
G
z j 1 )
∧···∧
(y j n k =
,
.
2. ( Foreign key constraints ) Given two relations r 1 and r 2 , a foreign key con-
straint is represented by the constraint π K (r 1 )
where y
=
y 1 ,...,y n
and z
=
z 1 ,...,z n
π K (r 2 ) where K is an or-
dered sequence of indexes in key(r 2 )
={
i 1 ,...,i h }⊆{
1 ,...,m
}
, m
=
ar(r 2 )
and h
constituting the key
of r 2 , and K is the correspondent sequence of the same attributes in r 1 . Such
n
=
ar(r 1 ) , with the sequence x
=
x i 1 ,...,x i h
Search WWH ::




Custom Search