Database Reference
In-Depth Information
If
V
=
t
then
B
is an
exact
translation (i.e., side-effect free) for
−
t
. Other-
wise
t
.
The problem of translating general select-project-join (SPJ) view deletions to
underlying database deletions has been studied in [
11
] which gives an algorithm
that exploits lineage information to find an exact (i.e., side-effect free) deletion-to-
deletion translation whenever possible.
The lineage information is used as a starting point to enumerate all candidate
witnesses for a deletion. In [
8
], it was shown that this minimization is NP-hard
in general for monotonic select-project-join-union (SPJU) fragment of relational
queries.
B
is inexact, that is, with side-effects (or extra deletions)
E
=
V
\
Proposition 31
Let us consider a database mapping system
(
graph
)
G
=
(V
G
,E
G
)
with a current mapping-interpretation α
∗
:
Sch
(G)
→
DB
(
i
.
e
.,
from Definition
11
and Proposition
16
,
α
∗
∈
DB
Sch
(G)
)
which is a model of each database
schema in V
G
(
but not necessarily satisfies all inter-schema mappings in G
)
with
A
Int(G)
⊆
α
∗
(
=
A
) obtained by deleting some tuples in
A
and there exists
M
BA
={
Φ
}∈
E
G
,
where Φ is a normalized SOtgd formula
f
∀
x
1
q
B
1
(
x
1
)
r
A,
1
(
t
1
)
∧···∧∀
x
m
q
B
m
(
x
m
)
r
A,m
(
t
m
)
∃
⇒
⇒
with
M
BA
=
.
Let
(
here S is defined in the algorithm 'Cmp' in Definition
11
for the relational symbols
r
i
1
,...,r
i
k
in q
B
i
(
x
i
)
)
S
B
=
(V
i
,t
i
)
MakeOperads(
M
BA
)
={
v
1
·
q
B,
1
,...,v
m
·
q
B,m
,
1
r
∅
}:
B
→
A
V
i
=
q
B
i
(
x
i
)
α
∗
(
B
)
,t
i
=
Cmp(S,
d
1
,...,
d
k
)
|
|
d
m
∈
α(r
i
m
),
=
=∅
=
=
=
m
1
,...,k,
b
α(q
B,i
)(
d
1
,...,
d
k
)
,α(v
i
)(
b
)
,
for v
i
·
q
B,i
∈
MakeOperads(
M
BA
),
O(r
q
,r
A,i
)
q
B,i
∈
O(r
i
1
,...,r
i
k
,r
q
),v
i
∈
,
t
i
⊆
t
i
is a subset of tuples accepted to be consecutively deleted from the view V
i
of a
database
be a nonempty set where for each element (V
i
,t
i
)
∈S
B
,
1
≤
i
≤
n
=|S
B
|
.
Then the concatenation of updates transitions
(
in Definition
49
)
of the
instance-databases of
B
B
M
P
n
−
1
⇒
M
P
1
⇒
M
P
n
⇒
α
∗
===
α
n
===
α
n
−
1
···===
α
1
where P
i
is a sequential composition of
RA
arrows in the Application Plan consid-
ered as a program of categorial machine
M
RC
which executes the deleting of the
tuples t
i
⊆
OP
BA
⇒
M
,
will be simply denoted by α
∗
===
α
1
,
t
i
in
B
for each (V
i
,t
i
)
∈S
B
OP
where
M
BA
=
M
P
n
◦···◦
P
1
is associated to the inverted arrow w
.
r
.
t
.
M
BA
,
so that
α
1
(
with minimal side-effects
.
Hence
,
we extend these changes to the mapping-interpretation
(
a functor
)
α
1
:
B
) is the final updated database instance of
B
→
Sch
(G)
in V
G
,
α
1
(
α
∗
(
DB
such that for each
C
=
B
C
)
C
)
.