Relationale Datenbanken für die Topologie architektonischer Räume

Arch

DTop

Funktor

Forum Bauinformatik 2005

Zielsetzung: Grundlagen topologischer Datenhaltung

topologische Eigenschaften der Architektur für die Datenhaltung und Datenmodellierung ausnützen.

Allgemeines Bezugsmodell für topologische Informationen bereitstellen.

Nutzen:

Versionkontrolle bei kooperativer räumlicher Planung

Verbindung von räumlichen Modellen und Raum-Zeit-Modellen

Integration verschiedener Detaillierungsstufen wie etwa Skizze-Werkplan

Analyse topologischer Eigenschaften wie etwa Wegebeziehungen

Bauteildatenbanken

Beispiele topologischer Eigenschaften

Wand berührt „Räume“

Kante berührt Wände

Änderung berührt Alt - Neu

ℝ2

Der Topologie - Begriff

Strukturierung einer Menge X durch Definition von Umgebungen für ihre Punkte

Beispiel: zweidimensionaler reeller Vektorraum X := ℝ2:

Umgebung eines Punktes p ist:

Jede Scheibe um p mit Radius r > 0

p

Der Topologie - Begriff

ℝ2

Strukturierung einer Menge X durch Definition von Umgebungen für ihre Punkte

Beispiel: zweidimensionaler reeller Vektorraum X := ℝ2:

Umgebung eines Punktes p ist:

Jede Scheibe um p mit Radius r > 0

Jede Obermenge einer Umgebung von p

p

ℝ2

Der Topologie - Begriff

Strukturierung einer Menge X durch Definition von Umgebungen für ihre Punkte

Beispiel: zweidimensionaler reeller Vektorraum X := ℝ2:

Umgebung eines Punktes p ist:

Jede Scheibe um p mit Radius r > 0

Jede Obermenge einer Umgebung von p

X selbst

p

ℝ2

Der Topologie - Begriff

Strukturierung einer Menge X durch Definition von Umgebungen für ihre Punkte

Beispiel: zweidimensionaler reeller Vektorraum ℝ2:

Umgebung eines Punktes p sei:

Jede Scheibe um p mit Radius r > 0

Jede Obermenge einer solchen Scheibe

X selbst

offene Menge:

Teilmenge von X, die Umgebung
aller ihrer Punkte ist.

insbesondere ∅ und X.

Topologie:

Menge von offenen Teilmengen von X

Obiges Beispiel ergibt die „natürliche Topologie des ℝ2“

p

Topologiebegriff

Definition von Topologie

Für eine Menge X – die Punktmenge – Festlegung eines Mengensystems TX von Teilmengen von X mit folgenden Eigenschaften:

(T1) ∅∈TX un X∈TX

(T2) Wenn A, B∈TX dann auch A∩B ∈TX

(T3) Wenn S ⊆TX dann auch ∪A∈SA ∈TX

TX heißt dann eine Topologie für X.

(X, TX) heißt topologischer Raum.

Eine Menge A ∈TX heißt offen in (X, TX).

Beispiele:

(X,{∅,X}) – der sog. triviale Raum

(X, ℘(X)) – der indiskrete Raum (℘(X) ist Potenzmenge von X)

({0,1}, {∅,{0},{0,1}}) – der Sierpinski-Raum

stetige Abbildungen

Analysis: -ℇ-Kriterium:

Äquivalent: Bild eines Berührpunktes einer Menge berührt die Bildmenge.

Äquivalent: Urbild eines offenen Intervalls ist Vereinigung offener Intervalle

Topologie:

Verallgemeinerung: Urbild einer offenen Menge ist offen.

p

A

f(p)

f[A]

•

•

•

f

f

U

f-1[U]

Der Quotientenraum

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie
(die uns zu fein ist)

Der Quotientenraum

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie in

Eckpunkte

Der Quotientenraum

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie in

Eckpunkte --- Kanten

Der Quotientenraum

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie in

Eckpunkte --- Kanten --- Flächen

A

B

C

U

Der Quotientenraum

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie in

Eckpunkte --- Kanten --- Flächen

ergibt eine Topologie für die Komponenten, die Quotiententopologie

A

B

C

U

Der Quotientenraum: Beispiele für offene Mengen

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie in

Eckpunkte --- Kanten --- Flächen

ergibt eine Topologie für die Komponenten, die Quotiententopologie

A

B

C

U

Der Quotientenraum: Beispiele für offene Mengen

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie in

Eckpunkte --- Kanten --- Flächen

ergibt eine Topologie für die Komponenten, die Quotiententopologie

A

B

C

U

Der Quotientenraum: Beispiele für offene Mengen

Zerlegung von ℝn (hier n=2) mit seiner natürlichen Topologie in

Eckpunkte --- Kanten --- Flächen

ergibt eine Topologie für die Menge der Komponenten, die Quotiententopologie

A

B

C

U

Kompaktifizierung

S2

IR2

Der Aussenraum ist keine Zelle — er hat ein Loch

Lösung: Kompaktifizierung (z.B. zur Sphäre S2):

Postulat: Architektur und Topologie

