Database Reference
In-Depth Information
1)
Associating variables with pairs
:
For each tuple
t
of a relation instance
r
in
D
and measure attribute
A
j
∈ M
R
,
we create the integer variable
z
t,A
j
whose domain is the same as
A
j
;
2)
Translating each aggregation function
tuple, measure attribute
χ
i
into sums of variables and constants:
Let
be the set of the ground substitutions of variables in x with con-
stants such that
Θ
(
ac
)
∀θ ∈ Θ
(
ac
)
φ
(
θ
x
)
is
true
on
D
. For every ground substitution
θ ∈ Θ
(
ac
)
and every
χ
i
, we denote as
T
χ
i
(
θ
)
the set of tuples involved in the
evaluation of
χ
i
w.r.t.
θ
, that is
T
χ
i
(
θ
)=
{
t
:
t
∈
r
i
∧
t
|
=
α
i
(
θ
y
i
)
}
, where
r
i
is
the instance in
D
of the relation scheme
R
i
in
χ
i
.
Then, for every ground substitution
θ ∈ Θ
(
ac
)
, we define the translation of
χ
i
w.r.t.
θ
as:
⎧
⎨
∑
t∈T
χ
i
(
θ
)
z
t,A
j
if
e
i
is the measure attribute
A
j
;
P
(
χ
i
,θ
)=
⎩
∑
t∈T
χ
i
(
θ
)
e
i
(
t
)
otherwise
.
3)
Translating the steady aggregate constraint ac into a set of linear inequalities:
The constraint
ac
is translated into the set
S
(
D,
ac
,
D
)
of linear inequalities
containing an inequality for every ground substitution in
Θ
(
ac
)
, that is
n
i
=
1
c
i
·P
(
χ
i
,θ
)
≤ K}
S
(
D,
ac
,
D
)=
{
θ∈Θ
(
ac
)
Finally, the system of linear inequalities
S
(
D,AC,
D
)
, which takes into account
all the aggregate constraints in
AC
, is then defined as
S
(
D,AC,
D
)=
S
(
D,
ac
,
D
)
ac
∈AC
, where
A
j
is the name of a measure attribute of tuple
t
, are associated with distinct integer
indexes. The set of these indexes will be denoted as
For the sake of simplicity, in the following we assume that the pairs
t
,
A
j
I
. Therefore, being
i
the integer
associated with the pair
, the variable
z
t,A
j
will be denoted as
z
i
.
Example 4.1.
In “Balance Sheets” example, we associate each pair
t
,
A
j
t
i
,
Value
with
the integer
i
, thus
I
=
{
1
,...,
20
}
. The translation of the (steady) aggregate con-
straints
κ
1
,κ
2
,κ
3
, introduced in Example 1.3 (and formalized in Examples 2.2
and 2.3), is as follows (we explicitly write equalities instead of inequalities):
⎧
⎨
z
2
+
z
3
=
z
4
κ
2
z
4
−
κ
3
z
1
−
z
5
+
z
6
+
z
7
=
z
8
z
8
=
z
9
z
9
=
z
10
κ
1
⎩
z
12
+
z
13
=
z
14
z
14
−
z
18
=
z
19
z
11
−
z
19
=
z
20
z
15
+
z
16
+
z
17
=
z
18
The set of inequalities
S
(
D,AC,
D
)
consists of all the inequalities above.
There is a one-to-one correspondence between every solution
s
of
S
(
D,AC,
D
)
and a repair
ρ
(
s
)
for
D
w.r.t.
D
and
AC
. In particular, the solution
s
corresponding
Search WWH ::
Custom Search