Information Technology Reference
In-Depth Information
and (
v
(
t
1
)
,...,v
(
t
n
))
∈
r
D
,where
v
is a valuation with
v
(
z
i
)=
a
i
, for all
i
∈{
r
(
t
1
,...,t
n
) is defined similarly.
In the following, let
C
be a set of constraints,
A
1
,...,k
}
¬
. Satisfaction for a constraint
⊆
D
m
,and
B
⊆
D
n
.The
selection
of
A
with respect to
C
is the
m
-ary relation
σ
C
(
A
):=
{
a
∈
A
|
a
satisfies all constraints in
C
}
.
The integer
i
is a
column
in
A
if 1
≤
i
≤
m
.Let
s
=(
s
1
,s
2
,...,s
k
) be a sequence
of
k
≥
0 columns in
A
.The
projection
of
A
on
s
is the
k
-ary relation
π
s
(
A
):=
(
a
s
1
,a
s
2
,...,a
s
k
)
k
(
a
1
,a
2
,...,a
m
)
A
.
∈
D
∈
Let
s
be a sequence of columns in
A
×
B
.The
join
and the
antijoin
of
A
and
B
with respect to
s
and
C
is defined as
A
s,C
B
:= (
π
s
◦
σ
C
)(
A
×
B
)
d
A
s,C
B
:=
A
\
(
A
s,C
B
)
.
Let
ω
be an operator in
Ω
,
G
asetof
k
0 columns in
A
,and
t
a constraint
term. The
ω
-aggregate
of
A
on
t
with grouping by
G
is the (
k
+ 1)-ary relation
ω
t
(
A
):=
(
b,a
)
a
=(
a
g
1
,a
g
2
,...,a
g
k
)
≥
π
g
(
A
)and
b
=
ω
(
M
a
)
.
Here
g
=(
g
1
,g
2
,...,g
k
) is the maximal subsequence of (1
,
2
,...,m
) such that
g
i
∈
∈
m−k
G
,for1
≤
i
≤
k
,and
M
a
:
D
→
N
is the finite multi-set
∈
D
,
where
h
is the maximal subsequence of (1
,
2
,...,m
) with no element in
G
and
D
:=
M
a
:=
(
π
h
◦
σ
{d≈t}∪D
)(
A
)
d
{
a
i
≈
z
g
i
|
1
≤
i
≤
k
}
.
3.3 Translation to Extended Relational Algebra
Let (
¯
(
¯
,τ,i
)
in
terms of the generalized relational algebra operators defined in Section 3.2.
Kind
(
FLX
)
.
This case is straightforward: for a predicate symbol
p
D
D
, τ
) be a temporal database,
i
∈
N
,and
ϕ
∈F
.Weexpress
ϕ
∈
R
f
of
arity
n
and pairwise distinct variables
x
1
,...,x
n
∈
V
,
(
¯
D
,τ,i
)
=
p
D
i
.
p
(
x
1
,...,x
n
)
Kind
(
RIG
∧
)
.
Let
ψ
∧
p
(
t
1
,...,t
n
)beaformulaofkind(
RIG
∧
). Then
D
,τ,i
)
=
σ
{p
(
θ
(
t
1
)
,...,θ
(
t
n
))
}
D
,τ,i
)
,
(
¯
(
¯
ψ
∧
p
(
t
1
,...,t
n
)
ψ
where the substitution
θ
:
fv
(
ψ
)
→{
z
1
,...,z
|fv
(
ψ
)
|
}
is given by
θ
(
x
)=
z
j
with
j
the index of
x
in
fv
(
ψ
). For instance, if
ϕ
∈F
is the formula
ψ
(
x,y
)
∧
(
¯
(
¯
(
x
D
,τ,i
)
.
Kind
(
GEN
S
)
.
Let
ψ
S
I
ψ
be a formula of kind (
GEN
S
) with
fv
(
ψ
)=(
y
1
,...,y
n
)
and
fv
(
ψ
)=(
y
1
,...,y
). Then
−
y
)
mod
2
≈
ϕ
D
,τ,i
)
=
σ
{
(
z
1
−z
2
)
mod
2
≈
0
}
ψ
0then
D
,τ,k
)
,
D
,τ,j
)
s,C
k
(
¯
(
¯
(
¯
ψ
S
I
ψ
D
,τ,i
)
=
ψ
ψ
j
∈{
i
|
i
≤
i, τ
i
−
τ
i
∈
I
}
∈{
j
+1
,...,i
}
where (a)
s
=(1
,...,n,n
+
i
1
,...,n
+
i
) with
i
j
such that (
i
1
,...,i
)isthe
maximal subsequence of (1
,...,
) with
y
i
j
/
∈
fv
(
ψ
)and(b)
C
=
{
z
j
≈
z
n
+
h
|
. For instance, for
fv
(
ψ
)=(
x,y,z
)and
fv
(
ψ
)=(
z,z
,x
), we have
s
=(1
,
2
,
3
,
5) and
C
=
y
j
=
y
h
,
1
≤
j
≤
n,
and 1
≤
h
≤
}
{
z
1
≈
z
6
,z
3
≈
z
4
}
.
