Information Technology Reference
In-Depth Information
xyg
1
ba
2
ba
1
ca
4
cb
xy g
1
2
1
b
b
c
a
4
c b
Fig. 1.
Relation
p
D
0
from Example 2. The two boxes represent the multi-set
M
for the
two valuations
v
1
and
v
2
, respectively.
Definition 1. In particular, consider a formula
ϕ
=[
ω
x
z.ψ
](
y
;
g
), with
x
∈
V
,
d
]) fixes the values of the
variables in
g
because these are free in
ϕ
. The multi-set
M
is as follows. If
x
and a valuation
v
.Notethat
v
(and thus also
v
[
z
→
∈
g
,
d
then
M
(
a
)=
|{
∈
ϕ
z,v
|
d
j
=
a
}|
, for any
a
∈
D
,where
j
is the index of
x
in
z
.If
x
∈
g
,then
M
(
v
(
x
)) =
|
ϕ
z,v
|
and
M
(
a
)=0,forany
a
∈
D
\{
v
(
x
)
}
.
Example 2.
Let (
¯
, τ
) be a temporal structure over a signature with a ternary
predicate symbol
p
with
p
D
0
=
{
(1
,b,a
)
,
(2
,b,a
)
,
(1
,c,a
)
,
(4
,c,b
)
}
.Moreover,
let
ϕ
be the formula [
SUM
x
x,y.p
(
x,y,g
)](
s
;
g
)and
z
=(
x,y
). At time point 0,
for a valuation
v
1
with
v
1
(
g
)=
a
,wehave
D
p
(
x,y,g
)
z,v
1
=
{
(1
,b
)
,
(2
,b
)
,
(1
,c
)
}
and
M
=
{|
1
,
2
,
1
|}
. For a valuation
v
2
with
v
2
(
g
)=
b
,wehave
p
(
x,y,g
)
z,v
2
=
{
(4
,c
)
}
and
M
=
{|
4
|}
. Finally, for a valuation
v
3
with
v
3
(
g
)
/
∈{
a,b
}
,wehave
that
z,v
3
and
M
are empty. So the formula
ϕ
is only satisfied under
a valuation
v
with
v
(
s
) = 4 and either
v
(
g
)=
a
or
v
(
g
)=
b
. Indeed, we have
p
(
x,y,g
)
ϕ
=
{
(4
,a
)
,
(4
,b
)
}
. The tables in Figure 1 illustrate this example. We obtain
[
SUM
x
y,g.p
(
x,y,g
)](
s
;
x
)
=
{
(2
,
1)
,
(2
,
2)
,
(4
,
4)
}
,ifwegrouponthevariable
x
instead of
g
and
[
SUM
x
x,y,g.p
(
x,y,g
)](
s
)
=
{
(8)
}
, if we do not group.
Example 3.
Consider the formula
ϕ
=[
SUM
a
a.ψ
](
s
;
u
), where
ψ
is the formula
[0
,
31)
withdraw
(
u,a
). Let (
¯
D
, τ
) be a temporal structure with the relations
withdraw
D
0
=
and
withdraw
D
1
=
{
(Alice
,
9)
,
(Alice
,
3)
}
{
(Alice
,
3)
}
,andthe
(
¯
(
¯
D
,τ,
0)
D
,τ,
1)
=
timestamps
τ
0
=5and
τ
1
=8.Wehavethat
ψ
=
ψ
(
¯
(
¯
D
,τ,
0)
D
,τ,
1)
{
.
Our semantics ignores the fact that the tuple (Alice
,
3) occurs at both
time points 0 and 1. Note that the withdraw events do not have unique
identifiers in this example.
To account for multiple occurrences of an event, we can attach to each
event additional information to make it unique. For example, assume we
have a predicate symbol
ts
at hand that records the timestamp at each time
point, i.e.,
ts
D
i
=
(Alice
,
9)
,
(Alice
,
3)
}
and therefore
ϕ
=
ϕ
=
{
(12
,
Alice)
}
. For the formula
ϕ
=[
SUM
a
a.ψ
](
s
;
u
)
{
τ
i
}
,for
i
∈
N
(
¯
with
ψ
=
ϕ
D
,τ,
0)
=
[0
,
31)
withdraw
(
u,a
)
∧
ts
(
t
), we have that
{
(12
,
Alice)
}
(
¯
(
¯
ϕ
D
,τ,
1)
=
ψ
D
,τ,
0)
=
and
{
(15
,
Alice)
}
because
{
(Alice
,
9
,
5)
,
(Alice
,
3
,
5)
}
(
¯
ψ
D
,τ,
1)
while
. To further distin-
guish between withdraw events at time points with equal timestamps, we
would need additional information about the occurrence of an event, e.g.,
=
{
(Alice
,
9
,
5)
,
(Alice
,
3
,
5)
,
(Alice
,
3
,
8)
}
