Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 8 Kapitel 8 Satzmengenverwaltung

UniversitätKarlsruhe (TH)

© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 8

Kapitel 8

Satzmengenverwaltung

2


Gegenstand des Kapitels

Mengenorientiertes Datenmodell

Datenmodell

Dateien

Dateiverwaltung

Geräteschnittstelle

Anfragebearbeitung

Satzorientiertes Datenmodell

Speicherstruktur

Schneller Transport zwischen Haupt- und Hintergrundspeicher

Hauptspeicherseiten u. Segmente

Segment- u. Pufferverwaltung Bevorratung von Daten im Hauptspeicher (rechtzeitige Bereitstellung vor Benutzung)

Transparenter homogener Speicher Datentypen:

Seite = feste Anzahl von BytesSegment = var. Anzahl von Seiten

Operatoren:Anforderung/Freigabe von SeitenSegmente anlegen/öffnen/schließen

Datentypen:Block = feste Anzahl von BytesDatei = variable Anzahl v. Blöcken

Operatoren: Dateien anlegen/öffnen/schließen Lesen/Schreiben von Blöcken

Geräte-E/A

Satz- u. Satzmengenverwaltung

Satzzugriffsstrukturen

Zugriffsschicht

Vorschau auf zukünftig benötigte Daten

Vermeiden nicht aktuell benötigter Daten

Datentypen:Sätze und Satzmengen

Operatoren:Operatoren auf Sätzen

Datentypen:Satzmengen

Operatoren:Operatoren auf Mengen

Datentypen:phys. Zugriffsstrukturen auf Sätze

Operatoren:seq. Durchlauf, gezielte Suche

Optimaler Einsatz der logischen Ressourcen

Performanz

3


Kapitel 8.1Kapitel 8.1

Interne DateienInterne Dateien

4


Ausgangslage

Physische DB (satzorientiert)

Zugriffs-struktur

Kl.Physischer Datensatz

enthält0..1

enthält0..1

