Database Reference
In-Depth Information
•
≈
w
'—two instance-databases
A
and
B
are weakly equivalent when each “certain” view (without Skolem constants)
obtained from a database
A
can be also obtained from a database
B
, and vicev-
ersa.
We will show the following inclusion relationships between them:
Weak observational equivalence
relation '
'
=
'
⊆
'
'
⊆
'
≈
'
⊆
'
≈
w
'
.
It is also possible to define other kinds of equivalences for databases. In the rest
of this chapter, we will consider only the last two equivalences defined above.
3.4.1 The (Strong) Behavioral Equivalence for Databases
Let us consider now the problem of defining the equivalent objects (instance-
databases) from a
behavioral point of view based on observations
: as we have seen,
each arrow (morphism) is composed of a number of “queries” (view-maps) and each
query may be considered as an
observation
over some database instance (i.e., an ob-
ject of
DB
). Thus, we can characterize each object in
DB
(i.e., an instance-database)
by its behavior according to a given set of observations.
Indeed, if one object
A
is considered as a black-box, the object
TA
is the set of
all observations on
A
. Thus, given two objects
A
and
B
, we are able to define the
relation of equivalence between them based on the notion of the bisimulation rela-
tion. If the observations (i.e., resulting views of queries) of the instance-databases
A
and
B
are always equal, independently of their particular internal structure, then
they look equivalent to an observer. In fact, any database can be seen as an Abstract
Object Type (AOT), presented in Sect.
2.4.2
by Definition
12
, with a number of in-
ternal states that can be observed by using query operators (i.e., programs without
side-effects). Consequently, two simple databases
A
and
B
are equivalent (or bisim-
ilar) if they provide the same set of observations, i.e., when the set of views
TA
is
equal to
TB
.
For the complex databases with separation operator ‡, represented equivalently
(up to isomorphisms) by non-symmetric disjoint union
, the behavioral equiva-
lence is more general relation than the isomorphism relation in
DB
category:
Definition 28
The relation of (strong) behavioral equivalence '
≈
' between objects
(databases) in
DB
is defined by the PO relation '
' (in Definition
19
)ontheset
Ob
DB
,
≈
A
B
iff
A
B
and
B
A.
g
iff
f
This equivalence relation for morphisms is defined by,
f
≈
≈
g
.
1
1
1
Notice that for any arrow
f
in
DB
,
f
⊥
≈⊥
f
≈
f
, where
⊥
=
α
∗
(
α
∗
(
1
r
∅
)
is an empty morphism between objects
(i.e., for any two objects
A
and
B
,wehaveanemptymorphism
{
1
r
∅
}
)
={
}={
q
⊥
:⊥→⊥}
1
⊥
:
A
→
B
with