Postulat 1 (Zerlegung des Irn):

Gegeben: ein kompakter Teilraum X des IRn für ein festes n

Architektur ist immer auch eine Zerlegung von X in endlich viele Teile

Den dadurch entstehenden topologischen Raum bezeichnen wir als eine architektonische Zerlegung des IRn.

Postulat 2 (Verfeinerung als Komplex):

Gegeben: eine architektonische Zerlegung.

Diese lässt sich zu einem Komplex verfeinern.

Dieser wiederum zu einem Zellenkomplex.

Diese Komplexe bezeichen wir als architektonische Komplexe.

Zellen-Komplexe

Aufbau aus orientierten Zellen:

0-Zellen (, , , , , , , )

















Zellen-Komplexe

Aufbau aus orientierten Zellen:

0-Zellen (, , , , , , , )

1-Zellen (a, b, c, d, e, f, g, h, i, k)

















a

b

k

h

i

g

c

d

e

f

U

•∞

Zellen-Komplexe

A

B

C

Aufbau aus orientierten Zellen:

0-Zellen (, , , , , , , )

1-Zellen (a, b, c, d, e, f, g, h, i, k)

2-Zellen (A, B, C, U)

Ergebnis: Kettenkomplex

ℤ{ A, B, C, U } ∂ ℤ{ a, b, ... , k } ∂ ℤ{ , , ... ,  }

mit ° = 0

















a

b

k

h

i

g

c

d

e

f

Durch Kompaktifi-

zierung wird U eben-

falls zur Zelle.

totale Randmatritzen in DketKomp*

U

A

B

C

















a

b

k

h

i

g

c

d

e

f

-1: gegenläufig

1: gleichsinnig

partielle Randmatritzen in DKetKomp

U

A

B

C

















a

b

k

h

i

g

c

d

e

f

Die partiellen Randmatritzen mit expliziter Null

U

A

B

C

















a

b

k

h

i

g

c

d

e

f

m

Dm,≠div

denn

 ∈ cl({m})

bzw.

„ berührt m“

Die Randrelation in DTop

U

A

B

C

















a

b

k

h

i

g

c

d

e

f

Die Randrelation in DTop

B

C

















a

b

c

d

e

f

g

h

A

k

i

Jeder endliche
topologische Raum
kann verlustfrei
durch eine derartige
Relation beschrieben
werden.

Offene Mengen in DTop

B

C

















a

b

c

d

e

f

g

h

A

k

i

Charakteristik:

Kein Pfeil geht
von aussen in die
Menge hinein.

Offene Mengen in DTop

B

C

















a

b

c

d

e

f

g

h

A

k

i

Charakteristik:

Kein Pfeil geht
von aussen in die
Menge hinein.

Offene Mengen in DTop

B

C

















a

b

c

d

e

f

g

h

A

k

i

Charakteristik:

Kein Pfeil geht
von aussen in die
Menge hinein.

Stetige Abbildungen in Dtop

B

C

















a

b

c

d

e

f

g

h

A

k

i

C'

'

'

'

'

h'

'

a'

d'

f'

g'

A'

k'

f

Stetigkeitskriterium:

f:(X, TR)  (Y, TS)

genau dann stetig in Top, wenn

a R b ⇒ f(a) S* f(b)

also

(f⊗f)[R] ⊆ S*

DTop die topologischen Datenbanken

Definition:

Seien (X, R) und (Y, S) Paare von endlichen Mengen X, Y mit jeweils einer Relation R auf X und S auf Y, die topologischen Datenbanken.

Seien f:(X, R)  (Y,S) Abbildungen f:XY mit der Eigenschaft a R b ⇒ f(a) S* f(b) für alle a,b in X, die stetigen Datenbankabbildungen.

Dann haben wir eine Kategorie DTop der topologischen Datenbanken mit den stetigen Datenbankabbildungen als Morphismen.

Satz:

DTop ist zur Kategorie der endlichen topologischen Räume äquivalent.

Folgerung:

Jeder endliche topologische Raum kann verlustfrei durch eine topologische Datenbank beschrieben werden.

Insbesondere ist das Schema topologischer Datenbanken denkbar einfach:

X

R

n

m

Stetigkeit und relationale Algebra

Satz:

Eine Abfragesprache, welche Stetigkeit in DTop entscheiden kann, kann für ein beliebiges Paar (a,b) ∈ X2 entscheiden, ob es in der transitive Hülle R+ einer Relation R⊆X2 liegt.

Beweis:

Erzeuge aus (a,b) die Menge Y:={a,b} und die Relation S:={(a,b)}.

Teste, ob die Injektion i : (Y,S)  (X, R) stetig ist.

Genau dann gilt S⊆R* und somit (a,b) ∈ R*.

Also kann a R* b entschieden werden.

Dann auch a R+ b mit (a≠b ∨ aRb) ∧ (a=b ∨ aR*b).

Folgerung:

Für viele Abfragen topologischer Eigenschaften ist die Berechnung der transitiven Hülle notwendig.

Z.B. durch start with ... join by ... - Abfragen in Oracle-SQL.

Beispiel: Raum-Zeit-GIS