Physische DB (seitenorientiert

Segment Seite

repräsentiertdurch

▼

repräsentiertdurch

▼

1..

1

1..

1enthält

0..1enthält

0..1

Externe DB Ausprägung des externen Datenmodellsenthält

Menge externer Objekte, mengenorientierte Anfragesprache

Satzmenge, Zugriffspfad

Performanzwahrende Umsetzung

5


Ausgangslage

Physische DB (satzorientiert)

Zugriffs-struktur

Kl.Physischer Datensatz

enthält0..1

enthält0..1

Physische DB (seitenorientiert

Segment Seite

repräsentiertdurch

▼

repräsentiertdurch

▼

1..

1

1..

1enthält

0..1enthält

0..1

Externe DB Ausprägung des externen Datenmodellsenthält



Satzmenge, mengeninterne und -übergreifende Zugriffspfade

Direkte Zuordnung Abbildung

Materialisierung Logische Zugriffspfade

6


Lösungsansatz (2)

Materialisierung: Konstruktion einer Satzmenge, die gemeinsam genutzte Elemente der extern gesehenen Datenbasis widerspiegelt.

Logischer Zugriffspfad: Beschreibung der Reihenfolge, in der auf die Datensätze einer oder mehrerer interner Dateien zugegriffen wird. Daraus will man Hinweise auf die Gestaltung der

Zugriffsstrukturen gewinnen. Interne Datei: Materialisierte Satzmenge samt einem oder

mehreren logischen Zugriffspfaden.

7


Zusammenhänge

Interne DB Int. Datei Int. Datensatzenthält

0..1enthält

0..1

Physische DBZugriffs-struktur

Physischer Datensatz

repräsentiertdurch

▼

repräsentiertdurch

▼

1

?

1

1enthält

0..1enthält

0..1

Physische DB Segment Seite

repräsentiertdurch

▼

repräsentiertdurch

▼

1..

1

1..

1enthält

0..1enthält

0..1

Externe DB Instanzen des externen Datenmodellsenthält


Satzmenge, mengeninterne und -übergreifende Zugriffspfade


Gegenstand des Kapitels

8


Operatoren auf internen Dateien

OPEN/CLOSE Datei

FIND/FETCH Satz //wertbasiert, navigierend//

INSERT Satz

DELETE Satz

UPDATE Satz

SCAN //sequentieller Zugriff satzweise//

Hilfsoperator

SORT //temporäres Sortieren einer Datei//

9


Sort-Operator (1)

Externes Sortieren: Sortieren unter Zuhilfenahme des Hintergrundspeichers.

Vorherrschende Technik: Sortieren durch Mischen (Sort-merge).

10


Sort-Operator (2)

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 21

Andreas 24

Berta 77

Chris 7

Dieter 2

Dieter 4

Dieter 11

Elle 36

Gunter 42

Mario 9

Peer 43

Tamara 99

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 24

Dieter 4

Gunter 42

Berta 77

Chris 7

Elle 36

Dieter 2

Mario 9

Tamara 99

Andreas 21

Dieter 11

Peer 43

Andreas 24

Berta 77

Chris 7

Dieter 4

Elle 36

Gunter 42

Andreas 21

Dieter 2

Dieter 11

Mario 9

Peer 43

Tamara 99

partition internal sort merge merge

11


Sort-Operator (3)

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 21

Andreas 24

Berta 77

Chris 7

Dieter 2

Dieter 4

Dieter 11

Elle 36

Gunter 42

Mario 9

Peer 43

Tamara 99

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 24

Dieter 4

Gunter 42

Berta 77

Chris 7

Elle 36

Dieter 2

Mario 9

Tamara 99

Andreas 21

Dieter 11

Peer 43

Andreas 24

Berta 77

Chris 7

Dieter 4

Elle 36

Gunter 42

Andreas 21

Dieter 2

Dieter 11

Mario 9

Peer 43

Tamara 99

Sortierung von Stellvertretern zur

Einsparung von E/A!

Partition ~ Pufferkachelgröß

e

Allgemein: m-Wege-Mischen

Sequentieller Durchlauf: 1 Pufferkachel pro beteiligter Partition genügt (hier: 3)

12


Sort-Operator (3)

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 21

Andreas 24

Berta 77

Chris 7

Dieter 2

Dieter 4

Dieter 11

Elle 36

Gunter 42

Mario 9

Peer 43

Tamara 99

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 24

Dieter 4

Gunter 42

Berta 77

Chris 7

Elle 36

Dieter 2

Mario 9

Tamara 99

Andreas 21

Dieter 11

Peer 43

Andreas 24

Berta 77

Chris 7

Dieter 4

Elle 36

Gunter 42

Andreas 21

Dieter 2

Dieter 11

Mario 9

Peer 43

Tamara 99Partition ~ Pufferkachelgröß

e

Sequentieller Durchlauf: 1 Pufferkachel pro beteiligter Partition genügt

Alternativen: Nutzung der Pufferverwaltung (bequem, aber keine Kontrolle!) Eigener Puffer

13


Sort-Operator (4)

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 21

Andreas 24

Berta 77

Chris 7

Dieter 2

Dieter 4

Dieter 11

Elle 36

Gunter 42

Mario 9

Peer 43

Tamara 99

Gunter 42

Andreas 24

Dieter 4

Chris 7

Berta 77

Elle 36

Tamara 99

Dieter 2

Mario 9

Peer 43

Dieter 11

Andreas 21

Andreas 24

Dieter 4

Gunter 42

Berta 77

Chris 7

Elle 36

Dieter 2

Mario 9

Tamara 99

Andreas 21

Dieter 11

Peer 43

Andreas 24

Berta 77

Chris 7

Dieter 4

Elle 36

Gunter 42

Andreas 21

Dieter 2

Dieter 11

Mario 9

Peer 43

Tamara 99

n: Seitenzahl, nB Kachelzahl

E/A-Aufwand: 2n E/A- Aufwand: 2nlognB-1(n/nB) falls Seitengröße=Kachelgröße

14



Relationales DatenmodellRelationales Datenmodell

15


Datenmodell Tupel: Folge als zusammengehörig betrachteter atomarer

Datenelemente (Tupelkomponente). Die Zahl der Komponenten liegt für das Tupel fest, ihre Anordnung ist beliebig, da jede durch einen Selektor (Attribut) mit Wert aus einer Domäne identifiziert wird.

Relation: Menge im mathematischen Sinn aus gleichartigen Tupeln (Übereinstimmung in Attribut/Domäne-Paaren).

Schlüsselattribute (kurz: Schlüssel): Attribute(kombination), deren Werte(kombination) (ebenfalls: Schlüssel) zur eindeutigen Identifikation von Tupeln einer Relationen genügt.

Referenzielle Konsistenz von R1.X1 nach R2.X2. Die Werte unter R1.X1 kommen unter R2.X2 vor X2 Schlüssel von R2 X1 Fremdschlüssel in R1.

16


Kapitel 8.2.1Kapitel 8.2.1

MaterialisierungMaterialisierung

17


Schema-beschriebene Strukturrepräsentation:

N ist die Anzahl der Felder, Offsi ist der Offset innerhalb des Datensatzes, an der Wert von Feldi gespeichert ist.

Die Reihenfolge der Felder entspricht einer vorgegebenen Reihenfolge der Attribute.

Die Längen der Feldwerte können dynamisch wachsen und schrumpfen (führt zu Vergrößerung bzw. Verkleinerung des Datensatzes).

Feldwerte am Ende der Datensätze, die mit Nullwerten belegt sind, können weggelassen werden.

Struktur von Datensätzen (1)

L Feld1 ..... FeldNN Offs1 ..... OffsN

18


Selbstbeschreibende Strukturrepräsentation:

Ergänzung der vorhergehenden Struktur um Fi = Bezeichner des Felds (Atttribut) an der i-ten Position im Datensatz.

Die explizite Angabe der Feldnamen ermöglicht eine beliebige Reihenfolge bei der Anordnung der Feldwerte im Datensatz.

Felder mit Nullwerten können generell weggelassen werden.

Struktur von Datensätzen (2)

L Feld1 ..... FeldNN F1 Offs1 ..... FN OffsN

19


Beispiel-Relationen

OID GeoId Mat Value Color V1 V2…V7 V8

id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0

Material OID X Y Zid11 0.0 0.0 0.0id18 0.0 6.694 6.694id21 0.0 0.0 0.0id28 0.0 5.848 5.848id31 0.0 0.0 0.0id38 0.0 4.641 4.641…. …. …. ….

Vertex

idi sind Schlüssel

20


Direkte Materialisierung (1)

Externe DB Relation Tupel

Interne DB Int. Datei Int. Datensatz

repräsentiertdurch

▼

repräsentiertdurch

▼

1

1

1

1enthält

0..1

enthält0..1

enthält0..1

enthält0..1

Eineindeutige Zuordnung: N-ary Storage Model

21




id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0


Vertex

Cub_NSM OID Geold Mat Value Color V1 V2…V7 V8

id1 4711 id77 39.99 “red“ id11 ... id18 id2 5301 id77 19.95 “blue“ id21 ... id28 id3 8020 id99 89.90 “yellow“ id31 ... id38

22



Gut für relationale Anfragen, die viele Tupel selektieren und auf viele Attribute zugreifen.

Weitere Vorteile Einfaches Abbildungsschema von der externen auf die interne

Ebene. Anfragen und Änderungen auf Relationen können direkt auf

die Dateien übertragen werden.

Schlecht wenn Zugriff auf nur wenige Attribute erfolgt, da alle Attribute eines Tupels gelesen werden müssen.

Weitere Nachteile Je größer die Tupel werden, desto schlechter werden die

Möglichkeiten, eine gute Ballung der Datensätze zu erreichen.

23


Materialisierte Projektion (1)


Interne DB Datei Int. Datensatz

repräsentiertdurch

▼

repräsentiertdurch

▼

1

1..

1

1..enthält

0..1

enthält0..1

enthält0..1

enthält0..1

Die Menge der Attribute einer Relation wird in Teilmengen zerlegt, die jeweils einer Datei zugeordnet werden: Partial Decomposition Storage Model (P-DSM).

Jede Attribut-Teilmenge enthält den Identifikator der Tupel, damit die Tupel aus den internen Datensätzen rekonstruiert werden können.

24




id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0

Material OID X Y Zid11 0,0 0.0 0.0id18 0,0 6.694 6.694id21 0,0 0.0 0.0id28 0,0 5.848 5.848id31 0,0 0.0 0.0id38 0,0 4.641 4.641…. …. …. ….

Vertex

Cub_Topology OID V1 V2..V7 V8 id1 id11 … id18 id2 id21 … id28 id3 id31 ... id38

Cub_Props OID Geold Value Mat Color id1 4711 39.99 id77 “red” id2 5301 19.95 id77 “blue“ id3 8020 89.90 id99 “yellow“

25



Gut bei gemeinsamem Zugriff lediglich auf Teilmenge von Attributen: Vertikale Fragmentierung. Es kann sinnvoll sein, dass sich Teile eines Tupels

überlappen; dies führt allerdings zu Redundanz in den internen Datensätzen.

Weitere Vorteile Die Datensätze sind i.Allg. kurz, sie können daher gut geballt

werden. Große Attributwerte wie Blobs werden immer getrennt von

den übrigen Attributen gespeichert; sie „stören“ daher nicht bei der Ballung der übrigen Datensätze.

Schlecht wenn auf mehr oder sämtliche Attribute eines Tupels zugegriffen werden soll. Der Datensatz muss erst durch mehrere Joinoperationen

„zusammengebaut“ werden.

26



Extremfall: Für jedes Attribut wird eine eigene Datei definiert (Decomposition Storage Model, DSM ).

Vorteil 1: Mengenwertige Attribute: Mengenwertige Attribute können ohne redundante

Speicherung anderer Attribute gespeichert werden.

Die interne Struktur der Daten ist bei DSM unabhängig davon, ob ein Attribut mengenwertig ist oder nicht.

Vorteil 2: Unbekannte Attributwerte: Im DSM werden keine Nullwerte benötigt: Ein unbekannter

Attributwert wird einfach durch die Abwesenheit eines internen Datensatzes in der entsprechenden Attributdatei repräsentiert.

27



Vorteil 3:Schemaevolution: Das Datenbasis-Schema spiegelt die Verhältnisse der realen

Welt wider; Änderungen in der realen Welt können zu Anpassungen des Schemas führen (Schemaevolution).

Änderungen des Schemas können Anpassungen der externen DB erfordern.

Beispiele: Hinzufügen oder Entfernen von Attributen aus logischen Kollektionen.

Im DSM wird das Hinzufügen eines neuen Attributs durch das Erzeugen einer neuen, (zunächst) leeren Attributrelation realisiert.

Das Entfernen eines Attributs wird durch das Löschen der entsprechenden Attributrelation erreicht.

28




id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0


VertexCub_Value

OID Value id1 39,99 id2 19,95 id3 89,90

Cub_Mat OID Mat id1 id77 id2 id77 id3 id99

Cub_Color OID Color id1 “red“ id2 “blue“ id3 “yellow“

Cub_V1 OID V1 id1 id11 id2 id21 id3 id31

Cub_V8 OID V8 id1 id18 id2 id28 id3 id38

Cub_GeoId OID Geold id1 4711 id2 5301 id3 8020

...

29



Weitere Nachteile: Die Identifikatoren der Tupel sind redundant gespeichert

(einmal für jeden Attributwert). Da sich die Identifikatoren i.Allg. nicht ändern, führt ihre redundante Speicherung jedoch nur zu einem erhöhten Speicherplatzbedarf, nicht aber zu einem erhöhten Änderungsaufwand.

30


Materialisierte Selektion (1)



repräsentiertdurch

▼

repräsentiertdurch

▼

1

1..

1

1enthält

0..1

enthält0..1

enthält0..1

enthält0..1

Die Tupel der Relation werden auf mehrere Dateien aufgeteilt (horizontale Fragmentierung). Als Kriterium dienen Wertebereiche unter einer

Attributkombination.

31




id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0


VertexCub_Iron

Cub_Gold


id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28


id3 8020 id99 89.9 “yellow“ id31 …. id38

32



Gut für Range Queries.

Schlecht bei Zugriff auf sämtliche Datensätze der Relation: Vereinigungsoperation erforderlich.

33


Materialisierter Join (1)



repräsentiertdurch

▼

repräsentiertdurch

▼

2

1

2

1enthält

0..1

enthält0..1

enthält0..1

enthält0..1

Spezialfall: Die Tupel zweier Relationen werden gemäß Fremdschlüsselbedingung zusammengeführt. Zu einem Tupel der Relation mit Schlüssel werden alle Tupel

der zweiten Relation gruppiert, die diesen Schlüssel als Fremdschlüssel besitzen.

34


Materialisierter Join (2)


id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0


Vertex

Cub_Mat

OID GeoId Mat Name SpecWeight Value Color V1 V2…V7 V8

id1 4711 id77 “Iron” 7.86 39.99 “red“ id11 …. id18

id2 5301 id77 “Iron” 7.86 19.95 “blue“ id21 …. id28

id3 8020 id99 “Gold” 19.0 89.9 “yellow“ id31 …. id38

35



Logische ZugriffspfadeLogische Zugriffspfade

36


Navigierende Zugriffspfade

Anforderung Umsetzung Bewertung

LIST Bevorzugter, schneller, sequentieller Zugriff

Geballte Liste Effizienter Aufbau nur bei Ablage in Eingangsreihenfolge. Ansonsten schlechtes Änderungsverhalten.

POINTER-ARRAY

Flexible Reihenfolge

Aufgeprägter Index

Zwar volle Freiheit für die Organisation der Datei, aber 2 Zugriffe pro Satz.

CHAIN Nicht bevorzugter, sequentieller Zugriff

Meist Verkettung als eingebetteter Zugriffspfad

Änderungen an beliebiger Stelle, aber langsamer Zugriff.

37


Wertbasierte Zugriffspfade (1)


Primär-index

Eindeutiger Schlüssel: Exact Match Query schnell, Range Query anspruchslos

B*-Baum Keine Kontrolle über interne Datei.

Sekundär-index

Mehrdeutiger Schlüssel: Exact Match Query schnell, Range Query anspruchslos

B*-Baum Keine Kontrolle über interne Datei.

Cluster-index

Wie Primärindex, aber schnelle Range Query

B+-Baum Interne Datei als geballte Liste.

38


Umsetzung wertbasierter Zugriffspfade (1)

Cub_NSM OID Geold Mat Value Color V1 ... V8

tid1 id1 4711 id77 39.99 “red“ id11 ... id18 tid2 id2 5301 id77 19.95 “blue“ id21 ... id28 tid3 id3 8020 id99 89.90 “yellow“ id31 ... id38

GeoIdIndex Geold AdrCubFile

4711 tid1 5301 tid2 8020 tid3

Primärindex

MatIndex

Mat AdrCubFile

id77 tid1, tid2 id99 tid3

Sekundärindex

39


Wertbasierte Zugriffspfade (2)


Mehrattri-butindex

(Partial) Exact Match Query und Range Query auf mehr-dimensionalem Schlüssel

mehr-dimensionalerIndex

Wenn Schneiden von Einzelindexen gewünscht, nur solche Zugriffspfade angeben!

Hash Exact Match Query auf ein- oder mehrdeutigem Schlüssel

Hash-verfahren

Gestreute Speicherung der internen Datei.

40


Umsetzung wertbasierter Zugriffspfade (2)

Mehrdimensionaler Index über (GeoId, Value)

Cub_NSM OID Geold Mat Value Color V1 ... V8

tid1 id1 4711 id77 39.99 “red“ id11 ... id18 tid2 id2 5301 id77 19.95 “blue“ id21 ... id28 tid3 id3 8020 id99 89.90 “yellow“ id31 ... id38

41


Statt einen Equi-Join zu materialisieren, kann man einen speziellen Zugriffspfad (Gruppierung) anlegen. Umsetzung 1: Über navigierenden Zugriffspfad

Umsetzung 2: Über einen speziellen Index, z.B. CH-Baum. Dort können auch mehr als 2 Relationen einbezogen werden,

sofern es sich um denselben Schlüssel handelt.

Join-unterstützender Zugriffspfad

42


Navigierender Zugriffspfad für Join (1)

Schlüssel-Satz

Fremdschlüssel-Satz 1

LIST:




43



Schlüssel-Satz

CHAIN:




44



Schlüssel-Satz

POINTERARRAY:




45


Basisstruktur: B+-Baum. Sortierte geballte Datei mit speziellem Format.

Aufbau der Datensätze auf der Schicht der Satzmengenverwaltung.

Falls eine Datenseite größer als die Seitengröße wird, werden zusätzliche Seiten angefordert und in Form einer Überlaufseiten-Liste verwaltet.

CH-Baum (1)

Länge d.

Records

Schlüs-selwert

Anzahl Dateien

Id von Datei 1

Off- set 1

…

Id von Datei

n

Off- set n

Datensätze zu Datei 1

…

Datensätze zu Datei n

Pointer ArrayGemeinsamer Schlüsselwert

Datensätze nach Dateizugehörigkeit

gruppiert

46


CH-Baum (2)

Nicht-Blattseiten wie im B-Baum

10 2 F1 F3 id1 id8

30 3 F1 F2 id2 id9id7F3

70 2 F1 F4 id3 id12

90 2 F2 F4 id11id4

40 1 F2 id6

50 2 F2 F3 id10id5

30 3 F1 F2 id2 id9id7F3

Detaildarstellung eines Blattseiten-records

Blattseite (ohne Längenfeld)

Blattseiten-Records

CubIndexGeo VolumeId4 90Id5 50Id6 40Id7 30

GeoIndexGeo VolumeId1 10Id2 30Id3 70

CylIndexGeo VolumeId8 10Id9 30Id10 50

PipeIndexGeo VolumeId11 90Id12 70

F1 F2F3 F4

Beispiel

47



Spezielle Scan-OperatorenSpezielle Scan-Operatoren

48


Scan-Operator (1)

SCAN: Tupelweises Aufsuchen, aus externer Sicht definiert, gemäß einer vorgeschriebenen Zugriffsreihenfolge.

4 Grundtypen: Relationen-Scan (Full-table scan) zum Aufsuchen aller Sätze

einer Relation. Index-Scan zum Aufsuchen von Sätzen in einer

wertabhängigen Reihenfolge. Link-Scan zum Aufsuchen von Sätzen in einer

gruppierungsbedingten Reihenfolge. k-d-Scan zum Aufsuchen von Sätzen in einem k-

dimensionalen Datenraum.

Die Implementierung hängt jeweils von den angelegten logischen Zugriffspfaden und deren Umsetzung auf der Zugriffsschicht ab.

49


Scan-Operator (2)

Abfolge: open scan:

Richte Scan-Kontrollblock ein.

Positioniere auf erstes Tupel gemäß Startbedingung.

fetch tuple: Beschaffe Tupel gemäß Position und schalte Position gemäß

Suchrichtung weiter.

close scan: Aufräumen.

Startbedingung

Stoppbedingung

Suchrichtung

Suchbedingung

50


Relationen-Scan

Es werden alle Tupel aufgesucht. Sehr effizient bei geballter Speicherung. Sehr ineffizient bei gestreuter Speicherung (Verkettung,

Hash). Stets 2 Seitenzugriffe bei Pointer array.

Falls Suchbedingung angegeben, wird sie auf jeden aufgesuchten Datensatz angewendet und über die Weitergabe entschieden.

Startbedingung beginof Cuboid

Stoppbedingung endof Cuboid

Suchrichtung forward

Suchbedingung all | Color=“red“

51


Index-Scan (1)

Es werden alle Tupel zwischen Start- und Stoppbedingung aufgesucht (Range Query). Sehr effizient bei Clusterindex. 2 Seitenzugriffe bei allen anderen wertbasierten Indexen. In allen anderen Fällen entartet Scan in einen Relationen-

Scan.

Falls Suchbedingung angegeben, wird sie auf jedes aufgesuchte Tupel angewendet und über die Weitergabe entschieden.

Startbedingung Cuboid ≥ 20

Stoppbedingung Cuboid > 75


Suchbedingung Color=“red“

52


Index-Scan (2)

Beispiel: Clusterindex (B+-Baum):

10 ...

25 45 65 75

20 ... 30 ... 40 ... 50 ... 60 ... 70 ... 80 ... 90 ...

Startbedingung Cuboid ≥ 20

Stoppbedingung Cuboid > 75



53


Link-Scan (1)

Es werden alle Schlüssel-Datensätze zwischen Start- und Stoppbedingung aufgesucht. Weiterbehandlung nur, falls Suchbedingung erfüllt ist.

Für jeden Schlüssel-Datensatz werden alle zugehörigen Fremdschlüssel-Datensätze aufgesucht Geschachtelter Scan. Weitergabe nur, falls Suchbedingung erfüllt ist.

Effizienz hängt offensichtlich von der Implementierung beider Satzmengen (evtl. einschl. log. Zugriffspfad) ab.

Startbedingung beginof Material

Stoppbedingung endof Material

Suchrichtung forward forward

Suchbedingung Name=„Iron“ GeoId ≥ 3000

54


Link-Scan (2)


id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0

Material

55


k-d-Scan

Annahme: Für Cub_NSM existiert mehrdimensionaler Index.

Startbedingung liefert Einstiegspunkt. Weiterbehandlung mit geschachteltem Scan, hängt im

Detail (z.B. Anordnung der Scans) von Implementierung ab. Typisches Optimierungsproblem.

Startbedingung GeoId ≥ 3000 Value ≥ 20.00

Stoppbedingung GeoId > 8000 Value > 60.00

Suchrichtung forward forward


56



Objektorientiertes DatenmodellObjektorientiertes Datenmodell

57


Beispiel

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9

Name: “Iron“SpecWght: 7.86

Name: “Gold“SpecWght: 19.0

id99

Name: “Alu“ SpecWght: 3.02

id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121

Id: 4711Geo: {id1,id2}

id120


id122

Name: “Gripper“Price: 283.00Cmps:{id120,id121,id122}Image: ...

Name: “Bolt“Price: 78.05Cmps: {id140}Image: ...

id102

Name: “Wheel“Price: 95.00Cmps: {id130,id131}Image: ...

id101

id100

Material id110 id1

Product

Herausforderungen:Große Zahl von ObjektenStarke Verzeigerung

58



Materialisierung von ObjektenMaterialisierung von Objekten

59


Materialisierungsstrategie

Objekte des selben Typs bilden Satzmenge.

Materialisierung dieser Satzmengen nach den selben Strategien wie bei Relationen.

60


Objekte mit großen Anteilen (1)

BLOB: Binary Large Object für vom DBMS nicht zu interpretierende Objekte (Bilder, Video, Audio).

CLOB: Character Large Object für lange Texte.

NCLOB: National Character Large Object für Unicode-Texte.

class Product {Name: string;Price: float;Cmps: setof Part;Image: BLOB

}

61


Objekte mit großen Anteilen (2)

DB2

.

.

.

.

DB2 File Manager

Datei 1Datei 2

Datei 3 Datei 4

SQL Anfrage Datei-AnfrageAutorisierungsprüfung

Üblich: vom DBMS getrennte (externe) Dateien. Beispiel: Data Links von IBM DB2 für die Domäne BLOB.

Zwei autonome Systeme. Satzmengenverwaltung so erweitert, dass die

Zusammenhänge berücksichtigt werden.

62


Materialisierung der Vererbung (1)

Typhierarchie: GeoPrimitive

CylinderCuboid

Pipe

{}

{id1,id2,id´3}{id4,id5 }

{id6 ,id7}

class GeoPrimitive {GeoId: string;Mat: Material;Color: string;Value: float

}

class Cuboid extends GeoPrimitive {V1, ..., V8: Vertex

}

class Cylinder extends GeoPrimitive {Center1, Center2: VertexRadius: float

}

class Pipe extends Cylinder {InnerRadius: float

}

63



Home Class Model Direkte Materialisierung jedes Typs als interne Datei derart,

dass sie alle Attribute einschließlich der ererbten enthält. Ein Objekt wird in genau 1 Datensatz abgebildet in der

Datei, die seine sämtlichen Attribute enthält (Verwandtschaft mit horizontaler Fragmentierung!).

Beispiel: Objekte, die als spezialisiertesten Typ Cylinder besitzen, werden nur in der Datei zu dem Typ Cylinder gespeichert, nicht jedoch in der Datei zu dem Obertyp GeoPrimitive.

64


Materialisierung der Vererbung (2)CubFile OID Geold Mat Value Color V1 … V8

id1 4711 id77 39.99 “red“ id11 … id18 id2 5301 id77 19.95 “blue“ id21 … id28 id3 8020 id99 89.90 “yellow“ id31 … id38

CylFile OID Geold Mat Value Color Center1 Center2 Radius

id4 7030 id88 20.04 “black“ id41 id42 30.0 id5 4132 id99 59.40 “yellow“ id51 id52 12.3

PipeFile OID Geold Mat Value Color Center1 Center2 Radius InnerRadius

id6 3423 id77 18.44 “red“ id61 id62 43.2 13.2 id7 5002 id99 45.79 “yellow“ id71 id72 10.1 8.9

GeoPrimitive

CylinderCuboid

Pipe

{id1,id2,id

´3}

{}

{id4,id5

}

{id6 ,id

7}

65



Split Instance Model Jedes Objekt eines Typs wird mehrfach gespeichert: einmal

in der Datei, die dem spezialisiertesten Typ des Objektes zugeordnet ist, und zusätzlich in den Dateien, die den Obertypen zugeordnet sind.

Die Objekte werden dabei vertikal entsprechend der Vererbungshierarchie fragmentiert: Die Datei für einen Typ enthält nur die Attribute, die in dem Typ definiert sind, aber keine geerbten Attribute.

Eine Datei zu einem Typ t enthält beim Split Instance Model somit Datensätze zu Objekten, die als spezialisiertesten Typ t oder einen seiner Untertypen besitzen.

66



GeoFile OID Geold Mat Value Color

id1 4711 id77 39.99 “red“

id2 5301 id77 19.95 “blue“

id3 8020 id99 89.90 “yellow“

id4 7030 id88 20.04 “black“

id5 4132 id99 59.40 “yellow“

id6 3423 id77 18.44 “red“

id7 5002 id99 45.79 “yellow“

CubFile OID V1 ... V8

id1 id11 ... id18

id2 id21 ... id28

id3 id31 ... id38

CylFile OID Center1 Center2 Radius

id4 id41 id42 30.0

id5 id51 id52 12.3

id6 id61 id62 43.2

id7 id71 id72 10.1

PipeFile OID InnerRadius id6 13.2 id7 8.9

GeoPrimitive

CylinderCuboid

Pipe

{id1,id2,id

´3}

{}

{id4,id5

}

{id6 ,id

7}

67



Repeat Class Model

Kombination von Home Class und Split Instance Model: Jedes Objekt eines Typs wird mehrfach gespeichert: einmal

in der Datei, die dem direkten Typ des Objektes zugeordnet ist, und zusätzlich in den Dateien, die den Obertypen zugeordnet sind.

In jeder Datei sind aber alle Attribute ihres Typs (inklusive aller ererbten) enthalten.

Das Repeat Class Model führt somit zu einer redundanten Speicherung von geerbten Attributen.

68



Logische Zugriffspfade für Verzeigerung: Logische Zugriffspfade für Verzeigerung: Pfad-IndexePfad-Indexe

69


Pfade

Modell: Pfade in objektorientierten Datenbanken Eine Objektbank enthält explizite Verweise zwischen

Objekten: Zwischen einem Objekt o1 und einem Objekt o2 besteht eine Referenz (von o1 nach o2), wenn o1 den Identifikator von o2 enthält.

Eine Objektbank bildet somit einen gerichteten Graphen beliebiger Struktur.

Ein Pfad ist eine Kette von Objekten, die über Referenzen miteinander verbunden sind.

Ein Pfadausdruck beschreibt die an der Kette beteiligten Attribute. Linearer Pfadausdruck: Keines der beteiligten Attribute ist

mengenwertig. Mengenwertiger Pfadausdruck: Mindestens eines der

beteiligten Attribute ist mengenwertig.

70


Linearer Pfadausdruck

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9



id99


id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121


id120


id122


id100

Material id110 id1

Productselect cfrom c in Cuboidwhere c.Mat.Name = “Gold“


id102


id101

id3

id7

id8 id99

id99

id99

71


Mengenwertiger Pfadausdruck

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9



id99


id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121


id120


id122



id102


id101

id100

Material id110 id1

Product

select [Name: p.Cmps.Geo.Mat.Name]from p in Productwhere p.Name = “Gripper“

id121

id122

id1

id2

id3

id4

id5 id77

id77

id99

id77

id100

id77

id120

72


Pfadausdrücke

Typisierung:

P= t0.A1..Ai..An

t1

ti

tn

R0

R1

R2

v

A1

A2

ov

t2

t0

t1

Beispiel:

P=Product.Cmps.Geo.Mat.Name

Part

Cuboid

Material

string

73


Pfadindexe

Anwendungen navigieren durch den Graphen, indem sie gemäß eines Pfadausdrucks Pfade durchlaufen und dabei auf die entlang des Pfades liegenden Objekte zugreifen.

Grundidee:

Häufig durchlaufene Pfadausdrücke werden vorausberechnet (materialisiert) und als Dateien (Access Support Relations, ASRs) gespeichert.

74


Binäre Pfadrelationen (1)

ti-1.Ai

OIDti-1 OIDti ... ... id1 id2

... ...

ti-1.Ai

OIDti-1 OIDti id1 id3 id1 id4

... ...

Fall 1: Fall2:

id1 id2 id1

id3

id4

75


Beispiel-Objektbank

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9



id99


id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121


id120


id122



id102


id101

id100

Material id110 id1

Product

Product.Cmps

OIDproduct OIDpart

id100 id120

id100 id121

id100 id122

id101 id130

id101 id131

id102 id140

Part.Geo

OIDpart OIDcuboid

id120 id1

id120 id2

id121 id3

id122 id4

id122 id5

id130 id6

id131 id7

id150 id9

Cuboid.Mat

OIDCuboid OIDMaterial

id1 id77

id2 id77

id3 id99

id4 id77

id5 id77

id6 id88

id7 id99

id8 id99

Material.Name

OIDMaterial string id77 “Iron“ id88 “Alu“ id99 “Gold"

76


Access Support Relations (1)

Formale Definition von ASRs

ASRs werden über den Join mehrerer binärer Pfadrelationen definiert.

77



Vollständige ASR-Extension Die vollständige Extension enthält alle vollständigen und

partiellen Pfade. Definition:

t0.A1..Ai..Anfull := t0.A1 tn-1.An Partielle Pfade beginnen und/oder enden daher mit NULL-

Werten.

Exkurs: Äußerer Join (full outer join)

LA B Ca1 b1 c1

a2 b2 c2

ResultA B C D Ea1 b2 c2 - -- - c3 d2 e2

a1 b1 c1 d1 e1

=

RC D Ec1 d1 e1

c3 d2 e2

⋈ ⋈

78


Beispiel-Objektbank

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9



id99


id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121


id120


id122



id102


id101

id100

Material id110 id1

Product

Product.Cmps

OIDproduct OIDpart

id100 id120

id100 id121

id100 id122

id101 id130

id101 id131

id102 id140

Part.Geo

OIDpart OIDcuboid

id120 id1

id120 id2

id121 id3

id122 id4

id122 id5

id130 id6

id131 id7

id150 id9

Cuboid.Mat

OIDCuboid OIDMaterial

id1 id77

id2 id77

id3 id99

id4 id77

id5 id77

id6 id88

id7 id99

id8 id99

Material.Name

OIDMaterial string id77 “Iron“ id88 “Alu“ id99 “Gold"

Product.Cmps.Geo.Mat.Namefull OIDProduct OIDPart OIDCuboid OIDMaterial string

id100 id120 id1 id77 “Iron“ id100 id120 id2 id77 “Iron“ id100 id121 id3 id99 “Gold“ id100 id122 id4 id77 “Iron“ id100 id122 id5 id77 “Iron“ id101 id130 id6 id88 “Alu“ id101 id131 id7 id99 “Gold“ id102 id140 - - -

- id150 id9 - - - - id8 id99 “Gold“

79



Links-Vollständige ASR-Extension Die linksvollständige Extension enthält Pfade, die in der

ersten Spalte der Access Support Relation beginnen und in einer beliebigen Spalte enden.

Definition:

t0.A1..Ai..Anleft := t0.A1 tn-1.An

Exkurs: Linker äußerer Join (left outer join)

LA B Ca1 b1 c1

a2 b2 c2

=

RC D Ec1 d1 e1

c3 d2 e2

Result A B C D E a1 b1 c1 d1 e1

a2 b2 c2 - -

⋈ ⋈

80


Beispiel-Objektbank



- id150 id9 - - - - id8 id99 “Gold“

Product.Cmps.Geo.Mat.Nameleft OIDProduct OIDPart OIDCuboid OIDMaterial string


81



Rechts-Vollständige ASR-Extension

Die rechts-vollständige Extension enthält Pfade, die in einer beliebigen Spalte beginnen und in der letzten Spalte enden.

Definition:

t0.A1..Ai..Anright := t0.A1 tn-1.An

Exkurs: Rechter äußerer Join (right outer join)L

A B Ca1 b1 c1

a2 b2 c2

=

RC D Ec1 d1 e1

c3 d2 e2

ResultA B C D Ea1 b1 c1 d1 e1

- - c3 d2 e2

⋈ ⋈

82


Beispiel-Objektbank



- id150 id9 - - - - id8 id99 “Gold“

Product.Cmps.Geo.Mat.Nameright OIDProduct OIDPart OIDCuboid OIDMaterial string

id100 id120 id1 id77 “Iron“ id100 id120 id2 id77 “Iron“ id100 id121 id3 id99 “Gold“ id100 id122 id4 id77 “Iron“ id100 id122 id5 id77 “Iron“ id101 id130 id6 id88 “Alu“ id101 id131 id7 id99 “Gold“

- - id8 id99 “Gold“

83



Kanonische ASR-Extension

Die kanonische Extension enthält nur vollständige Pfade, d.h., Pfade, die in der ersten Spalte der Access Support Relation beginnen und bis zur letzten Spalte reichen.

Definition:

t0.A1..Ai..Ancan := t0.A1 ⋈ ⋈ tn-1.An

Exkurs: Equi-JoinL

A B Ca1 b1 c1

a2 b2 c2

RC D Ec1 d1 e1

c3 d2 e2

ResultA B C D Ea1 b1 c1 d1 e1

=

84


Beispiel-Objektbank



- id150 id9 - - - - id8 id99 “Gold“

Product.Cmps.Geo.Mat.Namecan OIDProduct OIDPart OIDCuboid OIDMaterial string

id100 id120 id1 id77 “Iron“ id100 id120 id2 id77 “Iron“ id100 id121 id3 id99 “Gold“ id100 id122 id4 id77 “Iron“ id100 id122 id5 id77 “Iron“ id101 id130 id6 id88 “Alu“ id101 id131 id7 id99 “Gold“

85


Anfragebearbeitung mit ASR

Anfragearten: Rückwärts-Anfrage

select ofrom o in ti

where predicate (o.Ai+1.···.Aj) Vorwärts-Anfrage

select o.Ai+1.···.Aj

from o in ti

where predicate (o)

86


Rückwärts-Anfrage

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9



id99


id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121


id120


id122



id102


id101

id100

Material id110 id1

Product

select cfrom c in Cuboidwhere c.Mat.Name = “Gold“

•Anfrageergebnis: {id3,id7,id8}•Die Anfrage kann nur auf den Extensionen

Product.Cmps.Geo.Mat.Nameright Product.Cmps.Geo.Mat.Namefull

bearbeitet werden.

87


Vorwärts-Anfrage

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9



id99


id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121


id120


id122



id102


id101

id100

Material id110 id1

Product

select q.Geofrom q in Partwhere true

• Anfrageergebnis: {id1,id2,id3,id4,id5,id6,id7,id9}

• Die Anfrage kann nur auf der ExtensionProduct.Cmps.Geo.Mat.Namefull

bearbeitet werden.

88


Zugriff auf Access Support Relations (1)

Unterstützung von Vorwärtsanfragen der Formselect = o.Ai+1.···.Aj

from o in ti

where predicate (o)

Es wird ein zusätzlicher Zugriffspfad auf der i-ten Spalte der ASR t0.A1.···.An benötigt.

Da alle Spalten (bis auf die letzte) OIDs enthalten, und auf OIDs i.Allg. keine Range Queries, sondern nur Exact Match Queries gestellt werden, empfiehlt sich für den Zugriffspfad der Einsatz einer Hashtabelle.

89


Zugriff auf Access Support Relations (2)

Unterstützung von Rückwärtsanfragen der Formselect o from o in ti where predicate (o.Ai+1.···.Aj)

Es wird ein zusätzlicher Index auf der j-ten Spalte benötigt. Falls j=n und die letzte Spalte nicht oid-wertig ist, dann können

Range Queries vorkommen. In diesem Fall sollte für den Zusatzindex ein B+-Baum eingesetzt werden.

Falls die j-te Spalte oid-wertig ist, sollte eine Hashtabelle eingesetzt werden.

In wie vielen physischen Datenstrukturen insgesamt eine ASR gespeichert wird, hängt von dem Anfrageprofil ab (Abwägung zwischen Unterstützung von Anfragen und Änderungsaufwand).

90



Kombinierte Materialisierung von Objekten Kombinierte Materialisierung von Objekten und Zugriffspfaden und Zugriffspfaden

91


Gruppierte ObjekteAusgangspunkt: Vermeiden von häufig durchlaufenen

PfadenAnsatz: Composite Object oder Complex Object: Gruppierung

eines Objektes gemeinsam mit seinen durch vorgegebene Beziehungen verbundenen (Unter-)Objekten.

Vorteile: Durch Ballen der Bestandteile eines komplexen Objektes

in einem internen Datensatz werden Zugriffe auf das gesamte komplexe Objekt optimiert. Vermeiden von Join-Operationen.

Problem: Der interne Datensatz kann sehr groß werden.

92


Beispiel (1)

Geold: 1Mat: id77

Cuboid

Geold: 8Mat: id99

id8

Geold: 5Mat: id77

id5

Geold: 7Mat: id99

id7

Geold: 6Mat: id88

id6

Geold:3Mat: id99

id3

Geold: 2Mat: id77

id2

Geold:4Mat: id77

id4

Geold: 9Mat: -

id9



id99


id88

id77

Id: 3000Geo: {}

Part

Id: 6700Geo:{id9}

id150

Id: 1001Geo: {id6}

id130

Id: 2010Geo:{}

id140

Id: 1002Geo: {id7}

id131

Id: 4712Geo: {id3}

id121


id120


id122



id102


id101

id100

Material id110 id1

Product

93


Beispiel (2)


id1 4711 id77 39.99 “red“ id11 …. id18

id2 5301 id77 19.95 “blue“ id21 …. id28

id3 8020 id99 89.9 “yellow“ id31 …. id38

Cuboid

OID Name SpecWeight

id77 “Iron” 7.86

id99 “Gold” 19.0


VertexNestedCuboid

Geold Color Value Mat Vertices Vertld X Y Z

id1 “red“ 39.99 id77 id11 0.0 0.0 0.0 id18 0.0 6.694 6.694

id2 “blue“ 19.95 id77 id21 0.0 0.0 0.0 id28 0.0 5.848 5.848

id3 “yellow“ 89.90 id99 id31 0.0 0.0 0.0 id38 0.0 4.641 4.641

94


Nachteile der Gruppierung

Nachteile: Nicht-referenzierte Unterobjekte (bspw. Objekte des Typs

Part, die in keinem Produkt vorkommen) werden nicht erfasst. Nur durch umständliche Erweiterungen behebbar.

Unterobjekte, die von mehreren Objekten referenziert werden, werden mehrfach gespeichert.

95


Umsetzung

Dateien

Dateiverwaltung



Segment- u. Pufferverwaltung


Anfragebearbeitung


Satz- u. Satzmengen-verwaltung

SatzzugriffsstrukturenZugriffsschicht für

kurze Sätze

Objektorientier-tes Datenmodell

Objekt-verwaltung

Zugriffsschicht für große Sätze

Spez. Puf-ferverw.

Dateien

Dateiverwaltung





Anfragebearbeitung


Satz- u. Satzmengen-verwaltung


Zugriffsschicht für kurze Sätze

Objektorientier-tes Datenmodell

Objekt-verwaltung

Siehe Kapitel 5.4

Umsetzung gesucht, die die Join-Einsparung nicht aufzehrt

Mit großen Datensätzen Mit kurzen Datensätzen

96


Modell der Gruppierung: NF2-Datensätze

Datenmodell der NF2-Relation (Non First Normal Form):

Geschachtelte Relation durch Zulassen mengenwertiger Attribute (Unterrelationen). Die Elemente einer Unterrelation können ebenfalls wieder

Unterrelationen besitzen.

NF2-Tupel: Tupel mit mengenwertigen Attributen.

97


Materialisierung

Grundsatz: NF2-Datensätze werden in ihre Nicht-NF2-Bestandteile zerlegt Menge „flacher“ Datensätze. Im Grundsatz werden daher die nicht-mengenwertigen

Felder in einem eigenen Datensatz zusammengefasst.

Führt zu Verweisstrukturen.

1 interne Datei pro NF2-Relation mehrere Satztypen in einer Datei.

Zwei Arten von internen Dateien: für eine freie Speicherung:

Externe Satzablage.

für eine gesteuerte Speicherung: Interne Satzablage.

98


Freie Speicherung (1)

id1 “red“ 39.99 id77

8

id11 0.0 0.0 0.0

id18 0.0 6.694 6.694

Kardinalität der Menge (=Länge

der Zeigerreihung)

NestedCuboid Geold Color Value Mat Vertices

Vertld X Y Z id1 “red“ 39.99 id77 id11 0.0 0.0 0.0

id18 0.0 6.694 6.694

id2 “blue“ 19.95 id77 id21 0.0 0.0 0.0 id28 0.0 5.848 5.848

id3 “yellow“ 89.90 id99 id31 0.0 0.0 0.0 id38 0.0 4.641 4.641

99



id1 “red“ 39.99 id77

8

id2 “blue“ 19.95 id77

8

id3 “yellow“ 89.90 id99

8

id11 0.0 0.0 0.0

id18 0.0 6.694 6.694

id21 0.0 0.0 0.0

id28 0.0 5.848 5.848

id31 0.0 0.0 0.0

id38 0.0 4.641 4.641

100



Vorteile: Wachsen und Schrumpfen des Datensatzes bzw. der

Unterrelationen wird gut unterstützt. Nachteile: Die Teile eines NF2-Datensatzes sind beliebig über Seiten

verstreut; im schlimmsten Fall erfordert jeder Zugriff auf eine Unterrelation und auf ein Element einer Unterrelation einen Seitenzugriff.

TIDs sind relativ lang (4 Bytes) und können aufgrund von Verschiebungen von Datensätzen auf den Seiten einen Zugriffsfaktor von 2 aufweisen hoher Aufwand beim Navigieren durch die Unterrelationen eines Datensatzes.

101


Gesteuerte Speicherung (1)

Beispiel DASDBS (Darmstadt Datenbanksystem): Die Menge der Seiten, die ein NF2-Datensatz belegt

(Adressraum des Datensatzes), sind exklusiv dem Datensatz zugeordnet. Spezielle Adressen sind möglich. Ballen ist möglich.

Ein NF2-Datensatz wird in flache Datensätze zerlegt: Link Set zum Erfassen der Struktur: Sätze besitzen

ausschließlich Verweise auf andere Datensätze Data Set: zum Erfassen der elementaren (nicht-

mengenwertigen) Felder. Data Sets bilden daher die Blätter eines Baumes.

102



U

3 3

V

1 2 3

A B C 2 1 0

WWW

4 4 5 5 6 6

D E D E D E

10

G

11

G

12

GFF

7

F

8 9

45

U

A B CD

1 2 3

V

E FW

G

6

45

6

7

8

9

1011

12

—

Kardinalität der Unterrelation

103



U

3 3

V

1 2 3

4 4 5 5

6 6

A B C

D E D E

D E

2 1 0

WWW

7

F

10

G

11

G 8

F

12

G 9

F

P204

P123

P316

Ballen der Blätter in depth-first Reihenfolge

Ballen der internen Knoten in breadth-first Reihenfolge

104



Mini-TIDs für die interne Referenzierung: Beschränkung auf den Adressraum des Datensatzes.

2 Bytes für die Repräsentation der internen Seitennummern ausreichend: damit können 65.536 Seiten adressiert werden.

Aufwand 2+1 Bytes gegenüber 3+1 Bytes „normaler“ TIDs. Nutzung der Hierarchie Zu jedem internen Datensatz

existiert genau ein Vaterdatensatz. Bei Verdrängung eines internen Datensatzes wird die

Referenz in dem Vaterdatensatz direkt angepasst. Im Kopf der Wurzelseite befindet sich eine Tabelle, die

interne Seitennummern auf externe (Segment-) Seitennummern abbildet.

105



Hierarchische TIDs für die externe Referenzierung: Ein hierarchischer TID ist eine Folge:

Die erste Komponente ist die (externe) Seitennummer der Wurzel des NF2-Datensatzes.

Die restlichen Komponenten beschreiben einen Pfad in dem NF2-Datensatz.

Hierarchische TIDs müssen bei Verschiebungen von internen Datensätzen auf den Seiten des NF2-Datensatzes stabil bleiben. Daher dürfen die Verweise in den Link Sets nicht

verschoben werden. Löschen eines Elements einer Unterrelation: Setzen des

entsprechenden Slot in dem Link Set auf 0. Einfügen: Am Ende des Link Set oder bei einem 0-Eintrag.

106



U

3 3

V

1 2

4 4 5 5

6 6

A B C

D E D E

D E

2 1 0

WWW

7

F

10

G

11

G 8

F

12

G 9

F

P123

(P123,2,1,0) (P123,2,2,1,1)

3

Seitennummer

2. Unterrelation(V)

Element Nr.1

Nicht-mengenwertige Feldwerte (angezeigt durch die „0“)

Seitennummer2. Unterrelation(V)

Element Nr.21. Unterrelation(W)

Element Nr.1

107



U

3 3

V

1 2

4 4 5 5

6 6

A B C

D E D E

D E

2 1 0

WWW

7

F

10

G

11

G 8

F

12

G 9

F

(P123,0)P123

Seitennummer(P123,2,1,0)

(P123,1,2)(P123,2,2,1,1)

2. Unterrelation(V)

Element Nr.1

Nicht-mengenwertige Feldwerte (angezeigt durch die „0“)

(P123,2,2)

Seitennummer2. Unterrelation(V)

3

Element Nr.1

Element Nr.21. Unterrelation(W)

108



Probleme: Referenzen auf interne Datensätze (hierarchische TIDs)

haben variable Länge und erfordern ein anderes Format als Referenzen auf „normale“ Datensätze („normale“ TIDs).

Die sortierte Speicherung von Unterrelationen ist nicht möglich, da die Position der Elemente – unabhängig von dem Sortierkriterium – durch die hierarchischen TIDs festgelegt ist und bei Änderungen nicht verschoben werden darf.

109



XML-DatenmodellXML-Datenmodell

110


Klassifikation

Materialisierung von XML-Dokumenten

Materialisierung als Volltext

Dateispei-cherung: Dateien

Datenbank-speicherung:

CLOB

Abbildung auf konventionelle

Datenbankstrukturen

Struktur-bewahrende Abbildung

Struktur-zerstörende Abbildung

Materialisierung als Graphstruktur

Generische Graphspei-

cherung

Document Object Model

(DOM)

Zugriff wie bei Information Retrieval:

Volltextindex

Umsetzung auf Relationen

Umsetzung relational / objektrelational

111


Architekturerweiterung

Dateien

Dateiverwaltung





Anfragebearbeitung



Zugriffsschicht

XML- DatenmodellAbbildungSatz- u. Satzmengen-

verwaltung

Anpassungs-maßnahmen: Native Lösung

Keine Anpassung, Fragmentierung:

Schreddern

112


Dokument als Volltext (1)





CLOB


Datenbankstrukturen





cherung


(DOM)


Volltextindex



SchreddernNative Lösung

113



<?xml version="1.0" ?><bib>

<paper id = "o12" ><title> Foundations of Databases </title><author>

<firstname> Serge </firstname> <lastname> Abiteboul </lastname> </author> <year> 1997 </year>

<publisher> Addison Wesley </publisher></paper>

…</bib>





…</bib> XML

BibliographyBibliography

BibID PaperList

DBLP <?xml version="1.0"?><bib><paper id = "o12" ><title>Foundations of Databases</title><author><firstname>Serge</firstname><lastname>Abiteboul</lastname></author><year>1997</year><publisher> Addison Wesley</publisher></paper>…

DBLP.xml

Zusätzlicher VolltextindexZusätzlicher Volltextindex

114



Vorteile: Speichern und Auslesen von beliebigen XML-Dokumenten

wird unterstützt.

Datenbasis kommt ohne Datenbankschema aus Kein Schema für XML-Dokumente benötigt!

Nachteile:

Datenbanksystem muss spezielle Unterstützung für das Verarbeiten langer Texte bieten.

Dokumentstruktur wird nicht berücksichtigt.

Lesender oder schreibender Zugriff auf Werte einzelner XML-Elemente nur umständlich möglich.

115


Dokument als Graphstruktur





CLOB


Datenbankstrukturen





cherung


(DOM)


Volltextindex




116


Generischer Dokumentgraph (1)

Einbezug der Strukturinformationen, die ein XML-Dokument enthält, in die Speicherung.

Interpretation eines XML-Dokuments … …als gerichteter Graph...

XML-Elemente und XML-Attribute ergeben die Knoten des Graphen

Kanten modellieren die Enthaltensbeziehung Kanten werden mit den Bezeichnern der enthalten Elemente

bzw. Attribute gekennzeichnet

…und Speichern der Knoten und Kanten in einer Relation.

117







…</bib>





…</bib> XML

11

22

33

bib

paper

o12o12

id

Foundations…Foundations…

title

44

author

SergeSerge

firstname

AbiteboulAbiteboul

19971997

year

Addison…Addison…

publisher

lastname

118


11

22

33

bib

paper

o12o12

id

Foundations…Foundations…

title

44

author

SergeSerge

firstname

AbiteboulAbiteboul

19971997

year

Addison…Addison…

publisher

lastname

KantenKanten


Name

123334433

Beginn Ziel/WertIstText

bibpaperidtitleauthorfirstnamelastnameyearpublisher

neinneinjajaneinjajajaja

23o12Foundations…4SergeAbiteboul1997Addison…

Reihenf.

111231245

Bei Bedarf zusätzliches Attribut, um XML-Attribut und XML-Element unterscheiden

zu können

119


Document Object Model (1)

DOM: API mit Klassenstruktur

DOMImplementation Node NodeList NamedNodeMap

Attr

CharacterData

Document

DocumentType

Element

Entity

EntityReference

Notation

getChildren()getFirstChild()getNextSibling()getParentNode()getPreviousSibling()hasChildren()insertBefore(node,node)removeChild(node)replaceChild(node)

getChildren()getFirstChild()getNextSibling()getParentNode()getPreviousSibling()hasChildren()insertBefore(node,node)removeChild(node)replaceChild(node)

getAttributes()getElementsByTagName(string)getTagName()setAttribute(attribute)setAttribute(attributelist)setTagName(string)

getAttributes()getElementsByTagName(string)getTagName()setAttribute(attribute)setAttribute(attributelist)setTagName(string)

getName()getSpecified()getValue()setName(string)setSpecified(boolean)setValue(nodelist)toString()

getName()getSpecified()getValue()setName(string)setSpecified(boolean)setValue(nodelist)toString()

120



DOM: Beispiel Abbildung auf Relationen per Split Instance Model

DOMImplementation Node NodeList NamedNodeMap

Attr

CharacterData

Document

DocumentType

Element

Entity

EntityReference

Notation

121







…</bib>





…</bib>

node_id node_type doc_id parent p_sibling n_sibling

001 element b0001

002 element b0001 001 ......

003 element b0001 002 004

004 element b0001 002 003 007

005 element b0001 004 006

006 element b0001 004 005

007 element b0001 002 004 008

008 element b0001 002 007

009 attribute b0001 002

node_id tag_name text

001 bib

002 paper

003 title Foundations of Databases

004 author

005 firstname Serge

006 lastname Abiteboul

007 year 1997

008 publisher Addison-Wesley

node

element

122


Dokument als Graphstruktur

Vorteile: Festes Datenbankschema.

Kein Schema für XML-Dokumente benötigt!

XML-Dokument vollständig rekonstruierbar.

DOM-Speicherung auf API zugeschnitten gute Verarbeitbarkeit (insbesondere auch Änderungen!).

Nachteile:

Hochgradig fragmentierte Speicherung.

Dokumentrekonstruktion aufwändig.

Nur einfache Anfragen lassen sich performant beantworten.

123


Dokument als Relation





CLOB


Datenbankstrukturen





cherung


(DOM)


Volltextindex




124


Strukturbewahrende Abbildung (1)

Grundgedanke:

Überführen des XML-Dokuments in Relationen unter Wahrung der Dokumentstruktur. Zwang zu relationalem Datenbankschema.

Erfordert auch Datenbankschema für die XML-Dokumente.

Ausgehend von der DTD wird ein passendes relationales Schema erzeugt, das die Dokumente aufnehmen kann.

Es müssen alle erlaubten Dokumente, die der DTD gehorchen, gespeichert werden können: z.B. muss auch für optionale Unterelemente etc. Speicherplatz

vorhanden sein.

125



<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author+, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]>

<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author+, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]> DTD





