Database Reference
In-Depth Information
in
V
widerspiegelt. Die Knoten von
seien gerade die Elemente von
V
.Wirwerden
im Folgenden die Variablen aus
V
mit den entsprechenden Knoten identifizieren.
Ein naiver Ansatz zur Darstellung von Abhangigkeiten und Unabhangigkeiten
zwischen den Variablen in
V
ist der folgende:
G
•
Verbinde zwei Knoten genau dann, wenn die zugehorigen Variablen vonein-
ander abhangen.
Dies wirft jedoch eine Reihe von Fragen und Problemen auf: Was genau bedeutet
hier Abhangigkeit? Interpretiert man diesen Begriff in seiner vollen Allgemeinheit,
so wird man als Ergebnis einen Graphen erhalten, dessen Zusammenhangskompo-
nenten aus vollstandigen Teilgraphen bestehen. Besser ist es, die Abhangigkeiten
zu strukturieren und zwischen
direkter
und
indirekter Abhangigkeit
zu unterschei-
den. Direkt abhangige Variablen sollen auch direkte Nachbarn im Graphen sein,
wahrend indirekt abhangige Variablen durch Wege einer Lange
2 miteinander
verbunden sein sollen. Das Phanomen der indirekten Abhangigkeit lasst sich durch
das graphentheoretische Konzept der Separation prazisieren:
Fur disjunkte Teilmengen
A
,
B
,
C
≥
⊆
V
separiert
C
die Mengen
A
und
B
, in Zeichen
A
B
|
C
G
wenn jeder Weg zwischen einem Knoten in
A
und einem Knoten in
B
mindestens
einen Knoten aus
C
enthalt (vgl. Definition B.26 in Anhang B).
Proposition 13.1
Die Relation
auf den Teilmengen von
V
besitzt fur paarwei-
se disjunkte Teilmengen
A
,
B
,
C
,
D
⊆
V
in ungerichteten Graphen
G
die folgenden
Eigenschaften (da es sich um abstrakte Formulierungen handelt, lassen wir das Sub-
skript
G
G
weg):
•
Symmetrie:
A
B
|
C
gdw.
B
A
|
C
(13.1)
•
Zerlegbarkeit:
A
(
B
∪
D
)
|
C
impliziert
A
B
|
C
und
A
D
|
C
(13.2)
•
Schwache Vereinigung:
A
(
B
∪
D
)
|
C
impliziert
A
B
|
(
C
∪
D
)
(13.3)
•
Kontraktion:
A
B
|
C
und
A
D
|
(
C
∪
B
)
A
(
B
∪
D
)
|
C
(13.4)
impliziert
•
Schnitt:
A
B
|
(
C
∪
D
)
und
A
D
|
(
C
∪
B
)
impliziert
A
(
B
∪
D
)
|
C
(13.5)
