PHD Defense: Konsistenzprüfung von räumlichen semantischen Integritätsregeln

On the Consistency of Spatial

Semantic Integrity Constraints

Konsistenzprüfung von räumlichen

semantischen Integritätsregeln

Stephan Mäs

Stephan Mäs Konsistenzprüfung von räumlichen semantischen

Integritätsregeln 2 / 31

Problemstellung

Geographische Daten werden immer häufiger dezentral gehalten und mithilfe vernetzter Dienste ausgetauscht

Detailliertes Wissen über die jeweiligen Daten ist notwendig für deren Beurteilung und Nutzung

Modellbasierter Datenaustausch objektstrukturierter Geodaten

das Datenmodell wird zusammen mit den Daten bereitgestellt

semantische Integritätsregeln sind Teil dieser Datenmodelle und Teil der Qualitätsbeschreibung der Daten

Häufig mehrere tausend Integritätsregeln in einem Datenmodell

Prüfung der Integritätsregeln über hardcodierte Prüfroutinen

Management und Transfer der Integritätsregeln kaum möglich

Vergleich und Prüfung der internen Konsistenz der Regelsätze ist bisher nicht möglich

Methodik zum Vergleich und zur Konsistenzprüfung von räumlichen semantischen Integritätsregeln



Beispiel

Alle Auwälder liegen innerhalb (inside) genau einer Flussaue.

Alle Flussauen sind disjunkt (disjoint) von allen Atomkraftwerken.

Alle Auwälder sind disjunkt (disjoint) von allen Atomkraftwerken.



Beispiel






Beispiel




Alle Auwälder beinhalten (contains) ein Atomkraftwerk.



Gliederung

1. Wissenschaftliche Grundlagen

Definition von semantischen Integritätsregeln

Logisches Schließen auf Basis von räumlichen Relationen

2. Ansatz für das Logische Schließen mit semantischen Integritätsregeln

Trennung von Instanz- und Klassenrelationen

Komposition von Klassenrelationen

3. Anwendungsszenario Daten Integration

4. Zusammenfassung & Ausblick



Arten von Integritätsregeln

Domain Constraints

z.B. Einschränkungen von Attributwerten

Key and Relationship Constraints

z.B. Eindeutigkeit von Schlüsselattributen, Kardinalitätseinschränkungen

Semantic Integrity Constraints

schränken Relationen zwischen den Elementen des Datenmodells ein

spezifizieren wie die Semantik des Datenmodells im Datensatz umgesetzt / erzwungen wird

i.d.R. werden die eingeschränkten Relationen nicht explizit abgespeichert

Fokus der Arbeit liegt auf:

Semantischen Integritätsregeln welche auf binären räumlichen Relationen zwischen Objektklassen basieren



Räumliche semantische Integritätsregeln

Beispiele aus der natürlichen Sprache:

Topologische Einschränkungen:

Höhenlinien dürfen sich nicht mit Seen überschneiden.

Auwälder müssen innerhalb einer Flussaue liegen.

Orientierung / Richtungseinschränkungen:

Ein Hinterhof muss sich immer hinter einem Gebäude befinden.

Metrische Einschränkungen:

Eine Tankstelle muss mindestens 300m Abstand zu Schulen haben.

Untersuchungsziel:

Konsistenzprüfung von solchen Regelsätzen durch logisches Schließen.



Arten semantischer Integritätsregeln



Logisches Schließen mit räumlichen Relationen

Komposition von räumlichen Relationen

A B C

Finites Set von räumlichen Relationen

Komposition Beispiel: Explizites Wissen:

A berührt (meet) B

B beinhaltet (contains) C

Implizites Wissen:

A ist disjunkt (disjoint) von C



Komposition von räumlichen Relationen

Egenhofer, M. (1994): Deriving the Composition of Binary Topological Relations.



Constraint Satisfaction Problems

Herleitung von implizitem Wissen und Detektion von Inkonsistenzen und Redundanzen in Relationennetzen

Knoten repräsentieren Objekte

Kanten repräsentieren die (räumlichen) Relationen

Konsistenzprüfung der Relationen aller Objekttriple



Komposition Semantischer Integritätsregeln



???



Lösungsansatz

Aufteilung in 2 Ebenen:

getrennte Betrachtung der Kompositionen

von Instanzrelationen und

Kardinalitätseinschränkungen

Kombinierte

Kompositionen der

Klassenrelationen

Kompositionen der

Kardinalitätseinschränkungen

Klassenebene

Kompositionen der

Instanzrelationen

Instanzebene




k1

inside disjoint

k2

k3

f1

f2

f3

a1

a2

a3

a4




Instanzebene: inside(a,f ) ; disjoint(f ,k) disjoint(a .,k)