…</bib>





…</bib> XML

126



Schritt 1: Reduktion der Komplexität einer DTD Geschachtelte Elementdefinitionen entschachteln

z.B. (a|b) a?,b? Folge von Kardinalitäten zusammenfassen

z.B. a*? a* Unterelemente gruppieren

z.B. ..., a*, ..., a*, ... ..., a*, ... Alle „+“ Kardinalitäten werden zu „*“

Die obigen Transformationen bewahren ... 1:1- bzw. 1:n-Elementbeziehungen und Optionale Unterelemente

Aber: Informationen über Reihenfolge und genau erlaubte Anzahl der Unterelemente kann verloren gehen

127


Strukturbewahrende Abbildung (4) Im Beispiel wird author+ zu author* Neue DTD beschreibt also eine Obermenge von XML-

Dokumenten

<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author+, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]>

<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author+, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]> DTD

<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author*, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]>

<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author*, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]> DTD

128



Schritt 2: Strukturinformationen extrahieren Die neue DTD dient nun als Grundlage für einen gerichteten

DTD-Graphen, der die Struktur dieser DTD repräsentiert: Für jedes XML-Element ergibt sich genau ein Knoten im Graph. Für jedes Vorkommen eines XML-Attributs bei einem Element

wird ein Knoten angelegt, der mit dem entsprechenden Element-Knoten verbunden ist.