Ausgangslage: Eine Familie von verschiedenen Polygon-„topologien“ einer Region zu jeweils verschiedenen Zeiten:

Zwei benachbarte Grundstücke A und B werden zusammengefasst.

Dabei wird A vergrößert und B verschwindet.

Ziel: Speichern dieses Ablaufs so dass

die für jeden Zeitpunkt geltenden Polygone abgefragt werden können

unveränderte Objekte nicht redundant gespeichert werden

die Identität von Objekt A trotz veränderter Geometrie erhalten bleibt

Anfangszustand

B

A

point_a

point_b

line_a_b

Table CELL

Table BOUNDARY

Anfangszustand: Nachbarn A und B

B

A

Ereignis: A kauft B

A

B

A

Endzustand: A ist größer

A

A

B

A

Raum-Zeit-Komplex

(time)

A

B

t=2

t=1

t=0

gemeinsame Grenze von t=0 bis t=1

Raum-Zeit-Komplex mit Darstellung in DKetKomp

(time)

A

B

t=2

t=1

t=0

gemeinsame Grenze von t=0 bis t=1

Volumen

Flächen

Kanten

Knoten

D3

D2

D1







x

y

t

Kettenkomplex:

Volumen (= Fläche × Zeitintervall)

A

B

Flächen (Fläche ×Zeitpunkt bzw. Kante × Zeitintervall)

Linien (Linie ×Zeitpunkt bzw Eckpunkt × Zeitintervall)

Punkte (Eckpunkt × Zeitpunkt)

Nur Veränderung speichern und Redundanz vermeiden

(time)

t=2

t=1

t=0

(time)

t=2

t=0

Diese

Änderung

speichern

Hier fand keine

Änderung statt.

Topologische Konstruktionen

Prinzip: Mengentheoretische Konstruktionen mit einer Topologie austatten.

Zu jeder Konstruktion wird eine Topologie gesucht, so dass gewisse charakteristische Abbildungen gerade noch stetig sind.

Beispiel: Kartesisches Produkt:

Gegeben: zwei topologische Räume (X, TX), (Y, TY ).

Topologie für X × Y:
gröbste Topologie TX×Y mit stetigen Projektionen
X:(X×Y, TX×Y)  (X, TX) und Y:(X×Y, TX×Y)  (Y, TY) (initial: links vom Pfeil)

Beispiel: Teilraum

Gegeben: ein topologischer Raum (X,T) und eine Menge A ⊆ X

Topologie T |A für A:
gröbste Topologie mit stetiger Inklusionsabbildung i:(A,T |A)  (X, T ) (initial: links vom Pfeil).

Beispiel: Quotientenraum

Gegeben: topologischer Raum (X,T) und Äquivalenzrelation ~ auf X.

Topologie T /~ für X /~:
feinste Topologie mit stetiger natürlicher Abb. :(X,TX)  (X /~,T /~) (final: rechts vom Pfeil)

Beispiel Teilraum

Definition:

Sei (X, R) eine top. Datenbank, A ⊆ X und (X,T) der zugehörige top. Raum.

Dann ist R+A2 eine Relation auf A
und (A, R+A2) eine top. Datenbank des Teilraums (A, T|A)

Anwendung: topologische Selektion

Gegeben top. Datenbank (X,R) mit Schema X[id], R[a:X.id,b:X.id]

dann ist mit A:= P(X) und A2 := aid(A)×bid(A)

P(X,R) := (A , R+∩A2)

die topologische Selektion.

Anmerkungen:

Eine relationale Algebra, mit der die topologische Selektion (oder allgemein die Initialtopologie einer Abbildung) ausgeführt werden kann muss die transitive Hülle R+ einer Relation R berechnen können.

Konstruktion der Finaltopologie (z.B. group by) geht ohne transitive Hülle.

Zusammenfassung

Einfache Datenbankschemata für alle topologischen Informationen:

statisches Datenbankschema bei beliebiger dynamischer Dimension

Folge: Auch 37-D-Topolgien sind kein Problem

Einzige Voraussetzungen

Endliche Anzahl von Elementen

transitive Hülle, falls die Dimension nicht beschränkt wird.

Topologische Eigenschaften DIME, QuadView, IfcTopologyRessources, etc. sind immer auf DTop oder DKetKomp reduzierbar.

Geeignet als formale Grundlage zur Integration von GIS und Gebäudemodellen.

Element

bd

n

m

:ℤ

dim:ℤ

n-D-Element

bd-n

n

:ℤ

(n-1)-D-Element

m

n

bd-1

:ℤ

m

(n-1)-D-Element

...

Historisches: Topolgie – Relationen (Alexandroff 1937)

Anmerkungen:

Zum Begriff: Diese «diskreten Räume» heißen heute «Alexandroff-Räume»

Zu (1): In DTop sagen wir p R* p' statt p' < p.

R*T bzw. „<“ heißt in der englischen Literatur oft „specialization preorder“.

Bereits 1937 war der Zusammenhang Topolgie und Relation bekannt:

Relationale Datenbanken für die Topologie architektonischer Räume

petra

1999-12-21T15:33:58