k1

inside disjoint

k2

k3

f1

f2

f3

a1

a2

a3

a4





k1

inside disjoint

k2

k3

f1

f2

f3

a1

a2

a3

a4

Klassenebene: Alle Auwälder stehen in Relation r1 zu genau einer Flussaue ;

Alle Flussauen stehen in Relation r2 zu allen Atomkraftwerken

Alle Auwälder stehen in Relation r3 zu allen Atomkraftwerken.





k1

inside disjoint

k2

k3

f1

f2

f3

a1

a2

a3

a4

Klassenebene: Alle Auwälder stehen in Relation r1 zu genau einer Flussaue ;

Alle Flussauen stehen in Relation r2 zu allen Atomkraftwerken

Alle Auwälder stehen in Relation r3 zu allen Atomkraftwerken.

Kombinierte Komposition der Klassenrelationen:



Berücksichtigte Kardinalitätsbedingungen

Links-Totalität:

Jedes a steht in einer Relation r zu mindestens einem b.

Rechts-Totalität:

Jedes b steht in einer Relation r zu mindestens einem a.

To

tal

Pa

rtic

ipa

tio

n

Rechts-Eindeutigkeit:

Kein a steht in einer Relation r zu mehr als einem b.

Links-Eindeutigkeit:

Kein b steht in einer Relation r zu mehr als einem a.

Ca

rdin

ali

ty

Ra

tio



Definition von Klassenrelationen

RLD (A,B)

RRD (A,B)

RLT (A,B)

RRT (A,B)

RLD RD LT (A,B)

RLD RD RT (A,B)

RLD LT RT (A,B)

RRD LT RT (A,B)

RLD RD LT RT (A,B)

17 Abstrakte Klassenrelationen

RLD RD (A,B)

RLD LT (A,B)

RLD RT (A,B)

RRD LT (A,B)

RRD RT (A,B)

RLT RT (A,B)


INSIDE RD LT (Auwälder, Flussauen)

links-total rechts-eindeutig

Sonderfall: RLT RT-all (A,B)

Rsome (A,B)






Prototypische Umsetzung



Anwendungsszenario: Datenintegration

Hochwasser-analyse

Integration möglich?

Brauchbarkeit?

Datenquelle 2 Datenquelle 1

Implizite Restriktionen?

Implizite Restriktionen?



Instanzebene: contains(fa,a); meet(a,f)

contains covers overlap(fa,f)

Alle Auwälder müssen an mindestens einem Fluss liegen (meet).

Alle Auwälder müssen innerhalb

(inside) einer Flussaue liegen.

Klassenebene:





overlapcoverscontains

overlapcoveredBy

insidemeetdisjoint






overlapcoveredBy

insidemeetdisjoint






overlapcoveredBy

insidemeetdisjoint

Widersprüche ?






overlapcoveredBy

insidemeetdisjoint

Widersprüche ?




Auflösung des Beispiels

Hochwasser-analyse

Integration ist möglich

Konsistenzprüfung notwendig


Implizite Restriktionen

vorhanden

Implizite Restriktionen

vorhanden



Zusammenfassung

Kategorisierung von semantischen Integritätsregeln

Konsistenzprüfung von räumlichen semantischen Integritätsregeln / Klassenrelationen

Formale Beschreibung der semantischen Integritätsregeln

Generische Methodik zur Erkennung von Konflikten und Redundanzen

Die entwickelte Methodik ermöglicht die Erkennung von:

impliziten Restriktionen

widersprüchlichen Integritätsregeln

semantische Heterogenitäten und Konflikte in verschiedenen Datenmodellen

redundanten Restriktionen

Anwendungsgebiete:

Qualitätssicherung

Management von semantischen Integritätsregeln

Datenintegration

• Heterogenitäten der Qualitätsanforderungen

• Qualitätsunzulänglichkeiten in Bezug auf eine bestimme Nutzung



Ausblick

Erweiterungsmöglichkeiten:

Vererbung von semantischen Integritätsregeln

Ternäre Relationen (a befindet sich zwischen b und c)

Erweiterung der Formalisierung (z.B. 0..2 als Kardinalität)

Berechnung von minimalen Regelsätzen

Minimierung des Rechenaufwandes bei der Qualitätssicherung

Räumliche Relationen und ihre Kompositionen

Relationen über mehrere räumliche Aspekte

Kognitive Plausibilität

Weitere Anwendungsgebiete:

Ontologien und konzeptionelle Datenmodellierung

Messung semantischer Ähnlichkeit (Semantic Similarity Measurement)

Education

PHD Defense: Konsistenzprüfung von räumlichen semantischen Integritätsregeln