Knoten für Element und erlaubte Unterelemente werden durch Kanten verbunden.

Ist als Kardinalität bei einem Unterelement „*“ oder „?“ angegeben oder liegt ein mengenwertiges bzw. optionales XML-Attribut vor, wird die entsprechende Kante mit dem Symbol der Kardinalität markiert.

Rekursionen können durch Zyklen im Graph erkannt werden.

129


Strukturbewahrende Abbildung (6)<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author*, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]>

<!DOCTYPE bib [ <!ELEMENT bib (paper*)> <!ELEMENT paper (title, author*, year, publisher?)> <!ATTLIST paper id ID #REQUIRED> <!ELEMENT author (firstname,lastname)> <!ATTLIST author age CDATA #IMPLIED> <!ELEMENT firstname (#PCDATA)> <!ELEMENT lastname (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT year (#PCDATA)> <!ELEMENT publisher (#PCDATA)> …]>

idid

bibbib

paperpaper

authorauthor

yearyear publisherpublisher

ageage firstnamefirstname lastnamelastname

**

**titletitle

DTD-Graph

??

130



Schritt 3: Erzeugen der Relationstypen aus dem DTD-Graph Relationstypen erzeugen für…

jeden Knoten mit keiner oder mehr als einer Eingangskante, jeden Knoten unterhalb einer „*“-Kante, mindestens einen Knoten innerhalb einer Rekursion

… und mit Attributen ergänzen: Jedem Relationstypen werden diejenigen Blattknoten als

Attribute zugeschlagen, die direkt vom entsprechenden Knoten aus erreichbar sind. Eine dazwischenliegende „?“-Kante erlaubt NULL-Werte beim Attribut.

Jeder Relationstyp erhält künstlichen Schlüssel, der ein dort gespeichertes XML-Element eindeutig identifiziert.

Beziehungen werden über Fremdschlüssel modelliert.

131


Strukturbewahrende Abbildung (8)bibbib

paperpaper

idid

authorauthor

yearyear publisherpublisher

ageage firstnamefirstname lastnamelastname

**

**titletitle

relation Bib (bibID)

relation Author (authorID, paperID, age, firstname, lastname )

??

relation Paper (paperID, bibID, id, title, year, publisher)

132



Vorteile: Speichert alle XML-Dokumente, die einer DTD folgen. Bewirkt durch die Gruppierung von zusammengehörigen

Elementen in einem Relationstyp ein kompakteres relationales Schema.

Suche und Navigation innerhalb des Dokuments benötigen wenige Join-Operationen.

Ein direkter Zugriff auf die Elemente ist möglich.

Nachteile: Trotz Strukturabbildung kann die Struktur der XML-

Dokumente nicht mehr vollständig rekonstruiert werden. Das Wissen hierüber steckt in der Abbildungsvorschrift.

133


Strukturzerstörende Abbildung

Grundgedanke: Verwenden einer frei wählbaren Abbildungsvorschrift, die

die Elemente so zusammenfasst, dass bestimmte Anfragen besonders effizient beantwortet werden können.

Documents

Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 8 Kapitel 8 Satzmengenverwaltung