Database Reference
In-Depth Information
Table 1. Expansion rules
Rule
Description
if 1. 〈
C D
,
≥ 〉 ∈
,
n
( ,
x
is not indirectly
k
-blocked, and 2. {
x
〈 ≥ 〉 〈 ≥ 〉
C
,
,
n D
,
,
,
n
}
,
( )
x
³
then
( )
x
→
( )
x
∪ 〈 ≥ 〉 〈 ≥ 〉
{
C
,
,
n D
,
,
,
n
}
if 1. 〈
C D
,
≥ 〉 ∈
,
n
( ,
x
is not indirectly
k
-blocked, and 2. {
x
〈 ≥ 〉 〈 ≥ 〉 ∩
C
,
,
n D
,
,
,
n
}
( ) =
x
∅
³
′
, where
′
∈ 〈 ≥ 〉 〈 ≥ 〉
then
( )
x
→
( )
x
∪
{ }
C
C
{
C
,
,
n D
,
,
,
n
}
∃
≥
if 1. 〈∃
R C
.
,
≥ 〉
, (or 〈∃
n
T d
.
,
≥ 〉
, ) Î(
x
,
x
is not
k
-blocked. 2.
x
has no
R
n
n
³,
-neighbor(resp. no
T
³,
-neighbor)
y
s.t. 〈 ≥ 〉
C
, ,
n
n
(resp.〈 ≥ 〉
, , )Î(
y
,
then create a new node
y
with ( ,
d
n
x y
) = {
〈 ≥ 〉 and (
R
,
,
n
}
y
) = {
〈 ≥ 〉 (resp. with ( ,
C
,
,
n
}
x y
) = { ,
〈 ≥ 〉 and (
T
,
n
}
y
) = { ,
〈 ≥ 〉 ).
d
,
n
}
∀
≥
if 1. 〈∀
R C
.
,
≥ 〉
, (or 〈∀
n
T d
.
,
≥ 〉
, ) Î(
x
,
x
is not indirectly
k
-blocked. 2.
x
has an
R
≥
′
,
n
-neighbor
y
(resp. a
T
-neigh-
≥
′
,
y
, where
′
bor) with 〈 ≥ 〉
C
, , (resp. 〈 ≥ 〉
n
d
, , ) Ï (
n
n
= 1
− +
n
ε ,
then
(
y
)
→
(
y
)
∪ 〈 ≥ 〉 (resp.
{
C
,
,
n
}
(
y
)
→
(
y
)
∪ 〈 ≥ 〉 )
{ ,
d
,
n
}
∀
+
if 1. 〈∀
R C
.
,
≥ 〉 ∈
,
n
( with
Trans R
x
(
) ,
x
is not indirectly
k
-blocked, and 2.
x
has an
R
≥
′
,
-neighbor
y
with 〈∀
R C
.
,
≥ 〉 ∉
,
n
( ,
y
where
′
n
= 1
− +
n
ε ,
then
(
y
)
→
(
yy
∪ 〈∀
{
R C
.
,
≥ 〉
,
n
}
*
∀
′
+
if 1. 〈∀
S C
.
,
≥ 〉 ∈
,
n
( ,
x
is not indirectly
k
-blocked, and 2. there is some
R
, with
Trans R
x
(
) and
R
S
, 3.
x
has an
R
≥
′
,
( , where
′
-neighbor
y
with 〈∀
R C
.
,
≥ 〉 ∉
,
n
y
n
= 1
− +
n
ε ,
then
(
y
)
→
(
yy
∪ 〈∀
{
R C
.
,
≥ 〉
,
n
}
³
³
if 1. 〈≥
2 ,
S
≥ 〉 ∈
,
n
,
x
is not
k
-blocked, 2. #{
( )
x
∈
N
|
〈 ≥ 〉 ∈
R
,
,
n
( ,
x x
)} < 2
,
if
I
if
then introduce new nodes, s.t.
#
{
x
∈
N
|
〈 ≥ 〉 ∈
R
,
,
n
( ,
x x
)}
≥
2
if
I
if
≤
≥
if 1. 〈≤
1 ,
S
≥ 〉 ∈
,
n
,
x
is not indirectly
k
-blocked, 2. #{
( )
x
∈
N
|
〈 ≥ − + 〉 ε
R
,
,1
n
( ,
x x
)} > 1
and 3. there exist
x
l
if
I
if
and
x
k
, with no
x
» / , 4.
x
l
is neither a root node nor an ancestor of
x
k
.
x
l
k
then (i)
(
x
)
→
(
x
)
∪
(
x
)
(ii)
( ,
x x
)
→
( ,
x x
)
∪
( ,
x x
)
(iii) ( ,
x x
l
→ ∅ , (
)
x
l
→ ∅ (iv) set
x
)
» / for all
x
k
k
l
k
k
l
if
k
x
if
with
x
» / .
x
if
l
..
if 1. 〈≤
1 ,
S
≥ 〉 ∈
,
n
, 2. #{
( )
x
∈
N
|
〈 ≥ − + 〉 ε
R
,
,1
n
( ,
x x
)} > 1
and 3. there exist
x
l
and
x
k
, both root nodes, with no
if
I
if
» /
,
then 1.
x
x
l
k
′
〉
′
〉 ∅
′
〉
, i. if the edge
〈
x
k
,
x
does not exist, create it with
(
〈
x
,
x
) =
(
x
)
→
(
x
)
∪
(
x
)
2. For all edges 〈
x x
l
,
,
k
k
k
l
ii.
(
〈
x
,
x
′〉 → 〈
)
(
x
,
x
′〉 ∪ 〈
)
(
x x
,
′〉
)
does not exist, create it with
(
〈 ′
x x
k
,
〉 ∅
) =
. 3. For all edges 〈 ′
x x
, , i. if the edge 〈 ′
〉
x x
k
,
〉
,
k
k
l
ii.
〈
′
〉 → 〈
′
〉 ∪ 〈
′
x
l
Æ and remove all edges to/from
x
l
. 5. Set
′′
≈
x
/ for all
¢
x
with
(
x x
,
)
(
x x
,
)
(
x x
,
〉
)
. 4. Set (
) =
x
k
k
l
′′
≈
x
x
/ and set
x
» .
x
l
N
q
if 1.
C
D
Î and 2. {
〈¬ ≥ − + 〉 〈 ≥ 〉 ∩
C
,
,1
n
ε
,
D
,
,
n
}
( ) =
x
∅
for
n
∈
N
∪
,
′
for some
′
∈ 〈¬ ≥ − + 〉 〈 ≥ 〉
then
( )
x
→
( )
x
∪
{ }
C
C
{
C
,
,1
n
ε
,
D
,
,
n
}
.
Example 4.
Figure 1 shows a 2-complete and clash-free completion forest
for
, i.e.,
Î
ccf
2
(
,
)
where
o
= {
〈 ≥
C
,
, 0.8 ,
〉 〈∃
R C
.
,
≥
, 0.8 }
〉 ,
d
= { ,
〈 ≥ 〉 ,
R
d
,1 }
= {
〈 ≥
R
,
, 0.8 }
〉 ,
T
= { ,
〈 ≥ 〉 . In ,
o
1
T
,1 }
2
tree-blocks
T
o
4
2
, and
o
1
tree-blocks
o
5
. The
and
o
4
are 2-tree equivalent, and
o
1
is a 2-witness of
o
4
.
T
o
1
2
is directly blocked by
o
3
in
T
o
1
2
-tree, indicated by the dashed line.
node
o
6
in
T
o
4
