Diplomarbeit Michael Fuchs - 1997

Diplomarbeit Evaluierung der Datenbankverwaltung strukturierter Dokumente mit einem objektrelationalen Datenbanksystem (Informix-Universal-Server) ausgeführt am : Institut für Integrierte Publikations- und Informationssysteme GMD – Forschungszentrum Informationstechnik GmbH in Darmstadt Unter Betreuung von Prof.Dr. Erich J. Neuhold Dr. Klemens Böhm Dr. Yangjun Chen durch Michael Fuchs

Inhaltsverzeichnis 1

EINLEITUNG..................................................................................................................... 5 1.1 VORBEMERKUNG.................................................................................................................5 1.2 AUFBAU DIESER ARBEIT.......................................................................................................7

2

OBJEKTRELATIONALE DATENBANKSYSTEM IUS (INFORMIX UNIVERSAL SERVER)......8 2.1 DIE VERSCHIEDENE DATENBANKKATEGORIEN......................................................................8 2.2 DIE OBJEKTRELATIONALE DATENBANK IUS.........................................................................9

3

SGML : STRUKTUR UND VERWALTUNG........................................................................11 3.1 DIE STRUKTUR VON SGML...............................................................................................11 3.2 KONFIGURATION UND VERWALTUNG VON SGML-DOKUMENTEN........................................14

4

SYSTEMARCHITEKTUR DER SGML-VERWALTUNG......................................................16 4.1 ARCHITEKTUR DES GESAMTSYSTEMS.................................................................................16 4.2 BASIS-DATENTYPEN DER OBJEKTRELATIONALEN DATENBANK...........................................17 4.3 SELBSTERSTELLTE DATENTYPEN........................................................................................18 4.4 DATENBANK-TABELLEN.....................................................................................................18

DocElemTable vom Typ docElem...............................................................................19 NonFlatElemTable vom Typ nonFlatElem + docElem...............................................20 4.5 DER SGML-PARSER : SP...................................................................................................22

4.5.1 Beschreibung des SP.......................................................................................22 4.5.2 Benutzung des SP............................................................................................23 4.6 ABLAUF DER DATENBANKORGANISATION...........................................................................24

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 4.6.1 Erstellen der Datenbank-Tabellen und -Typen...............................................24 4.6.2 Ablauf : Einfügen eines Dokumentes.............................................................25 4.6.3 Aufrufen der Funktionen................................................................................28 5

IUS- SCHNITTSTELLEN-FUNKTIONEN...........................................................................29 5.1 IUS-SP SCHNITTSTELLEN-FUNKTIONEN : SGML-PARSER-MODUL.....................................29

5.1.1 SP- Funktionen, die ESQL/C-Funktionen aufrufen (Sprache : C++)...........29 5.2 IUS-SP SCHNITTSTELLE ALS ESQL/C-MODUL...................................................................31

5.2.1 Funktionen zum Aufbauen einer Client-Verbindung.......................................32 5.2.2 Funktionen zum Generieren der Datenbank...................................................32 5.2.3 Funktionen zum Generieren der Indizes.........................................................33 5.2.4 Informations- und Navigations-Hilfsfunktionen.............................................35 5.3 SGML-API-FUNKTIONEN (API=APLICATION PROGRAM INTERFACE)..................................36

5.3.1 Spezielle Abfrage-Funktionen.........................................................................36 5.3.2 Ausgabe-Funktionen.......................................................................................39 5.3.3 Funktionen zur Navigation im Dokument.......................................................39 5.3.4 Info-Funktionen über Dokumente, DTDs und Elemenenttypen.....................40 5.3.5 Funktionen speziell für strukturierte Elemente (Datenbank-Objekte)............41 5.3.6 Funktionen speziell für flache Datenbank-Objekte........................................42 5.3.7 Hilfs-Funktionen zur Navigation, speziell in flachen Textteilen.....................43 5.3.8 Hilfs-Funktionen zur Abfrage, speziell in flachen Textteilen..........................44 6

DER ALGORITHMUS : GETALLCONTAINING...................................................................46 6.1 PROBLEME MIT INCLUSIONS/EXCLUSIONS BEI DER FRAGMENTIERUNG...............................46 6.2 DEFINITIONEN FÜR DEN ALGORITHMUS..............................................................................48 6.3 BESCHREIBUNG DES ALGORITHMUS...................................................................................49

6.3.1 Funktionen, die in den Körpern der drei Schleifen aufgerufen werden.........49 6.3.2 Hilfsfunktionen, die für die Schleifenterminierung benötigt werden..............50 6.3.3 Die elementaren Funktionen...........................................................................51 6.3.4 Der Gesamt-Algorithmus................................................................................52 6.4 BEWEIS MIT INDUKTION ZUR RICHTIGKEIT DES SATZES......................................................53

7

EXPERIMENTE................................................................................................................ 57 7.1 BASIS-ELEMENTE DER EXPERIMENTE................................................................................57

7.1.1 Die SGML-Test-Dokumente............................................................................57 7.1.2 Die verschiedenen Konfigurationen...............................................................58

Seite 3t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 7.2 EXPERIMENT (I+II): DOKUMENTBEZOGENE QUERIES UND GESAMT-OPERATIONEN (EINFÜGEN, AUSGEBEN).....................................................................................................60

7.2.1 Beschreibung der Experimente.......................................................................60 7.2.2 Ergebnisse des Experiments (I+II).................................................................61 7.2.3 Analyse der Ergebnisse...................................................................................61 7.3 EXPERIMENT (III) : DOKUMENTBEZOGENE EINZEL-FUNKTIONEN.......................................62

7.3.1 Beschreibung des Experiments (III)...............................................................62 7.3.2 Ergebnisse des Experiments (III)....................................................................63 7.3.3 Analyse der Ergebnisse...................................................................................63 7.4 EXPERIMENT (IV): DATENBANK-QUERY MIT VERSCHIEDENEN KONFIGURATIONEN.............64

7.4.1 Beschreibung des Experiments (IV)................................................................64 7.4.2 Ergebnisse des Experiments (IV)....................................................................64 7.4.3 Analyse der Ergebnisse...................................................................................64 7.5 EXPERIMENT (V) : VORAUSPARSEN VS. AD-HOC-PARSEN....................................................65

7.5.1 Beschreibung des Experiments (V).................................................................65 7.5.2 Ergebnisse des Experiments (V).....................................................................66 7.5.3 Analyse der Ergebnisse...................................................................................66 8

SCHLUSSBEMERKUNG.................................................................................................... 67

ANHANG A............................................................................................................................ 69 DIE DTD FÜR SHAKESPEARE DRAMEN......................................................................................69

ANHANG B............................................................................................................................ 71 DIE SUPERDTD-INSTANZ 'SDTDI_PLAY', ERSTELLT VON DER DTD 'SHAKSPER.DTD' AUS ANHANG A........................................................................................................................71

ANHANG C............................................................................................................................ 76 DAS SQL-SCRIPT 'CREATE.SQL' ZUM ERSTELLEN DER DATENBANK-TYPEN UND -TABELLEN......76

ANHANG D............................................................................................................................ 81 DAS SQL-SKRIPT 'INITS.SQL' ZUM INITIALISIEREN DER DATENBANKTABELLEN...........................81

ABBILDUNGSVERZEICHNIS................................................................................................... 85 TABELLENVERZEICHNIS...................................................................................................... 86 LITERATURVERZEICHNIS..................................................................................................... 87

Seite 4t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

1 Einleitung

1.1

Vorbemerkung Man findet in der heutigen Zeit in fast allen Lebensbereichen multimediale Informationen,

die durch fortschreitende Rechnertechnologie, sinkende Beschaffungskosten und Vereinfachung der Hard- und Softwarebedinung zu erklären ist. Einen wesentlichen Anteil trägt natürlich auch das Internet, das ohne multimediale Informationen gar nicht mehr denkbar ist. Neben Video und Audio kommen wir mit dem Internet auf ein wichtiges Medium, den Text. Eine Seite im Internet ist als besonderer Text abgespeichert. Man nennt diese Textform HTML und steht für "Hyper Text Markup Language" . HTML ist aber kein einfacher Text, sondern eine Sprache (wie das Wort "Language" schon ausdrückt) mit syntaktischen und semantischen Regeln und ist ein Dialekt aus der Familie SGML (Standard Generalized Markup Language). Mit SGML hat man die Möglichkeit, Teile des Textes mit sogenannten Markups hervorzuheben und auch Zusatzinformationen oder Optionen (Attribute) über den Inhalt zu bestimmen. Diese hervorgehobenen Textteile kann man dann gesondert behandeln. Beispiele für diese 'Sonderbehandlung' sind : Sprünge ausführen, Informationen über den Inhalt oder Inhalte selbst abfragen, Schrift des Inhalts ändern usw. Diese Hervorhebungen kann man jedoch nur optimal nutzen, wenn auch mehrere SGML-Texte zusammen abgespeichert sind und es Möglichkeiten gibt, um diese markierten Textteile auch von mehreren Dokumenten abzufragen. So etwas ist mit Textverarbeitungssystemen, im herkömmlichen Sinne, nur schwer bis überhaupt nicht möglich.

Seite 5t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Um

Daten

abzuspeichern

und

sie

dann

später

abzufragen,

hat

sich

die

Datenbanktechnologie bewährt. Hierbei hat sich das relationale Datenbankschema in den letzten Jahren als populärstes Schema hervorgetan. Für dieses Datenbankschema gab es eine Reihe von Optimierungen, die eine sehr schnelle Abfrage von Daten ermöglicht. Das Problem bei der Verwaltung von multimedialen Informationen mit einer relationalen Datenbank ist aber schon an dem Beipiel 'großer Text' zu illustrieren. Die relationale Datenbank hat nur einfache Datentypen. Unter anderem können Texte, nur bis zu einer gewissen Größe, in der Datenbank gespeichert werden. SGML-Textteile können aber beliebig groß sein und somit ist das relationale Datenbankschema, in seinem Ursprung, nicht Ideal für die Verwaltung von multimedialen Informationen. Wenn man diese Dokumentteile (und dessen Behandlung) jetzt nicht nur als Felder in einer Datenbank, sondern mehr als Objekte, ansieht, dann bietet sich das objektorientierte DBMS (DatenBank Management System) an. Eine solche Verwirklichung besteht in dem System HyperStorM (Hypermedia Document Storage and Modelling) ([BANY95]) welches auf dem objektorientierten Datenbanksystem 'VODAK' ([IPSI95]) entwickelt wurde. Die im Laufe der Jahre gewonnenen Erkenntnisse zur Optimierung von 'Queries' in relationalen Datenbanken wurde genutzt, um ein neues Datenbankschema zu entwickeln, welches auch den Objektgedanken integriert. Man nennt es das objektrelationale DBMS. Mit diesem DBMS kann man alle Vorteile einer relationalen Datenbank nutzen und zusätzlich Objektkonzepte behandeln. Somit können wir in einem solchen System, multimediale Objekte speichern und darauf zugreifen. Eine genauere Diskussion über das Auswählen des geeigneten Datenbankschemas liefert [Sto96]. In dieser Arbeit sollen nun die Ideen und Erfahrungen von HyperStorM übernommen und auf ein solches objektrelationales DBMS projeziert werden. Das hierbei gewählte objektrelationale System ist IUS (Informix Universal Server). Mit einer Menge von 'build in'-Funktionen und einigen Innovationen wurden dann Evaluierungen vorgenommen. Diese Experimente stützen sich wiederum teilweise auf die Erfahrungen, die in HyperStorM beobachtet wurden.

Seite 6t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

1.2

Aufbau dieser Arbeit Im folgenden Unterkapitel, gibt es ein Übersicht, wie diese Arbeit mit seinen 8 Kapiteln

aufgebaut ist. Kapitel 2 soll einen Überblick über das objektrelationale Datenbankschema geben und geht dabei insbesondere auf das gewählt System IUS ein. Im Kapitel 3 werden dann Grundsätze von SGML erläutert und Verwaltungsmechanismen beschrieben. Die Architektur einzelner Komponenten (wie zum Beispiel der SGML-Parser, die Datenbank, usw.) sowie des Gesamtsystems wird in Kapitel 4 aufgezeigt. Danach folgt die Beschreibung der Implementierten Funktionen im Kapitel 5. Motivation, Beschreibung und Verifikation des Algorithmus getAllContaining, der das Fragmentieren von Dokumenten mit komplexer DTD erleichtern soll, sind im Kapitel 6 zu finden. Der evaluierende Teil der Arbeit in Form von fünf Experimenten befindet sich im Kapitel 7. Zum Ende, in Kapitel 8, gibt es, nach einer Zusammenfassung noch ein paar abschließende Bemerkungen und eine Aussicht. Im Anhang befinden sich ausführliche Beispiele für eine DTD, Super-DTD-Instanz und SQL-Skripten.

Seite 7t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

2 Objektrelationale Datenbanksystem IUS (Informix Universal Server) Im folgenden Kapitel werden in Unterkapitel 2.1 verschiedene Datenbankkategorien genannt und miteinander verglichen. In 2.2 wird dann das Datenbanksystem IUS vorgestellt. 2.1

Die verschiedene Datenbankkategorien. Seit den letzten zwei Jahrzehnten haben sich Datenbanktechniken schnell entwickelt und

es stehen der Welt unterschiedliche Datenbank- und Informationssysteme zur Verfügung. Diese Systeme können nach Stonebraker [Sto96] in vier Kategorien klassifiziert werden: 1. Text oder Bildverarbeitungssystem (keine Datenbank) 2. Relationale Datenbank mit einfachen Datentypen und SQL (Standard Query Language) 3. Objektorientierte Datenbank mit komplexen Datentypen 4. Objektrelationale Datenbak mit komplexen Daten und ESQL (Extended SQL) Vorteil von der Kategorie 1 ist die Einfachheit im Behandeln der Objekte, es gibt jedoch keinerlei Datenbankfunktionalitäten. Kategorie 2 ist die weit verbreitetste Datenbankform. Mit einem solchen Datenbanksystem operiert man auf einfachen Datentypen. Die Behandlung von Daten durch Queries wurde im Lauf der Jahre optimiert. Alle Anwendungsfälle, die keine komplexeren Datentypen benötigen, werden optimal mit der relationalen Datenbank unterstützt. Komplexe Datentypen können, wenn überhaupt, nur umständlich mit relationalen Datenbanksystemen verwaltet werden. Um komplexe Datentypen zu behandeln, wurde das objektorientierte Datenbanksystem entwickelt. In Kategorie 3 ist die Modellierung eines

Seite 8t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Objektes sehr flexibel und einfach, der Zugriff dagegen ist sehr komplex. Um von der Einfachheit und Mächtigkeit des relationalen Zugriffs zu profitieren, wurde die realtionale Datenbanktechnik für Modellierung und Zugriff auf komplexe Datentypen erweitert. Diese neuen Systeme gehören zu Kategorie 4. Auf einem solchen objektrelationalen System wurde diese Arbeit implementiert und evaluiert. Das gewählte objektrelationale System trägt den Namen IUS (Informix Universal Server). Andere Beispiele für die Ausnutzung der verschiedenen Kategorien kann man im Kapitel 14 in [Sto96] finden. 2.2

Die objektrelationale Datenbank IUS Das objektrelationale Datenbanksystem IUS kann als Basis wie ein relationales

Datenbanksystem betrachtet werden. Es gibt zusätzlich neue Datentypen zur Einbettung von verschiedenen multimedialen Informationen. Hauptsächlich handelt es sich dabei um Datentypen wie : lvarchar, clob oder collection . Diese Datentypen werden genauer im nächsten Kapitel beschrieben, in dem auch die Architektur des Systems skizziert wird. Außerdem gibt es die Möglichkeit, frei definierte Funktionen und Prozeduren zu erstellen. Diese Funktionen können dann aufgerufen werden, sowie in ein SQL-Statement eingebunden werden. Beispielsweise kann man ein Funktion mit execute function bzw. execute procedure aufrufen. Die Sammlung der Funktionen zur Manipulation von Datenbankinhalten, die vom Benutzer definiert wurden, nennt man 'DataBlade'.

In SQL-Statements kann man sowohl im select-Teil sowie im where-Teil eine Funktion einbauen. Im Folgenden sind einige Beispiele für neue Datentypen und deren Benutzung in dieser Arbeit. 

collection (Liste,Menge) benutzt bei Index-Einträgen



clob (große Texte bis 4 GB) benutzt für flache Text-Objekte



lvarchar (varible Zeichenketten bis 32 KB) content-model



opaque (private Datentypen)

Seite 9t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Die Funktions-Einbindung kann Beispielsweise folgendermaßen geschehen:



execute function getAll("10|-1","NAME") In diesem Beispiel wird die DataBlade-Funktion getAll aufgerufen und das Ergebnis wird

in die vorher ausgewählte Ausgabe übergeben. Die Eingabe-Parameter sind vom Typ char(128). Man kann also 128 Zeichen lange Strings als Parameter übergeben. Als Rückgabe bekommt man ein clob.



select etName from nonFlatElemTable where isContainedIn(own_id , 10) Dieses SQL-Statement bindet eine DataBlade-Funktion in die 'where-clause' mit ein.

Berechnet werden alle Namen aus der nonFlatElemTable, die in dem Element mit der oid 10 enthalten sind. own_id ist ein Feld der Datenbanktabelle nonFlatElemTable und wird während der Query mit entsprechenden Zwischenwerten gefüllt.

Seite 10t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

3 SGML : Struktur und Verwaltung In diesem Kapitel werden einige Grundkenntnisse über die Struktur in Unterkapitel 3.1 vermittel. In 3.2 geht es um die Verwaltung von SGML-Dokumenten, auch anhand eines Beispiels, sowie speziell gewählte Verwaltungsmechanismen. Es handelt sich hierbei um das Konfigurieren von Dokumenten. 3.1

Die Struktur von SGML Im Folgenden werden Beschreibungen der Sprache SGML gebracht. Diese Einführung

dient nur als Auffrischung der Kenntnisse von SGML und ist keinerlei Ersatz für die gesamte Lehre in SGML. Ausführlichere Beschreibungen, Definitionen und Grammatiken finden sich in Practical SGML([Her94]). SGML steht für 'Standard Generalized Markup Language'. Ein SGML-Dokument besteht aus 2 Teilen. Der erste Teil ist ein Dokument mit markierten Textteilen und der zweite Teil ist eine Definitionsdatei, zur Definition verschiedener Dokumenttypen. (z.B. Brief, Bericht, Drama). Man nennt diese Datei die DTD (Dokument Type Definition). Dadurch werden Syntax und Grammatik der markierten Textteile für die jeweiligen Typen festgelegt. Diese Textteile nennt man Dokument-Elemente. Die Markierung dieser Dokument-Elemente im Dokument geschieht mit sogenannten Markups und bestehen aus dem Elementtyp-Namen und Zeichen, die es als Markierung kennzeichnen und angeben, ob es sich um den Beginn oder das Ende der Markierung handelt. Zusammengesetzt nennt man diese Zeichenfolge Starttag bzw. Endtag. Ein Starttag hat die Form : "<ETName>" und das Endtag : "". In jedem Element können sich weitere Elemente befinden. Welche Elemente in einem anderen Element enthalten sein dürfen, wird für jedes Element in der DTD definiert. Man nennt die Definition,

Seite 11t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS die eine 'enthalten'-Beziehung definiert, das Content-Model. Zusätzlich können auch Metainformationen von Elementtypen definiert werden. Diese Metainformationen nennt man Attribute und sind jeweils auf die Dokument-Elemente bezogen. In Abbildung 3.1-1 ist ein SGML-Dokument mit entsprechenden Kommentaren und in Abbildung 3.1-2 ist die dazugehörende DTD vom Dokumenttyp 'article'. Wie man erkennen kann, gibt es auch Starttags ohne die entsprechenden Endtags, wie im Beispiel bei 'author' oder 'paragr'. In einem solchen Fall kann man nur mit der DTD entscheiden, wo sich das Ende befindet. Ausfühlicher wird dieses Problem im Experiment (V), Kapitel 7 ab der Seite 65 noch einmal behandelt. Die Elementente, die den eigentlichen Text beinhalten, nennt man nichtstrukturierte Dokument-Elemente und haben als Content-Model (#PCDATA). PCDATA steht für Parsed Character DATA. Beispiele dieser Elemente kann man in der DTD in Abbildung 3.1-2 finden. Es handelt sich um die Elemente title, author, abstact, caprion, paragraph und acknowl. Die Definitionen im Einzelnen findet man in [Her94]. <article status="final">  article hat ein Attribut namens 'status' mit dem Wert 'final' D. David R. John  Das ist ein Author ohne Endtag ! ... ... Structured documents (e.g., SGML) can benefit a lot from database support and more specifically from object-oriented database(OODB) management systems <section> <sectitle>Introduction ...... <paragr>This paper is organized as follows. Section 2 introduces the SGML standard. The mapping from SGML to the O2 DBMS is defined in Section 3. Section 4 presents the extension ... <section> <sectitle>SGML preliminaries <paragr>In this section, we present the main features of SGML. (A general presentation is clearly beyond the scope of this paper.) ... ... Abbildung 3.1-1:

Eine Beispiel-Dokumnet vom Dokumenttyp 'article'

Seite 12t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

DTD:
article [ article article title author abstract section sectitle subsectn body figure figure picture picture


caption fig paragr figure acknowl

(title,author+,affil,abstract,section+,acknowl)> status (final|draft) draft> (#PCDATA)>  Parsed Character Data; (#PCDATA)> Ist der eigentliche Inhalt eines (#PCDATA)> terminalen Elementes. ((title, body+) | (title, body*,subsectn+))> (#PCDATA)> (title, body+)> (figure | paragr)> (picture, caption?)> lable ID #IMPLIED EMPTY> sizex NMTOKEN "16cm" sizey NMTOKEN #IMPLIED file ENTITY #IMPLIED (#PCDATA)> SYSTEM "/u/chris/SGML/image1" NDATA> (#PCDATA)> reflable IDREF #REQUIRED> (#PCDATA)>

]> Abbildung 3.1-2:

Eine Beispiel-DTD vom Dokumenttyp 'article'

Seite 13t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

3.2

Konfiguration und Verwaltung von SGML-Dokumenten Dieses Unterkapitel beschäftigt sich mit Verwaltungs- und Konfigurations-Mechanismen,

die HyTime Standards entsprechen. Näheres über HyTime erfährt man in [BAK95]. Bei der Verwaltung von SGML-Dokumenten hat man die Möglichkeit, jedes strukturierte Dokument-Element als eigenes Datenbankobjekt zu speichern. Dies wird auch in der Abbildung 3.2-4 deutlich. Hier ist das Beispiel-Dokument als Baum dargestellt. In dem Baum entspricht jeder Knoten einem eigenen Datenbank-Objekt. Die flachen DatenbankObjekte bilden die Blätter dieses Baumes und sind in der Baumdarstellung mit einem Rahmen versehen.

author

title

author

David

author

abstract

sectitle

John

Introduction From Stuctured Documtent...Facilit

.......

section

Structured documents .....management system

section

sectitle

body

.......

body

prelimitinaries paragraph

paragraph

This paper organazed as follows... In this section, we present .... ...the extension .... ...the scope of this paper) ... Abbildung 3.2-3:

Repräsentation des Beispieldokuments – Dokumentelement = Knoten

Weiterhin gibt es auch die Möglichkeit, die Speicherung der Dokument-Elemente in einer anderen Weise zu organisieren. Extremfall wäre die Speicherung des SGML-Textes, ohne Strukturierung und als Ganzes. Eine Mischung aus diesen zwei Extremen wurde für diese Arbeit gewählt.Bei dieser Variante (hybride Speicherung [BAK95]) ist es nun möglich, bestimmte Dokument-Elemente zusammenzufassen und als komplett markierte Textteile in flache Datenbank-Objekte zu speichern. In Abbildung 3.2-4 ist wieder das Beispieldokument in Baum-Darstellung. In diesem Falle sind aber die Dokument-Elemente vom Typ 'sectitle', 'body', 'paragraph' zu einem flachen Datenbank-Objekt zusammengefaßt. Diese verschiedenen

Seite 14t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Repräsentationsmöglichkeiten (Konfigurationen) werden bei der Verwaltung berücksichtigt. Auf diese zusammengefaßten, flachen Datenbank-Objekte kann nun mit individuellen Mechanismen zugegriffen werden. Neben den klassischen C-String-Funktionen, hat man auch die Möglichkeit, den ganzen, flachen Teil als PAT-Trees oder PAT Arrays abzuspeichern, wie es im Kapitel 5 in [GBS92] beschrieben ist. Im Kapitel 7 werden unterschiedliche Konfigurationen evaluiert und dann die entsprechenden Vor- bzw. Nachteile dazu erörtert.

Abbildung 3.2-4:

Repräsentation des Beispieldokuments - zusammengefaßte Elemente author

title

author

author

abstract

section

....... section

.......

David John ctitle>Introduction <sectitle>SGML preliminaries... ..... <paragr>In this section, we present the main features of SGML. (A general presentation is clearly be ody><paragr>This paper is organized as follows.Section 2 introduces the SGML standard. The mapping from SGML to the O2 DBMS is defined in Section 3. Section 4 presents the extension ... ... ody> From Stuctured Documtent...Facilit

Structured documents .....management system

Seite 15t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

4 Systemarchitektur der SGML-Verwaltung Im folgenden Kapitel wird die Architektur des Verwaltungssystems vorgestellt. Im Unterkapitel 4.1 gibt es eine Beschreibung des Gesamtsystems. Weiterhin gibt es in 4.2 ein Überblick über Datentypen, die benutzt wurden und in 4.3 über die selbsterstellten Datentypen. Es folgt eine Auflistung der zehn Datenbanktabellen in 4.4 sowie eine Skizzierung des SGMLParsers in 4.5. Die Einbindung von Funktionen in der Datenbank, sowie der Ablauf des Einfügens eines SGML-Dokuments werden anhand von Beispielen in Unterkapitel 4.6 gezeigt. 4.1

Architektur des Gesamtsystems Im Folgenden wird ein Überblick, über das gesamte System gegeben. Unter anderem

wird in Abbildung 4.1-5 die Architektur des Gesamtsystems skizziert. Außerdem werden die Schnittstellen genannt und der Bezug zum SGML-Parser angegeben. Der SGML-Parser SP ist in mehrere Komponenten aufgeteilt, wobei hier nur die Komponenten genannt sind, die direkt mit der SGML-Datenbankverwaltung zu tun haben. Die in der Abbildung links befindliche Komponente ist eine C++-Klasse (elementOutput), die aus einer DTD eine SuperDTD-Instanz erstellt. Genaueres über diese Generierung befindet sich im Kapitel 4.6.2. Die rechte Komponente hingegen ist eine Klasse (ModFuncs), die Funktionen der ESQL-Schnittstelle aufruft. Diese Funktionen sind im wesentlichen zum Erstellen der Dokument-Elemente und der Index-Strukturen. In dieser Komponente wird auch die Konfigurations-Datei ausgelesen und ebenso werden die Index-Informationen aus der SuperDTD-Instanz geholt. Die ESQL/C-Schnittstelle ist eine Sammlung von Funktionen, die in der Sprache C implementiert sind und eine extended SQL-Schnittstelle verwenden. Diese ESQL/C-Sprache

Seite 16t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS wird dann mit einem 'Precompiler' zu einem C-Quellcode und hinterher zu einem ausführbaren Objekt compiliert. Zu SQL-Abfragen und Aufrufen wird dann das sogenannte Datablade als Kommunikationsmittel benutzt. Das Datablade besteht aus Funktionen, deren AufrufSchnittstellen direkt in IUS integriert sind und dynamisch aus einer 'library' (sgml_server.so) geladen und ausgeführt werden.

execute function oder SQL-Abfragen

SP-Komponente zum Erstellen der SDTD-Instanz

SP-Komponente zum Einfügen in die Datenbank

ESQL/C -

C++

Schnittstelle

SGML-Parser DataBlade API

Index-Strukturen Dokumente SuperDTDInstanzen

Abbildung 4.1-5:

4.2

Architektur des Gesamtsystems

Basis-Datentypen der objektrelationalen Datenbank Die

Tabelle

4.2-1

in

diesem

Unterkapitel

listet

die

Basis-Datentypen

der

objektrelationalen Datenbank auf. Insbesondere sind das die Datentypen von SQL und der Schnittstellen-Sprache C. SQL char int boolean varchar

C mi_char mi_integer mi_boolean mi_lvarchar*

clob collection

MI_LO_HANDLE* MI_COLLECTION *

Tabelle 4.2-1:

Beschreibung entspricht dem char in C entspricht dem int in C entspricht dem int in C, mit true oder false als 1 oder 0 Zeiger auf ein String mit variabler Zeichenanzahl(max. 32KB) Handle auf ein Dateiartigen Text (max. 4 GB) Handle auf eine geordnete/ungeordnete Liste oder Menge

Datentypen von den verschiedenen Schnittstellen

Seite 17t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 4.3

Selbsterstellte Datentypen Die in Tabelle 4.2-1 aufgelisteten Datentypen werden als Basis für selbsterstellte

Datentypen benutzt. Diese selbsterstellten Datentypen werden mit einer Formbeschreibung und einem Beispiel in Tabelle 4.3-2 skizziert, die sich im folgenden Unterkapitel befindet. Name Position

Basistyp spezielle Form mi_lvarchar* "|"

id_type DocElemRef DocIDRef IndexValue

mi_integer mi_integer positiv mi_integer. positiv mi_lvarchar* "|"

Tabelle 4.3-2:

4.4

Beispiel "10|-1", "32|400" 10 55 10 Bsp.: "20|2" , "100|-1"

Bemerkung Strukturiert  offset=-1

Strukturiert  occurrence=-1

Selbsterstellte Datentypen und ihre Abstammung

Datenbank-Tabellen Im flogenden Unterkapitel werden zehn Tabellen aufgelistet. Diese Tabellen werden zur

Speicherung von Dokumenten und Metainformationen benutzt. DocumentTable : In dieser Tabelle wird der 'Kopf' der Datei gespeichert. Der Kopf besteht aus name, dem Namen des Dokumentes (mit Pfad, wenn dieser beim Einfügen mit angegeben wurde) und aus Referenzen dtdref bzw. root zur DTD und zum Wurzel-Element des Dokuments. own_id ist die oid des Datenbankobjekts. DocumentTable vom Typ document Feldname Feldtyp Beschreibung own_id id_type Eindeutiger Bezeichner des Datenbankobjektes document name varchar(128) Der Name des SGML-Dokumentes mit Pfad dtdref id_type Die oid der zugehörigen DTD root id_type Die oid des Wurzel-Elementes des Dokuments DtdTable : Hier werden die Informationen der DTD abgespeichert. name ist der Dokumenttyp-Name und config ist der Inhalt der Konfigurations-Datei. DtdTable vom Typ dtd Feldname Feldtyp own_id id_type name varchar(128) config clob

Beschreibung Eindeutiger Bezeichner des Datenbankobjektes dtd Der Name des Dokumenttyps der DTD Konfiguration der zugehörigen DTD

EtypeTable : In dieser Tabelle werden die einzelnen Elementtypen gespeichert. name ist der Elementtyp-Name, der zusammen mit dtdref eindeutig wird. dtdref ist die Referenz auf die entsprechende DTD. Die Definition des Elementtyps ist mit contentmodel in der Tabelle

Seite 18t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS repräsentiert. pcdataindexed gibt an, ob für diesen Elementtyp ein PCDATA-Index angelegt ist. EtypeTable vom Typ etype Feldname Feldtyp own_id id_type name varchar(128) contentmodel lvarchar dtdref id_type pcdataindexed boolean

Beschreibung Eindeutiger Bezeichner des Datenbankobjektes etype Der Name des Elementtyps Das Contentmodel des Elementtyps Die oid der zugeörigen DTD Flag, ob der Elementtyp im PCDATA-Index ist oder nicht

Die folgenden drei Tabellen vom Typ docElem, nonFlatElem und flatElem stehen in Beziehung zu einander. Wie in Abbildung 4.4-6 zu erkennen ist, sind die Typen nonFlatElem und flatElem, Erben vom Typ docElem. In den entsprechenden Tabellen werden jedoch nur die Felder beschrieben, die diese Typen nicht gemeinsam haben.

Ist vom Typ

Ist vom Typ

docElem

flatElem Abbildung 4.4-6 :

nonFlatElem

Das Vererbungsverhältnis zwischen docElem, nonFlatElem und flatElem.

DocElemTable : In diese Tabelle werden die Felder doc, up, succ, pred, aller Dokument-Elemente gespeichert. doc ist eine Referenz auf das Dokument-Objekt, das in der DocumentTable gespeichert ist. up hat als Inhalt die oid des logischen Vater-Elements und in succ bzw. pred sind die oids des logischen Vorgängers bzw. Nachfolgers gespeichert. DocElemTable vom Typ docElem Feldname Feldtyp Beschreibung own_id id_type Eindeutiger Bezeichner des Datenbankobjektes docElem doc id_type Die oid des Dokumentes up id_type Die oid des Vater-Elements succ id_type Die oid des Nachfolger-Elements pred id_type Die oid des Vorgänger-Elements NonFlatElemTable : Diese Tabelle enthält für die strukturierten Dokument- Elemente zusätzlich (zur DocElemTable) die Felder down und etName. down ist die oid des ersten Sohnes und etName der Name des Elementtyps.

Seite 19t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS NonFlatElemTable vom Typ nonFlatElem + docElem Feldname Feldtyp Beschreibung down id_type Die oid des am weitesten linken Sohnes etName varchar(128) Der Name des Elements FlatElemTable : Diese Tabelle enthält für die flachen Dokument-Elemente zusätzlich (zur DocElemTable) das Feld flat, welches einen großen Text als Inhalt hat und in dem mehrere flache Dokument-Elemente zusammengefaßt abgespeichert werden. FlatElemTable vom Typ flatElem + docElem Feldname Feldtyp Beschreibung flat clob Der Text (bis 4 GB) des flachen Elementes AttRecTable : Hier werden die Attribute der strukturierten Dokument- Elemente gespeichert. element ist dann die oid des strukturierten Dokument-Elements und name, value beinhaltet dann den Text des Attribut-Namens und –Wertes AttrRecTable vom Typ attRec Feldname Feldtyp element id_type name varchar(128) value varchar(128)

Beschreibung Die oid des Elements Der Name des Attributes des Elementes Der Attributwert des Attributs

AttribIndexTable : attrName und attrValue sind Name und Wert des Attributs, die zu dem Elementtyp mit der oid elementType gehören. In positions sind dann die Index-Einträge abgelegt. Ein Index-Eintrag ('indexValue') besteht aus der oid des Dokument-Elements und der Anzahl des Auftretens innerhalb des Datenbankobjektes. Handelt es sich bei dem Datenbankobjekt um ein strukturiertes Dokument-Element, wird als Anzahl -1 angegeben. AttribIndexTable vom Typ attribIndex Feldname Feldtyp Beschreibung elementType id_type Die oid des Elementtyps für den Index attrName varchar(128) Der Name des Attributes für den Index attrValue varchar(128) Der Attributwert für den Index positions setof(indexValue) Index-Eintrag : oid des Elements | Anz.-Auftreten StructIndexTable : Der strukturierte Index besteht aus einem externen Elementtyp und einem internen Elementtyp und dem Inhalt des internen Elements, content. Der externe/interne Elementtyp wird in dieser Tabelle durch die Referenzen extElemType/intElemType repräsentiert. extElemType/intElemType sind die oids der entsprechenden Elementtypen. positions ist wie oben beschrieben.

Seite 20t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS StructIndexTable vom Typ structIndex Feldname Feldtyp Beschreibung extElemType id_type Die oid des äußeren Elementtyps für den strukt. Index intElemType id_type Die oid des inneren Elementtyps für den strukt. Index content varchar(128) Der Text-Inhalt des inneren Elementes für den Index positions setof(indexValue) Index-Eintrag : oid des Elements | Anz.-Auftreten PCDATAIndexTable : Der PCDATA-Index besteht aus einer Referenz auf den Elementtyp, elementType, und dem Inhalt des Elements, content. positions ist wie oben beschrieben. PCDATAIndexTable vom Typ pcdataIndex Feldname Feldtyp Beschreibung ElementType id_type Die oid des für den PCDATA-Index Content varchar(128) Der Text-Inhalt des Elementes für den Index Positions setof(indexValue) Index-Eintrag : oid des Elements | Anz.-Auftreten In Abbildung 4.4-7 wird ein Zusammenspiel der oben beschriebenen sechs Tabellen skizziert, die direkt mit der Dokumentspeicherung zu tun haben. In der DocumentTable wird der Name und eine Referenz auf die entprechende DTD gespeichert. Diese DTD wird in der DTDtable repräsentiert. In dieser DTDtable wird der Dokumenttyp-Name gespeichert, sowie die Menge der entsprechenden Elementtypes und die Konfiguration. Normalerweise werden die Elemente eines Dokuments in vier Tabellen aufgeteilt. (DocElemTable, NonFlatElemTable, AttrRecTable und FlatElemTable). FlatElemTable flat "Text zu Elem1" "Text zu Elem4" "Text zu Elem6" "Text zu Elem8" "Text zu Elem10"

NonFlatElemTable down etName 1 "E0" 3 "E2" 4 "E3" 6 "E5" 8 "E7" 10 "E9"

Abbildung 4.4-7:

4.5

DocElemTable own_id doc up succ pred 0 1 1 1 0 2 2 3 2 2 5 4 2 3 5 2 2 7 3 6 2 5 7 2 2 5 8 2 7 9 3 10 3 9 -

DocumentTable own_id name dtdref 1 "Dok1" 2 2 "Dok2" 1 3 "Dok3" 1

attrRecTable element name 2 Attr2 3 Attr3

root 0 2 9

value AW2 AW3

DocumentTable own_id name etypes config 1 "DTD1" {...} "...." 2 "DTD2" {...} "...." 3 "DTD3" {...} "...."

Zusammenspiel der Tabellen, die zur Speicherung der Dokumente beteiligt sind.

Der SGML-Parser : SP Im diesem Unterkapitel wird der Parser selbst, sowie seine Parameter anhand von

Beispielen beschrieben. Ebenso wird ein Überblick geliefert, welche Klassen bzw. Sourcecode-Dateien extra für diese Arbeit implementiert wurden.

Seite 21t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 4.5.1 Beschreibung des SP Der SP (SGML-Parser) wird zur Überprüfung und Einfügung von SGML-Dokumenten bezüglich ihrer DTD benutzt. Man kann auch eine DTD ohne ein Dokument parsen. Der SP geht bei dieser Überprüfung, sowohl auf den Syntax, wie auf die Grammatik ein. Fehler werden angezeigt. Neben der Fehlermeldung steht noch die Koordinate, bei der dieser Fehler aufgetreten ist. Wird die Option zum Einfügen gewählt, werden alle korrekt geparsten Dokument-Elemente in die Datenbank eingefügt. Die Konfigurations-Datei bestimmt hierbei, welche Elemente flach und welche strukturiert eingefügt werden sollen. Beim Einfügen werden SGML-Index-Strukturen generiert. Die Information, für welche Elemente ein Index angelegt werden soll, ist in der SuperDTD-Instanz, die sich in der Datenbank befindet, enthalten. Der Name des SP-Programmes ist „nsgmls“. Die Optionen, die dabei in der Komandozeile

eingegeben

werden

sind

"-x"

"-y"

und

"-X".

Die

C++-Dateien

elementOutput.cxx (SuperDTD-Instanz-Erstellen) und ModFuncs.cxx (DB-Einfügen) sind speziell für die diese Zwecke entwickelt worden. ModFuncs.cxx wird dabei von dem Parser benutzt und ruft die Schnittstellenfunktionen von der ESQL/C-Datei functions.ec auf.

Seite 22t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

4.5.2 Benutzung des SP Im Folgenden gibt es eine genaue Beschreibung der Parameter von 'nsgmls': Die Option "-x " Funktion :

Das Dokument mit dem Namen Dokument-Name (kompletter Pfad) wird geparst und in die Datenbank eingefügt. Die KonfigurationsDatei ist dabei der Name der Datei (kompletter Pfad), in der alle Namen der Dokument-Elemente zeilenweise stehen, die strukturiert abgespeichert werden sollen.

Beispiel :

nsgmls -y SGML-DB -x /sample/config /sample/hamlet.sgml Das Dokument hamlet.sgml wird unter der Konfiguration in config in die Datenbank SGML-DB eingefügt.

Die Option "-X Funktion :

Das Dokument mit dem Namen Dokument-Name (kompletter Pfad) wird geparst und von der dazugehöhrenden DTD wird eine SuperDTD-Instanz erstellt. Der Name der Instanz besteht dann aus dem Dokumenttypnamen plus Zusätze.

Beispiel :

nsgmls -X /home/sample/hamlet.sgml Das Dokument hamlet.sgml ist vom Dokumenttyp "PLAY" . Somit wird die SuperDTD-Instanz mit dem Namen "SDTDi_PLAY" erstellt.

Die Option "-y ....." Funktion :

Beim Einfügen muß man die Datenbank angeben. DB-name ist der Name der gewälten Datenbank.

Beispiel :

nsgmls -y ius_sgml –x cfg hamlet.sgm Ein Dokument mit dem Namen hamlet.sgm und der Konfiguration cfg wird mit diesem Befehl in die Datenbank ius_sgml eingefügt.

Seite 23t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 4.6

Ablauf der Datenbankorganisation In diesem Unterkapitel wird die Datenbankorganisation diskutiert. Dabei sind die

Stationen, im einzelnen, das Erstellen der Datenbank, das Einfügen eines Dokuments (und dessen Vorbereitungen) und schließlich das Abfragen von Daten. 4.6.1 Erstellen der Datenbank-Tabellen und -Typen Zum Erstellen und Initialisieren der Datenbank-Tabellen und –Typen, existieren SQLSkripte, die mit Hilfe von dem 'Utility' dbaccess aufgerufen werden können. Es handelt sich hierbei um die Skripte : create.sql, inits.sql und delete.sql. 

create.sql erstellt alle Datentypen, die in der Datenbank verwendet werden sowie alle Tabellen.



inits.sql initialisiert die Tabellen mit Null-Werten und richtet auch die notwendigen Elementtypen sowie die DTD-Referenzobjekte ein.



delete.sql löscht alle Datentypen, Tabellen und deren Inhalte. Dieses Skript ist hauptsächlich zur Behandlung von Updates, die auch Tabellendesign oder Datentypen betreffen.

Zum Erstellen des SGML-DataBlades wird die 'library' sgml_server.so kompiliert und mit dem SQL-Skript func.sql werden die Funktionen in die Datenbank eingefügt. Die Skripte create.sql und inits.sql sind im Anhang C und D aufgelistet.

Seite 24t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

4.6.2 Ablauf : Einfügen eines Dokumentes Das Einfügen eines Dokumentes in die Datenbank wird in der illustriert. SGMLDTD

Abbildung 4.6-8

SGMLSDTD-Instanz

SP

Benutzer

SDTD-Instanz als Dokument in DB

SGMLDokument

SGMLDokument in DB

SP KonfigurationsDatei

Abbildung 4.6-8:

modifizierte SGMLSDTD-Instanz

SP

SGMLDTD

Ablaufdiagramm - Einfügen eines SGML-Dokuments in die Datenbank.

Als Vorbereitung wird aus der SGML-DTD des Dokumentes eine SuperDTD-Instanz generiert. Dieses Dokument enthält im wesentlichen alle Informationen aus der DTD, plus zusätzliche Informationen, die die Erstellung der Indizes betrifft. Diese Generierung wird mit Default-Werten durch den SGML-Parser durchgeführt. Um die drei Indexstrukturen zu bestimmen, werden entsprechende Einträge durch den Benutzer in die Super-DTD-Instanz eingetragen. Im wesentlichen handelt es sich um Attribute der entsprechenden Super-DTDInstanz-Elemente . Im Dokumentelement vom Typ <ELEM> gibt es das Attribut ELEMINDEX, das als Attributwert 'Y' oder 'N' annehmen kann. Ist der Attributwert 'Y', dann wird ein Index für PCDATA angelegt, daß heißt, ein Indexeintrag enthält die Elementtyp-Id, den entsprechenden Dokument-Elements und die Positionen, bei denen der Inhalt auftritt. Falls der Attributeintrag 'N' entspricht, wird kein Index erstellt. Ein weiteres Attribut trägt den Namen

Seite 25t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS STRUCTINDEXED und enthält alle Elementtyp-Namen, für die ein strukturierter Index angelegt werden soll. ELEMNAME ist der Name des externen Elementtyps und in STRUCTINDEXED befinden sich alle Namen der internen Elementtypen. Ein Indexeintrag enthält die Elementtyp-Id des externen und des internen Elementtyps, sowie den Inhalt des internen Dokument-Elements und eine Menge aller Positionen, bei denen der Inhalt auftritt. Beispiel : SuperDTD-Instanz-Zeile : <ELEM

elemName="NAME"..ELEMINDEX='Y'

STUKTINDEX='VORNAME,...' ...> Dokument-Zeilen : Michael Fuchs PCDATAIndex-Instanz : [ET-Id_von(NAME), "Michael Fuchs", {("10|-1"),("15|2")}] Um den eindeutigen Elementtyp zu bestimmen, wird die oid des Elementtyps im Index verwendet. In diesem Beispiel handelt es sich um die oid des Elementtyps NAME. Der Inhalt "Michael Fuchs" kommt im strukturierten Element mit der Position 10|-1 vor und in dem flachen Dokument-Element, mit der oid 15, zweimal vor. structIndex-Instanz : [ET-Id_von(NAME),ET-Id_von(VORNAME), "Michael ", {(10,-1)}] Das

Gleiche,

was

für

die

PCDATAIndex-Instanz

gilt,

gilt

auch

für

die

structIndex-Instanz. Der Inhalt eines Elementes ist aber nur die erste Bedingung für den Index.

Seite 26t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Das Element, das "Michael" beihalten soll und vom Elementtyp VORNAME ist, muß auch noch in einem Element vom Typ NAME enthalten sein. Ein weiterer Elementtyp in der SuperDTD-Instanz ist . Hier ist das Attribut ATTRINDEX für den Attribut-Index verantwortlich. Hat es den Attributwert 'Y', dann wird eine Index-Instanz angelegt, die die oid, sowie den Attribut-Name und den AttributWert des entsprechenden Elementtyps enthält und ebenso die Positionen, bei denen dieses Attribute-Paar auftritt. Ist der Attributwert 'N', wird kein Index angelegt. Beispiel : SuperDTD-Instanz-Zeilen : <ELEM elemName="NAME"..>
attName='NACHNAME' ...attrIndex='Y'..... rel="nofollow">

Dokument-Zeile : .... AttribIndex-Instanz : [ET-Id_von(NAME), "NACHNAME", "Fuchs ",{("10|-1"),("15|2")}] Die AttribIndex-Instanz hat, verglichen mit der structIndex-Instanz, andere Bedingungen, die für "Fuchs" herrschen. "Fuchs" ist hier ein Attributwert vom Attribut NACHNAME und gehört zu einem Element vom Typ NAME. Ein Beispiel für eine DTD mit der zugehörigen SuperDTD-Instanz ist im Anhang A beigefügt.

Seite 27t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

4.6.3 Aufrufen der Funktionen Die Funktions-Einbindung kann Beispielsweise folgendermaßen geschehen:



execute function hasAttrValueRegex("4|0","TABLES","N?N*"); In diesem Beispiel wird die DataBlade-Funktion hasAttrValueRegex aufgerufen und das

Ergebnis wird in die vorher ausgewählte Ausgabe übergeben. Die Eingabe-Parameter sind alle vom Typ char(128). Als Rückgabe bekommt man den int-Wert 1, falls das Attribut TABLES im Element mit der Position 4|0 den regulären Ausdruck N?N* enthält, sonst 0.



select getDocNamebyOid(doc) from FlatElemTable where isInside(own_id,"Michael Fuchs") Dieses SQL-Statement bindet eine DataBlade-Funktion in die 'where-clause' und eine

DataBlade-Funktion in die 'select-clause' ein. Berechnet werden alle Dokument-Namen, die in irgendeinem flachen Dokument-Element "Michael Fuchs" beinhalten. own_id und doc sind Felder aus der FlatElemTable.

Seite 28t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

5 IUS- Schnittstellen-Funktionen Das Kapitel fünf beschäftigt sich mit den Funktionen, die als Schnittstelle für das objektrelationale Datenbanksystem fungieren. Die Auflistung ist in drei Teile untergliedert. Der erste Teil (5.1) befaßt sich mit den Funktionen, die zum SP gehören. Sie sind in der Sprache C++ verfaßt und rufen im wesentlichen ESQL/C Funktionen auf. Diese ESQL/C-Funktionen werden im zweiten Teil (5.2) aufgelistet. Im dritten Teil (5.3) gibt es eine Darstellung aller Funktionen, die in API/C implementiert und teilweise als DataBlade-Funktionen in die Datenbank integriert wurden. 5.1

IUS-SP Schnittstellen-Funktionen : SGML-Parser-Modul Dieses Unterkapitel listet alle Funktionen auf, die in der C++-Datei ModFuncs.cxx

implementiert sind. Diese Funktionen werden direkt während des Parsens vom SP aufgerufen, um DTD-konforme Dokument-Komponenten, direkt in die Datenbank einzufügen oder entsprechende Vorbereitungen dafür zu treffen. Die Funktionen selbst rufen dann wieder ESQL/C-Funktionen auf, die im darauffolgenden Unterkapitel beschrieben werden. Diese externen Funktionsaufrufe werden in der Funktionsbeschreibung mit "" und kursiv dargestellt. 5.1.1 SP- Funktionen, die ESQL/C-Funktionen aufrufen (Sprache : C++) int daiInterInit(char * docName, char * dtdName, char* isFragment, char* OIDUp, char* OFFUp, char* OIDLeft, char* OFFLeft,char* OIDRight,char* OFFRight) Funktion Herstellen der Verbindung zur Datenbank  make_connection, ein Dokument-Datenbankobjekt mit dem Namen docName erstellen und die SuperDTD-Instanz von der DTD mit dem Namen dtdName auslesen und Index Abfragestrings erstellen  create_doc.

Seite 29t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

Rückgabewert Beispiel

IsFragment, OIDUp, OFFp, OIDLeft, OFFLeft, OIDRight, OFFRight werden zum derzeitigen Implementierungsstand nicht genutzt. 0: Dokument-Objekt erfolgreich angelegt -1: Fehler ist aufgetreten daiInterInit("hamlet.sgm","PLAY",NULL,...,NULL,NULL)

void daiInterClose() Funktion Aufrufen der zum Schließen der Verbindung zur Datenbank  close_connection Rückgabewert Keiner void daiInterStartTag(char * elemName) Funktion Das Dokument-Element mit dem Namen elemName wurde mit dem Starttag geöffnet. Dabei wird entschieden, ob dieses Dokument-Element in ein flaches oder strukturiertes Datenbankobjekt gespeichert wird. Soll elemName strukturiert gespeichert werden, wird es mit  createStructElem angelegt und mit  subInsertElem in die logische Datenbankstruktur eingefügt. (Spezialfall: Die Dokument-Wurzel wird mit  insertRoot eingefügt). Soll das Element elemName flach gespeichert werden, wird es an den flachen Teil angefügt. (Sonderfall : Das Dokument-Element ist das erste Element im flachen Teil  ein neuer flacher String wird angelegt ) Rückgabewert Keiner Beispiel daiInterStartTag("ACT") void daiInterEndTag(char *elemName) Funktion Das 'Endtag' des Dokument-Elementes mit dem Namen elemName ist erreicht. Wenn es sich um ein strukturiertes Element handelt, wird es vom internen Elementstack genommen. Wenn zu diesem strukturierten Element ein flaches Vorgänger-Element existiert, wird der gesamte flache Teil gespeichert  createStructElem + subInsertElem. Handelt es sich aber bei dem Element elemName um ein flaches Element, wird dieses an den flachen Teil angehängt. Dabei wird der strukturierte Index aufgebaut  shouldStrPCDATAIndexed + insertInStrPCDATAIndex Rückgabewert Keiner Beispiel daiInterEndTag("ACT") void daiInterBeginTagClose() Funktion Eine Spezialbehandlung für 'Starttags' mit fehlendem 'Endtag'. Das 'Endtag' wird zugefügt. Dies entspricht dem Prinzip des Vorrausparsens. Rückgabewert Keiner void daiInterAttr(char * attrName, char * attrVal, char * attrType) Funktion Das Attribut mit dem Namen attrName und dem Wert attrVal wird im strukturierten Falle als Datenbankobjekt angelegt  insertStructAttribs oder im flachen Fall an den Starttag-Namen angefügt. Dabei wird der Atribut-

Seite 30t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

Rückgabewert Beispiel

Index aufgebaut  insertInAttribIndex. attrType wird zum momentanen Zeitpunkt nicht berücksichtigt. Keiner daiInterAttr("NAME","Fuchs",NULL)

void daiInterPcdataStr(char * str) Funktion Der PCDATA-Teil mit dem Text-Pointer str wird als eigenes Datenbankobjekt angelegt  createStructElem (statt dem Element-Namen, wird „flat“ als Parameter übergeben) und gespeichert  subInsert, oder dem flachen Teil zugefügt. Dabei wird der PCDATA-Index aufgebaut -> insertInPCDATAIndex. Rückgabewert Keiner Beispiel daiInterPcdataStr("Dies ist der Inh. eines PCDATA-Elements") void getConfig(char *Filename) Funktion das Config-File mit dem Namen Filename, das alle Element-Namen enthält, dessen Elemente strukturiert gespeichert werden sollen, wird ausgelesen und von den Namen wird eine Tabelle im Hauptspeicher für isFlat erstellt. Rückgabewert Keiner Beispiel getConfig("/home/fuchs/samples/config_for_PLAY") int isFlat(char *elemName) Funktion Aus der im Hauptspeicher befindlichen Tabelle der strukturierten Elemente wird ermittelt, ob das Element mit dem Namen elemName flach oder strukturiert in die Datenbank gespeichert werden soll. Rückgabewert 0 : elemName ist strukturiert (in der Tabelle enthalten) 1 : elemName ist flach Beispiel isFlat("SCENE") 5.2

IUS-SP Schnittstelle als ESQL/C-Modul Im folgenden Unterkapitel werden die Funktionen beschrieben, die in ESQL/C-Datei

functions.ec implementiert sind. Diese Funktionen bilden die eigentliche Schnittstelle zwischen SP und IUS. Es wurde dabei eine Unterteilung in Funktionskategorien vorgenommen. Im Einzelnen geht es um Funktionen, die sich mit der Client-Server-Verbindung befassen, die zum Generieren der Datenbank sowie der Indizes benutzt werden. Das Schnittstellenmodul benötigt natürlich auch einige Abfragefunktionen. 5.2.1 Funktionen zum Aufbauen einer Client-Verbindung int make_connection(char* conn_name_p) Funktion Errichten einer Verbindung zur Datenbank conn_name_p. Rückgabewert 1: Verbindung wurde erfolgreich aufgebaut 0: Fehler ist aufgetreten Beispiel make_connection("sgml_db@athen")

Seite 31t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS int close_connection() Funktion Schließt die aktuelle Verbindung zur Datenbank. Rückgabewert Keiner 5.2.2 Funktionen zum Generieren der Datenbank documentRef createDoc(char* p_name, char* p_DTDname) Funktion Erstellt ein Dokument-Objekt mit dem Namen p_name und eine DTDReferenz zu der DTD mit dem Namen p_DTDname, liest die zu dieser DTD gehörende SuperDTD-Instanz aus und erstellt einen String zur Abfrage, welches Element für einen Index in Frage kommt (AttribIndex, PCDATAIndex oder StrPCDATAIndex) Rückgabewert oid: Dokument-Objekt -1: Fehler ist aufgetreten Beispiel createDoc("hamlet.sgm","PLAY") int insertRoot(documentRef p_doc, docElemRef p_elem) Funktion Erstellt ein Element-Datenbank-Objekt mit der oid p_elem und macht beim Dokument-Datenbank-Objekt mit der oid p_doc, p_elem zum WurzelElement Rückgabewert 1: Wurzel-Element wurde erfolgreich angelegt 0: Fehler ist aufgetreten Beispiel createDoc(2,4) docElemRef createStructElem(char* p_text, documentRef p_doc) Funktion Falls p_text  "flat" wird ein Element-Datenbank-Objekt in der nonFlatElemTable mit dem Namen p_text erstellt. Falls p_text = "flat" wird ein Element-Datenbank-Objekt in der flatElemTable. Das Datenbank-Objekt bekommt eine Referenz auf das Dokument-Objekt mit der oid p_doc Rückgabewert oid: Dokument-Objekt -1: Fehler ist aufgetreten Beispiel createStructElem("ACT",4) int setFlatContent(docElemRef p_elem, char* p_text) Funktion In das flache Datenbank-Objekt mit der oid p_elem wird der Text p_text gespeichert. Rückgabewert 1: erfolgreiches Update des flachen Datenbank-Objekts -1: Fehler ist aufgetreten Beispiel setFlatContent(5,"Dies ist ein Inh eines PCDATA-Elems") int setStructAttrVal(docElemRef p_elem, char* p_name, char* p_value) Funktion Fügt ein strukturiertes Attribut-Objekt in die Datenbank ein, mit der Referenz p_elem auf das strukturierte Dokument-Element, dem Attribut-Name p_name und dem Attribut-Wert p_value. Rückgabewert oid: Attribut- Datenbank- Objekt -1: Fehler ist aufgetreten Beispiel setStructAttrVal(4,"NAME","Fuchs")

Seite 32t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS int subInsert(docElemRef p_son, docElemRef p_parent) Funktion Fügt ein strukturiertes Dokument-Element p_son in die Datenbank ein. Dabei wird es , vom logischen her gesehen, als ganz rechter Sohn von p_parent eingefügt Rückgabewert oid: Attribut-Datenbank-Objekt -1: Fehler ist aufgetreten Beispiel setStructAttrVal(6,4) 5.2.3 Funktionen zum Generieren der Indizes void getSDTDattribs(char *DTD_param) Funktion Erstellt die drei Index-Strings von der SuperDTD-Instanz, die von der DTD mit dem Namen DTD_param abstammt. Diese Index-Strings sind für die Abfragefunktionen : shouldStructIndexed, shouldAttrIndexed, shouldPCDATAIndexed. Rückgabewert Keiner Beispiel getSDTDattribs("PLAY") int shouldStructIndexed(char *exName,char *inName) Funktion Ermittelt, ob für die Strukturbeziehung der zwei Elementtypen mit dem Namen exName und inName ein Index angelegt werden soll. Dabei wird der erstellte String von getSDTDattribs benutzt. Rückgabewert 1: Index soll angelegt werden 0: Index soll nicht angelegt werden. Beispiel shouldStructIndexed("ACT","ACTTITLE") int shouldAttrIndexed(char *etName,char *p_name) Funktion Ermittelt, ob für das Attribut mit dem Namen p_name vom Elementtyp mit dem Namen etName ein Index angelegt werden soll. Dabei wird der erstellte String von getSDTDattribs benutzt. Rückgabewert 1: Index soll angelegt werden 0: Index soll nicht angelegt werden. Beispiel shouldAttrIndexed("NAME","Nachname") int shouldPCDATAIndexed(char *etName) Funktion Ermittelt, ob für den Elementtyp mit dem Namen etName ein Index angelegt werden soll. Dabei wird der erstellte String von getSDTDattribs benutzt. Rückgabewert 1: Index soll angelegt werden 0: Index soll nicht angelegt werden. Beispiel shouldPCDATAIndexed("ACTTITLE") int createAttrIndex(docElemRef etype, char* p_name) Funktion Legt für das Attribut mit dem Namen p_name vom Elementtyp mit der oid etype einen Index an, falls dieser nicht existiert. Rückgabewert 1: Index existiert 0: Index existierte nicht und wurde erstellt Beispiel createAttrIndex(getElem("NAME"),"Nachname")

Seite 33t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS int createStructIndex(docElemRef exEtype, docElemRef inEtype) Funktion Legt für die Struktur der Elementtypen mit der externen Element-oid exEtype und der internen Element-oid inEtype einen Index an, falls dieser nicht existiert. Rückgabewert 1: Index existiert 0: Index existierte nicht und wurde erstellt Beispiel createStructIndex(getElem("ACT"),getElem("ACTTITLE")) int createPCDATAIndex(docElemRef etype) Funktion Legt für den Elementtyp mit der oid etype einen Index an, falls dieser nicht existiert. Rückgabewert 1: Index existiert 0: Index existierte nicht und wurde erstellt Beispiel createPCDATAIndex(getElem("ACTTITLE")) int InsertInAttribIndex(docElemRef etype, char* p_name, char* p_value, docElemRef p_elem) Funktion Legt für das Attribut mit dem Namen p_name von dem Element-Typ mit der Elementtyp-oid etype den Indexeintrag mit dem Attributwert p_value und der Dokument-Element-oid p_elem an. Rückgabewert 1: erfolgreich angelegt -1: Fehler ist aufgetreten Beispiel InsertInAttribIndex(getElem("NAME"),"Nachname","Fuchs",8)) int InsertInStrPCDATAIndex(docElemRef exEtype, docElemRef exEtype, char* p_value, docElemRef p_elem) Funktion Legt für die Elementtyp Beziehung mit der externen Elementtyp-oid exEtype und die interne Elementtyp-oid inEtype den Indexeintrag mit dem Text p_value und der Dokument-Element-oid p_elem an. Rückgabewert 1: erfolgreich angelegt -1: Fehler ist aufgetreten Beispiel InsertInStrPCDATAIndex(getElem("ACT"),getElem("ACTTITLE"), "ACT IV",9)

int InsertInPCDATAIndex(docElemRef etype, char* p_value,docElemRef p_elem) Funktion Legt für den Elementtyp mit der oid etype den Indexeintrag mit dem Text p_value und der Dokument-Element-oid p_elem an. Rückgabewert 1: Erfolgreich angelegt 0: Fehler ist aufgetreten Beispiel InsertInPCDATAIndex(getElem("ACTTITLE"),"ACT IV",9)

Seite 34t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

5.2.4 Informations- und Navigations-Hilfsfunktionen int getElem(char *p_name) Funktion Liefert die oid des Elementtyps mit dem Namen p_name Rückgabewert oid: Elementtyp -1: nicht existent Beispiel getElem("ACT") int getETName(docElemRef etype) Funktion Liefert die Namen des Elementtypes mit der oid etype Rückgabewert Name: Elementtyp "": nicht existent Beispiel getETName(5) docElemRef physGetUp(docElemRef p_elem) /* Version ESQL */ Funktion Liefert die oid des Vaters vom Dokument-Element mit der oid p_elem Rückgabewert oid: Vater -1: nicht existent Beispiel physGetUp(8)

Seite 35t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

5.3

SGML-API-Funktionen (API=Aplication Program Interface) Das letzte Unterkapitel beschreibt die Funktionen, die auf der Server-Seite zur

Behandlung der Daten in IUS zuständig sind. Bei diesen Funktionen handelt es sich, sowohl um erweiterte SQL-Funktionen, die mit 'execute function', direkt in SQL aufgerufen werden, als auch um Funktionen, die nur als Hilfsfunktionen dienen und in der Library sgml_server.so zur Verfügung stehen. Zuerst werden die speziellen Abfrage-Funktionen genannt. Anschließend folgen zwei Augabefunktionen, gefolgt von Navigations- und Informations-Funktionen für Dokumente und deren Elemente. Die letzten Auflistungen zeigen dann Funktionen, die speziell für strukturierte bzw. flache Elemente implementiert wurden. Alle Parameter vom Datentyp mi_lvarchar* werden in den Beispielen zur Vereinfachung als einfacher "String" dargestellt. Um eine Library-Funktion mit einem solchen Datentyp zu behandeln, müßte man die Funktion mi_lvarchar_to_string( ) bzw. mi_string_to_lvarchar( ) zum Konvertieren verwenden. Die genauen Definitionen befinden sich im Handbuch [INF97]. 5.3.1 Spezielle Abfrage-Funktionen Im Folgenden werden die Funktionen für spezielle Queries und Werte-Bestimmung aufgelistet. mi_lvarchar *getAttrValue(position elem_pos, mi_lvarchar *pattName) Funktion Ermittelt den Attributwert von dem Element mit der Position elem_pos und dem Attribut mit dem Namen pattName Rückgabewert Attributwert "" nicht existent Beispiel execute function getAttrValue("10|100","Nachname") Bemerkung

Die Position in dem obigen Beispiel wird als String übergeben und entspricht dem Paar von zwei Integer-Werten, 10 und 100. Die Transformation von String zu 'Integer|Integer' wird jeweils in der Funktion übernommen. Der erste Integer-Wert entspricht der oid und der zweite entspricht dem Offset in dem flachen Element. Wenn das Element nicht flach ist, ist der Offset : -1.

mi_integer

hasAttrValue(position elem_pos,mi_lvarchar *pattName, mi_lvarchar *pattValue) Funktion Ermittelt von dem Element mit der Position elem_pos und dem Attribut pattName, ob der betreffende Attributwert gleich pattValue ist. Rückgabewert 1: Abfrage ist wahr 0: sonst Beispiel execute function hasAttrValue("10|100","Nachname","Fuchs")

Seite 36t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS mi_integer

hasAttrValueRegex(position elem_pos,mi_lvarchar *pattName, mi_lvarchar *pattRegEx) Funktion Ermittelt von dem Element mit der Position elem_pos und dem Attribut pattName, ob pattRegEx ein regulärer Ausdruck von dem betreffenden Attributwert ist. Rückgabewert 1: Abfrage ist wahr 0: sonst Beispiel execute function hasAttrValueRegex("10|100","Nachname","?u*") mi_integer Funktion

hasTextualContent(position elem_pos,mi_lvarchar *text) Ermittelt von dem Element mit der Position elem_pos, ob dessen Inhalt text entspricht. Rückgabewert 1: Abfrage ist wahr 0: sonst Beispiel execute function hasTextualContent("10|200","ein Bsp-Inhalt") mi_integer Funktion

hasTextContRegex(position elem_pos,mi_lvarchar *RegEx) Ermittelt von dem Element mit der Position elem_pos, ob RegEx ein regulärer Ausdruck von dessen Inhalt ist. Rückgabewert 1: Abfrage ist wahr 0: sonst Beispiel execute function hasTextualContentRegex("10|200","^ein?B*") mi_lvarchar *getETName(position elem_pos) Funktion Ermittelt den Namen des Elements mit der Position elem_pos Rückgabewert Element-Name "" : nicht exitistent Beispiel execute function getETName("10|200") mi_intege Funktion

isContainedIn(position son, position father) Ermittelt, ob das Element mit der Position son in dem Element mit der Position father, enthalten ist. Rückgabewert 1: Abfrage ist wahr 0: sonst Beispiel execute function isContainedIn("10|200","9|-1") In den folgenden Abfrage-Funktionen ist der Rückgabewert unter Vorbehalt ausgewählt worden. Zu dem Implementierungszeitpunkt dieser Arbeit, war der Datentyp clob der geeignetste. In Zukunft könnte man sich auch andere Datentypen zur Rückgabe vorstellen. Als Beispiel gäbe es die Möglichkeit, Datentypen wie collection oder file als Rückgabewert zu nutzen. MI_LO_HANDLE *getContaining(position elem_pos) Funktion Ermittelt alle Positionen der Elemente vom Dokument, in denen das Element mit Position elem_pos enthalten ist. Rückgabewert Text: alle Positionen als Zeilen NULL: Fehler ist aufgetreten Beispiel execute function isContainedIn("10|200")

Seite 37t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS MI_LO_HANDLE *getAll(position elem_pos,mi_lvarchar *pname) Funktion Ermittelt alle Positionen der Elemente mit dem Namen pname in preorder im betreffenden Dokument von der Position elem_pos an. Rückgabewert Text: alle Positionen als Zeilen NULL: Fehler ist aufgetreten Beispiel execute function getAll("8|-1","SCENE") MI_LO_HANDLE *getObjs(mi_integer pelem) Funktion Ermittelt alle Positionen der Elemente vom Elementtyp mit der oid pelem. Rückgabewert Text: alle Positionen als Zeilen NULL: Fehler ist aufgetreten Beispiel execute function getObjs(getETId("SCENE")) MI_LO_HANDLE Funktion Rückgabewert Beispiel

*getObjsByAttr(mi_integer pelem, mi_lvarchar *pattName, mi_lvarchar *pattVal) Ermittelt alle Positionen der Elemente vom Elementtyp mit der oid pelem, bei denen das Attribut pattName den Attributwert pattVal hat. Text: alle Positionen als Zeilen NULL: Fehler ist aufgetreten execute function getObjsByAttr(getETId("NAME"),"Nachname","Chen")

MI_LO_HANDLE Funktion Rückgabewert Beispiel

*getObjsByAttrWithRegEx(mi_integer *elem_name, mi_lvarchar *pattName, mi_lvarchar *pattRegEx) Ermittelt alle Positionen der Elemente vom Elementtyp mit der oid pelem, bei denen das Attribut pattName, pattRegEx ein regulärer Ausdruck für den Attributwert ist. Text: alle Positionen als Zeilen NULL: Fehler ist aufgetreten execute function getObjsByAttrWithRegEx(getETId("NAME"),"Nachname","?uch*")

MI_LO_HANDLE *getContentByPosition(mi_integer etype,mi_lvarchar *content) Funktion Ermittelt alle Positionen der Elemente vom Typ etype mit dem Inhalt content. Rückgabewert Text: alle Positionen als Zeilen (nur vom exitierenden Index) NULL: Fehler ist aufgetreten Bemerkung Die Funktion wurde zum Testen des PCDATA-Index implementiert, enthält aber zur Zeit keine vollständige Abfrage. Ist der entsprechende Index nicht vorhanden, wird ein Fehler gemeldet. MI_LO_HANDLE Funktion Rückgabewert Bemerkung

*getElemsByPosition(mi_integer exEtype, mi_integer inEtype, mi_lvarchar *content) Ermittelt alle Positionen der Elemente vom Typ inEtype mit dem Inhalt content, welche in Elementen vom Elementtyp exEtype enthalten sind. Text: alle Positionen als Zeilen (nur vom exitierenden Index) NULL: Fehler ist aufgetreten Die Funktion wurde zum Testen des strukturierten Index implementiert, enthält aber zur Zeit keine vollständige Abfrage. Ist der entsprechende Index nicht vorhanden, wird ein Fehler gemeldet.

Seite 38t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 5.3.2 Ausgabe-Funktionen MI_LO_HANDLE *getElemText(position elem_pos) Funktion Ermittelt den Inhalt des Elementes (mit Markup) mit der Position elem_pos. Rückgabewert Text: Element-Inhalt mit Markup NULL: Fehler ist aufgetreten Beispiel execute function getElemText("10|200") mi_lvarchar *getElemScreen(position elem_pos,mi_char **akt_pos,mi_char **stack) Funktion Ermittelt den Inhalt des Elementes (mit Markup) mit der Position elem_pos. Der Inhalt wird dabei auf eine voreingestellte Bildschirmgröße begrenzt. Die Position, bei der die maximale Zeilenanzahl erreicht worden ist, wird mit dem Zeiger akt_pos eingelesen und auch wieder zurückgeliefert. Dazu wird der Element-Stack mit dem Zeiger stack ausgelesen und wieder zurückgeliefert. Diese Funktion dient als Hilfsroutine zum bildschirmweisen Ausgeben eines großen Elementes. Die Zeiger akt_pos und stack müssen dabei zwischengespeichert und immer wieder übergeben werden. Rückgabewert Text: Element-Inhalt mit Markup (begrenzt auf Bildschirmgröße) NULL: Fehler ist aufgetreten Beispiel getElemScreen("10|200",&aktPos,&aktStack) 5.3.3 Funktionen zur Navigation im Dokument position Funktion

getRoot(position p_elem) Ermittelt die Position der Dokument-Wurzel von dem Dokument-Element mit der Position p_elem. Rückgabewert Position: Wurzel -1 : nicht existent Beispiel execute function getRoot("10|200") position Funktion

getRootbyDocName(mi_lvarchar *DocName) Ermittelt die Position der Dokument-Wurzel von dem Dokument mit dem Namen DocName. Rückgabewert Position: Wurzel -1 : nicht existent Beispiel execute function getRootbyDocName("hamlet.sgm") position Funktion

up(position elem_pos) Ermittelt die Position des Vater-Elementes von dem Dokument-Element mit der Position p_elem. Rückgabewert Position: Vater-Element -1: nicht existent Beispiel execute function up("10|200") position Funktion

down(position elem_pos) Ermittelt die Position des ersten Sohnes von dem Dokument-Element mit der Position p_elem. Rückgabewert Position: erster Sohn -1: nicht existent Beispiel execute function down("10|200")

Seite 39t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS position Funktion

succ(position elem_pos) Ermittelt die Position des Nachfolger-Elementes von dem DokumentElement mit der Position p_elem. Rückgabewert Position: Nachfolger-Element -1: nicht existent Beispiel execute function succ("10|200") position Funktion

pred(position elem_pos) Ermittelt die Position des Vorgänger-Elementes von dem Dokument-Element mit der Position p_elem. Rückgabewert Position: Vorgänger-Element -1: nicht existent Beispiel execute function pred("10|200") 5.3.4 Info-Funktionen über Dokumente, DTDs und Elemenenttypen mi_integer Funktion

getETStuff(mi_integer p_elem,mi_char **PName,mi_integer *PDTDid) Ermittelt den Namen und die DTD-oid des Elementtyps mit der oid p_elem und gibt sie im Pointer Pname bzw. PDTDid zurück. Rückgabewert 0: Ermittlung ergolgreich -1: Fehler ist aufgetreten Beispiel getETStuff(5,&resname,&resdtd) mi_integer Funktion

getETypeID(mi_lvarchar *PName,mi_integer PDTDid) Ermittelt die oid des Elementtypes mit dem Namen Pname und der DTD-oid PDTDid Rückgabewert oid: Elementtype -1: nicht existent Beispiel getETypeID("SCENE",2) mi_lvarchar *getETypeName(mi_integer p_elem) Funktion Ermittelt den Namen des Elementtyps mit der oid p_elem. Rückgabewert Name: Elementtyp "": nicht existent Beispiel getETypeName(5) mi_integer Funktion

getDoc(position p_elem) Ermittelt die oid des Dokuments von dem Dokument-Element mit der Position p_elem. Rückgabewert oid: Dokument "": nicht existent Beispiel execute function getDoc("10|200")

Seite 40t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS mi_integer Funktion

getDTD(position p_elem) Ermittelt die oid der DTD von dem Dokument-Element mit der Position p_elem. Rückgabewert oid: DTD "": nicht existent Beispiel execute function getDTD("10|200") mi_lvarchar *getAllContaining(mi_lvarchar *Doctype) Funktion Ermittelt für jeden Elementtyp vom Dokumenttyp Doctype die Menge aller indirekt oder direkt enthaltenen Elementtypen. Rückgabewert Elementtypen+Menge aller entahltenen Elementtypen "": nicht existent Beispiel execute function getAllContaining("PLAY") mi_lvarchar *getDTDFragment(mi_integer etype) Funktion Ermittelt die DTD, die benötigt wird um ein einzelnes Element vom Elementtyp mit der oid etype zu parsen. Rückgabewert DTDFragment "": nicht existent Beispiel execute function getDoc(getETypeID("SCENE",2)) 5.3.5 Funktionen speziell für strukturierte Elemente (Datenbank-Objekte) docElemRef physGetUp(docElemRef p_elem) Funktion Ermittelt den Vater des strukturierten Elements mit der oid p_elem. Rückgabewert oid: Vater -1: nicht existent Beispiel execute function physGetUp(11) docElemRef physGetDown(docElemRef p_elem) Funktion Ermittelt den 1. Sohn des strukturierten Elements mit der oid p_elem. Rückgabewert oid: ganz linker Sohn -1: nicht existent Beispiel execute function physGetUp(11) docElemRef physPred(docElemRef p_elem) Funktion Ermittelt den Vorgänger des strukturierten Elements mit der oid p_elem. Rückgabewert oid: Vorgänger -1: nicht existent Beispiel execute function physPred(11) docElemRef physSucc(docElemRef p_elem) Funktion Ermittelt den Nachfolger des Datenbank-Dokument-Elementes mit der oid p_elem. Rückgabewert oid: Vorgänger -1: nicht existent Beispiel execute function physSucc(11) mi_lvarchar *physName(docElemRef p_elem) Funktion Ermittelt den Name des strukturierten Elements mit der oid p_elem.

Seite 41t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Rückgabewert

Name: Datenbank-Dokument-Element "": nicht existent

Beispiel

execute function physName(11)

mi_lvarchar *getPhysAttribs(docElemRef p_elem) Funktion Ermittelt die Attribute als String des strukturierten Elements mit der oid p_elem. Rückgabewert Attribut-String "": nicht existent Beispiel execute function getPhysAttribs(11) docElemRef getNextObj(docElemRef p_elem,mi_char *elem_name ) Funktion Ermittelt, im Dokument, das nächste strukturierte Dokument-Element vom Element mit der oid p_elem, das den Namen elem_name trägt. Rückgabewert oid: nächstes, strukturiertes Element -1: nicht existent Beispiel execute function getNextObj(11,"ACT") 5.3.6 Funktionen speziell für flache Datenbank-Objekte mi_integer is_flat(docElemRef p_elem) Funktion Ermittelt , ob ein Dokument-Element mit der oid p_elem flach ist oder nicht Rückgabewert 0: Dokument-Element ist nicht flach 1: Dokument-Element ist flach Beispiel execute function is_flat(11) mi_integer *getFlatText(docElemRef elem_pos, mi_char **PPuffer) Funktion Holt den Text aus dem flachen Dokument-Element mit der oid elem_pos und legt das Ergebnis im String-Zeiger *PPuffer ab Rückgabewert Länge: Elementtext -1: nicht existent Beispiel getFlatText(11) docElemRef getNextFlatText(docElemRef p_elem,mi_lvarchar *pname, mi_lvarchar **pflat,mi_integer PDTDid) Funktion Holt den Text und die oid des nächsten flachen Dokument-Element von dem flachen Objekt mit der oid p_elem von der DTD mit der oid PDTDid, indem der Markup mit dem Namen p_name vorkommt. Die Puffer-Adresse des Textes wird dabei mit der Adresse *pflat zurückgeliefert. Rückgabewert oid: nächstes flaches Element -1: nicht existent Beispiel getNextFlatText(10,"SCENE",&restext,getDTD("10|0"))

Seite 42t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 5.3.7 Hilfs-Funktionen zur Navigation, speziell in flachen Textteilen mi_integer findBackward(mi_char *searchStr,mi_integer ofs,mi_char *whatStr) Funktion Sucht whatStr in searchStr rückwärts von der Zeichenposition ofs an. Rückgabewert Zeichenposition des gesuchten Strings -1: Suche erfolglos Beispiel findBackward("Zu Suchender Text",5,"Such") mi_integer findForward(mi_char *searchStr,mi_integer ofs,mi_char *whatStr) Funktion Sucht whatStr in searchStr vorwärts von der Zeichenposition ofs an. Rückgabewert Zeichenposition des gesuchten Strings -1: Suche erfolglos Beispiel findForward("Zu Suchender Text",5,"Such") mi_integer

findCorrespBackward(mi_char *FlatElem,mi_integer offset, mi_char *ElementTypeName) Funktion Sucht rückwärts in FlatElem nach dem Starttag mit dem Namen ElementTypeName, das zu dem Endtag mit dem Namen ElementTypeName an der Zeichenposition offset gehört. Rückgabewert offset: gefundenes Starttag -1 Fehler ist aufgetreten Beispiel findCorrespBackward("%~Text%~",9,"A") mi_integer

findCorrespForward(mi_char *FlatElem,mi_integer offset, mi_char *ElementTypeName) Funktion Sucht vorwärts in FlatElem nach dem Endtag mit dem Namen ElementTypeName, das zu dem Starttag mit dem Namen ElementTypeName an der Zeichenposition offset gehört. Rückgabewert offset: gefundenes Endtag -1 Fehler ist aufgetreten Beispiel findCorrespForward("%~Text%~",9,"A") mi_integer

getElementTypeName(mi_char *searchStr,mi_integer ofs, mi_char **ElementTypeName) Funktion Ermittelt in searchStr an der Stelle ofs den Namen und ob es sich um ein Starttag, Endtag oder kein tag handelt. Der Zeiger auf den resultierenden Namen wird mit dem Zeiger *ElementTypeName zurückgeliefert Rückgabewert 1: Name ist ein Starttag 0: Name ist kein tag -1: Name ist ein Endtag Beispiel getElementTypeName("%~Text",0,"Such")

Seite 43t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS mi_integer Funktion

testElemPos(mi_char *searchStr,mi_integer ofs) Ermittelt in searchStr an der Stelle ofs ob es sich um ein Starttag, Endtag oder kein tag handelt. Rückgabewert 1 Name ist ein Starttag 0 Name ist kein tag -1 Name ist ein Endtag Beispiel testElemPos("...%~Text...",15) mi_integer Funktion

testElemName(mi_char *searchStr,mi_integer ofs,mi_char *what) Ermittelt in searchStr an der Stelle ofs ob es sich bei what um ein Starttag, Endtag oder kein tag handelt. Rückgabewert 1: Name ist ein Starttag 0: Name ist kein tag -1: Name ist ein Endtag Beispiel testElemName("%~Text",0,"NAME") 5.3.8 Hilfs-Funktionen zur Abfrage, speziell in flachen Textteilen mi_integer Funktion

match(mi_char *pattern, mi_char *search) Ermittelt, ob der reguläre Ausdruck pattern in dem String search vorkommt. Rückgabewert 0: pattern ist kein regulärer Ausdruck in search 1: pattern ist regulärer Ausdruck in search Beispiel match("Dies ist ein Beispiel-String","Bei*l?St?i*") mi_integer

getAllinFlat(mi_char *pflat,position elem_pos,mi_char *pname, mi_char **PPuffer); Funktion Ermittelt, alle Positionen von Elementen mit dem Namen pname aus pflat von der Position elem_pos an in preorder und fügt sie zeilenweise dem Puffer mit dem Stringzeiger *PPuffer hinzu. Rückgabewert Anzahl: ermittelte Positionen Beispiel getAllinFlat("%~Text..%~","10|0","NAME",&resStr) mi_integer

getObjsByAttrinFlat(mi_char *pflat, position elem_pos, mi_char *pname,mi_char *AttName,mi_char *AttVal, mi_char **PPuffer); Funktion Ermittelt, alle Positionen von Elementen mit dem Namen pname und dem Attributnamen AttName und dem Attributwert AttVal aus pflat in preorder und fügt die Positionen zeilenweise dem Puffer mit dem Stringzeiger *PPuffer hinzu. Rückgabewert Anzahl: ermittelte Positionen Beispiel getObjsByAttrinFlat(flat,"10|0","NAME","VORNAME", "Michael",&resString)

Seite 44t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS mi_integer

getObjsByAttrWithRegExinFlat(mi_char *pflat,position elem_pos, mi_char *text,mi_char *AttName, mi_char *attRegEx,mi_char **PPuffer) Funktion Ermittelt, alle Positionen von Elementen mit dem Namen pname und dem Attributnamen AttName, bei denen attRegEx ein regulärer Ausdruck des Attributwerts ist. Der String pflat wird dabei in preorder durchsucht und fügt die Positionen zeilenweise dem Puffer mit dem Stringzeiger *PPuffer hinzu. Rückgabewert Anzahl: ermittelte Positionen Beispiel getObjsByAttrinFlat(flat,"10|0","NAME","VORNAME", "Mi??a*",&resString)

mi_integer Funktion

getElemTextinFlat(mi_char *pflat,position elem_pos,mi_char **PPuffer) Holt den Inhalt des flachen Elements mit der Position elem_pos mit kompletten Markup und fügt diesen dem Puffer mit dem Stringzeiger *PPuffer hinzu. Rückgabewert 1: falls das Element im flachen Teil nur PCDATA enthielt. 0: sonst ( speziell für getElemText für den Zeilenumbruch) Beispiel getElemTextinFlat(flat,"10|40",&resStr) mi_integer

getElemScreeninFlat(mi_char *pflat,position elem_pos, position cutpos,mi_char **PPuffer,mi_integer *akt_offset, mi_integer *akt_enter) Funktion Holt den Inhalt des Elements mit der Position elem_pos mit komplettem Markup. Dabei wird der Inhalt eingeschränkt. Angefangen wird bei der Position cutpos und zurückgeliefert wird nur eine vordefinierte Anzahl von Zeilen. Das Ergebnis wird in den Puffer mit dem Stringzeiger *PPuffer hinzugefügt. Außerdem wird der Offset von der Stopposition sowie die Anzahl der ausgeführten Zeilenumbrüche in den Zeigern akt_offset und akt_enter zurückgeliefert. Rückgabewert 1: falls das Element im flachen Teil nur PCDATA enthielt. 0: sonst ( speziell für getElemScreen für den Zeilenumbruch) Beispiel getElemScreeninFlat(flat,"9|-1","10|200",&resStr,&rofs,&rCR)

Seite 45t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

6 Der Algorithmus : getAllContaining Dieses Kapitel beschreibt Motivation, Beschreibung und Verifikation des Algorithmus getAllContaining. Mit der Motivation beginnt dieses Kapitel in 6.1 und kommt dann in Unterkapitel 6.2 zur Definition, sowie in 6.3 zur Beschreibung des Algorithmus. Da Vieles von der Richtigkeit dieses Algorithmus abhängt, wird in 6.4 ein intuitiver Induktionsbeweis geführt, um die Korrektheit zu garantieren. 6.1

Probleme mit Inclusions/Exclusions bei der Fragmentierung Dieses Unterkapitel soll eine Motivation für den Algorithmus getAllContaining geben.

Im wesentlichen wird diese Motivation durch Probleme mit Inclusions und Exclusions hervorgerufen. Bei der Konfiguration eines SGML-Dokumenttyps werden alle Namen der Elementtypen, die als eigenes Datenbankobjekt gespeichert werden sollen (nonFlatElement), in eine Konfigurations-Datei geschrieben. Alle anderen Elementtypen von diesem Dokumenttyp werden zusammengefaßt und in einem flachen Text-Block (flatElement) in die Datenbank eingefügt. Nach Lemma 3+4 in [Bö97], dürfen flache Elementtypen keine strukturierten Elementtypen enthalten und wenn ein Elementtyp erst mal als flach deklariert worden ist, dann kann er nicht mehr in einen strukturierten Elementtyp umgewandelt werden. Eine Inclusion ist ein Elementtyp, der in der Definition eines Elementtyps eine besondere Rolle spielt. Ein Beispiel ist die Fußnote: +(FN). Wenn eine Elementtyp-Definition diese Inclusion beinhaltet, dann können alle Elemente, die in diesem Element enthalten sind auch eine Fußnote (Element vom Typ 'FN') enthalten. Der folgende Ausschnitt aus einer DTD dient als Beispiel :

Seite 46t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS


+(FN)>

Der Elementtyp FN ist eine Inclusion in der Definition vom Elementtyp A, daß heißt, FN darf in jedem Dokument-Element vom Typ A enthalten sein (muß aber nicht). Aus der Sicht von A gesehen, verhält sich das genauso bei C. Die Fußnote FN darf aber auch in C enthalten sein, da C der direkte Nachfolger von A ist. Weiterhin darf FN auch in D und E enthalten sein, denn sie sind indirekte Nachfolger von A. Exclusions werden genauso definiert wie Inclusions, mit dem Unterschied, daß ein Exclusion-Typ nicht enthalten sein darf und das gilt auch für alle direkt oder indirekt enthaltenen Elementtypen. (Genaue Definitionen in [Her94]) Diese Inclusions erschweren nun die Berechnung der flachen Fragmente, weil es nicht so einfach vorhersagbar ist, welche Elemente in Welchen vorhanden sein dürfen. Der folgende Algorithmus getAllContaining soll zur Lösung dieses Problems beitragen. Da man von dem 'worst case' ausgehen muß, kann man die Exclusions vernachlässigen, denn sie beeinflussen nicht das absolute 'enthalten_in'-Modell. Der Algorithmus baut im wesentlichen einen DTD-Baum auf, berücksichtigt dabei alle Inclusions und berechnet danach den transitiven Abschluß. Als Ergebnis erhält man, für jeden Elementtyp die Menge aller direkt oder indirekt enthaltenen Elementtypen. Beim Konfigurieren muß man also bei jedem Elementtyp, der flach eingefügt werden soll, auch alle Elementtypen flach einfügen, die in der Ergebnis-Menge enthalten sind. Wenn in diesem Algorithmus auch noch Exclusions genauso berücksichtigt werden, dann ist es leicht möglich, eine Fragment-DTD zu erzeugen, um nur einzelne Dokument-Elemente zu parsen. Das Ergebnis wäre dann nicht 'alle enthaltenen Elementtypen' sondern 'alle zu berücksichtigenden Elementtypen' als Menge. Man müßte dann nur noch die Element- und Attribut-Definitionen dieser Elementtypen als eine DTD zusammenfassen. Diese Funktion wurde implementiert und dessen Beschreibung kann man in Kapitel 5.3.4 finden.

Seite 47t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 6.2

Definitionen für den Algorithmus Im folgenden Unterkapitel werden einige Definitionen dargestellt, die benötigt werden,

um den Algorithmus besser zu verstehen. Die Definitionen bilden auch die Grundlage für die Verifikation. EC[0] Container von ET mit id : e0 iS (includedSet) cS (containedSet) sS (sonSet) Tabelle 6.2-3:

EC[1] Container von ET mit id : e1 iS (includedSet) cS (containedSet) sS (sonSet)

... ... ... ...

EC[M] container von ET mit id : eM iS (includedSet) cS (containedSet) sS (sonSet)

Illustration des benutzten Datentyps für den Algorithmus

Vorgaben : -

alle Set, sind Mengen von Kontainer(-Pointern) (siehe Tabelle 6.2-3)

-

alle sS haben als anfänglichen Inhalt das contentModel des jeweiligen Elementtyps

-

alle iS haben als anfänglichen Inhalt die inclusion Types des jeweiligen Elementtyps

-

alle cS (die eigentliche Ergebnismenge) ist anfänglich leer.

-

nach Abbildung des Container-Arrays auf einen ADT sind die Söhne in sS und die Wurzel ist EC[0] (erfolgreiches Parsen der DTD zum DTD-Baum vorausgesetzt)

Ein Wort zu Zyklen : -

um zu vermeiden, daß indirekte Zyklen entstehen, muß man vor dem Bearbeiten eines Sohnes, diesen mit dem gesamten Stack vergleichen. Nur wenn dieser Sohn nicht auftritt, darf er behandelt werden !

Direkte

Zyklen : a  b und b  a

Indirekte Zyklen : a  b und b  c und c  d und d  b versteckte Zyklen : wenn ein direkter oder indirekter Zyklus durch Weiterleiten der Inclusions ensteht, aber vorher nicht feststellbar ist !

Seite 48t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS 6.3

Beschreibung des Algorithmus Dieses Unterkapitel beschreibt den Algorithmus in allen Einzelheiten. Es handelt sich

hierbei im Groben um drei verschachtelte Schleifen, die jeweils Funktionen aufrufen. Zum Überprüfen der Terminierungsbedingung werden noch einige Hilfsfunktionen genannt. 6.3.1 Funktionen, die in den Körpern der drei Schleifen aufgerufen werden

In Abbildung 6.3-9werden die elementaren Funktionen beschrieben. Dabei ist in der linken Spalte die Beschreibung in der Form eines DTD-Baumes skizziert ist, während in der rechten Spalte der Algorithmus der einzelnen Funktionen in einem Pseudocode beschrieben wird.

down (before):

down (after):

father +( If1..IfK )

father +( If1..IfK ) e

.........

a If1 ... IfK ...

son 1 +( Is11..Is1L )

c

son 1 +( Is11..Is1L ) +( If1..IfK )

succ (before) :

succ (after):

father +( If1..IfK )

father +( If1..IfK ) b d

son 1 +( Is11..Is1L ) +( If1..IfK )

son 2

son 1

.......

+( Is11..Is1L )

+( Is11..Is1L ) +( If1..IfK )

up (before) :

c son 2

...

+( Is21..Is2L ) +( If1..IfK )

up (after) :

father

father d b

son 1

.......

son N

Tabelle 6.3-4:

son 1

.......

son N

down(container father) ( init(son.sS) ; init(son.iS) ) a) father.sS := father.sS  father.iS b) father.cS := father.cS  father.sS c) if (son  leaf) then son.iS :=(son.iS  father.iS) / {son} d) push(father,stack) /* father auf stack */ e) return(son) /* mit son weiter */ succ(container son1) ( init(next(son).sS) ; init(next(son).iS) ) a) father := top(father) /* Top of the stack */ b) father.cS := father.cS  son.cS /* results to father */ c) if (next(son)  leaf) then next(son).iS := (next(son).iS  father.iS) / {next(son)} d) next(son).cS := next(son).cS  next(son).sS e) return(next(son)) /* mit next(son) weiter */ up(container sonN) a) father := top(father) /* Top of the stack */ b) father.cS := father.cS  sonN.cS /* results to father */ c) pull(stack) /* father vom stack */ d) return(father) /* weiter mit father */

Darstellung der Funktionen down, succ, up links grafisch, rechts als Pseudo-Code

Seite 49t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS

6.3.2 Hilfsfunktionen, die für die Schleifenterminierung benötigt werden  up_is_root( root , akt ) testet den aktuellen father (top of stack) und ist true, wenn up(akt)=root  no_succ(akt) testet den nächsten in der Menge sS vom aktuellen father (top of stack) und ist true, falls keiner exitiert  no_down(akt) testet sS von akt und liefert true, falls diese leer ist.

getAllContaining(array_of_container from_DTD) akt:=root ; push(root,stack) Loop1 while akt=root or not(up_is_root(akt))

3 2 1

Loop2 while akt=root or not(no_succ(akt)) 3

Loop3 while akt=root or not(no_down(akt)) 3) akt:=down(akt)

2

2) akt:=succ(akt)

bis der Stack leer ist

Breitensuche bis rechter Sohn Tiefensuche bis Blatt

1) akt:=up(akt) If not(no_succ(akt)) -> akt:=succ(akt)

Abbildung 6.3-9:

Algorithmus getAllContained in einem Struktogramm mit grafischer Erklärung

Idee : Der Baum wird durch Tiefensuche abgearbeitet, und dabei werden die Inclusion-Regeln beachtet. Ergebnisse werden beim backtracking (Postorder) vom rechten Sohn und bei dem Besuch der Bruder-Knoten von den anderen Söhnen geliefert. (up-b und succ-b ). Bei der Tiefensuche : alle included Types werden auch zu Söhnen gemacht. Alle Söhne bekommen dann durch down bzw succ die included Types des Vaters weitergeleitet : son_i.iS := (son_i.iS  father.iS) Dabei ergibt sich ein Sonderfall (siehe Abbildung 6.3-10)

Seite 50t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS r a c

d i

Abbildung 6.3-10:

b e

i

i

i i

i

Sonderfall, beim Weiterleiten der included Types des Vaters an seine Söhne

Es dürfen also nur die included Types weitergeleitet werden, die nicht zyklisch sind (d.h. I  I.iS) . Das wird jeweils in down und succ durch die Mengen-Differenz vermieden : son_i.iS := (son_i.iS  father.iS) / {son_i}. Die Initialisierung aller Söhne vor der Behandlung (in down und succ) garantiert, daß die Sub-Bäume der Element-Types wieder in aller Reinheit betrachtet werden können. (  wichtig für die mehrmalige Betrachtung von Elementtypen) 6.3.3 Die elementaren Funktionen Im Folgenden werden die Funktionen von Tabelle 6.3-4 näher erläutert. zu down :  Initialisiert die Mengen des ersten Sohnes (iS:=includedTypeDef, sS:=contentModel,cS:={})  setzt die includedTypes vom aktuellen Knoten als Söhne, denn included Types sind auch gleichzeitig Söhne  setzt alle Söhne in die Ergebnismenge(=alle Nachkommen vom aktuellen Knoten) als Zwischenergebnis.  setzt die includedTypes vom aktuellen Knoten in die includedTypes-Menge des ersten Sohnes (ganz links) außer Sohn 1 selbst (falls er ein includedType des Vaters ist -> Vermeidung von Zyklen), denn alle included Types des Vaters sind auch included Types aller Nachkommen.  dann mit dem ersten Sohn weiter ....  Tiefensuche (deep search first)

Seite 51t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS zu succ :  Initialisiert die Mengen des (i+1)-ten Sohnes (iS:=includedTypeDef, sS:=contentModel,cS:={})  der i-te Sohn liefert die Ergebnismenge(=alle seine Nachkommen) an den aktuellen Vater, denn alle seine Nachkommen sind auch Nachkommen des Vaters  setzt alle includedTypes des aktuellen Vaters in die includedType-Menge seines jüngeren Bruders (Sohn i+1), außer den Bruder selbst (falls er ein includedType des Vaters ist -> Vermeidung von Zyklen), denn alle included Types des Vaters sind auch included Types aller Nachkommen.  dann mit Bruder weiter ...  Besuch der Bruderknoten

zu up :  der aktuelle Sohn liefert die Ergebnismenge(=alle seine Nachkommen) an den aktuellen Vater, denn alle seine Nachkommen sind auch Nachkommen des Vaters  backtracking

6.3.4 Der Gesamt-Algorithmus Im Folgenden wird die Algorithmusbeschreibung von Abbildung 6.3-9 näher erläutert. zu getAllContaining :  Die Sonderabfragen beim Spezialfall, daß die Wurzel weniger als zwei Nachkommen hat, kann man in der Implementierung als vorausgesetzt annehmen. Für den Algorithmus soll es genügen, daß alle 3 Funktionen (down, succ, up) den Sonderfall akt=LostNode behandeln : top(stack)=up(LostNode)  LostNode=down(LostNode)  LostNode=succ(LostNode), wobei LostNode wie ein Null-Blatt zu sehen ist.  durch down ist die Ergebnismenge der vorletzten Generation (Väter mit nur Blättern als Söhne) als richtig gewährleistet  ansonsten geben alle Generationen durch succ und up jeweils ihre Ergebnismenge an ihren Vater weiter (backtracking)

Seite 52t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS  Da Zyklen von getAllContaining durch Prüfung vermieden werden und der DTD-Baum mit gesetzten included Types als Vorbedingung auch keine Zyklen enthalten dürfen, entsteht ein ADT-Baum, der einem durch die gesetzten incType-Bäume erweiterten DTD-Baum entspricht  Loop 3 terminiert, da an jedem Ast ein Blatt existiert (Abbruchbedingung für Loop 3)  Loop 2 terminiert, da Loop 2 und jeder Knoten nur eine endliche Anzahl von Söhnen hat

(diese Annzahl wird nur von down verändert, also nur beim

ersten Sohn)

 Loop 1 terminiert, da Loop 3+2 terminieren und der Baum endlich ist (keine Zyklen) und

als endlicher Keller nur mit down gefüllt ist .

6.4

Beweis mit Induktion zur Richtigkeit des Satzes Im letzten Unterkapitel befindet sich die Verifikation des Algorithmus getAllContaining.

Es handelt sich hierbei um einen intuitiven Induktions-Beweis. Satz (Proposition) : Der Algorithmus getAllContaining arbeitet korrekt mit den vorgegebenen Bedingungen.

Induktionsanfang(Basis) : n ist die Anzahl der in der DTD vorkommenden included Types n = 0:keine included Types  DTD-Baum in Postorder

n = 1:es existiert nur ein included Type : I  wenn der Elementtyp durch down oder succ erreicht wird, wird I zum Sohn gemacht bei

jedem down bzw. succ wird I jeweils an die Söhne weitergeleitet mit Ausnahme von I selbst (keine Zyklen) ! Diese Schritte werden dann mit den jeweiligen Söhnen fortgesetzt, bis zu den Blättern (deep search first) und dann mit up wieder zurück. (backtracking). Die Ergebnisauswertung ist dann wie oben beschrieben.

Seite 53t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Induktionsschritt :

wenn die Induktionsannahme für n gilt, n Inc.ETypes

dann gilt sie auch für n+1. Also wenn der

InduktionsSchritt

Algorithmus für n included Types funktioniert, dann funktioniert er auch für (n+1)-ten included Type ! (siehe Abbildung 6.4-11)

n+1 Inc.ETypes

Abbildung 6.4-11: Der Baum vor und nach dem Induktionsschritt

Folgende Fälle sind dabei für included Type (n+1) oder I(n+1) zu beachten : I. I(n+1) ist Sohn eines Elementtyps, der selbst kein included Type ist. II. I(n+1) ist Sohn eines included Type

Für jeden der beiden Fälle gilt folgender Fall :  I(n+1) ist flach, denn wenn I(n+1) strukturiert ist, wird (bis auf die Sonderbehandlung bei der incuded Type - Mengenverarbeitung) in jedem Knoten wie ein Sohn behandelt.  Ohne die Allgemeinheit zu verletzen, nehmen wir an, daß I(n+1) der Letzte included Type in der included Type Menge ist, (also auch der der ganz rechte Sohn des aktuellen Vaters) und alle included Types vorher wurden schon korrekt verarbeitet .  Durch die Inititialisierungen in down und succ werden außerdem versteckte Zyklen außeinandergebrochen (das gilt nicht für direkte und indirekte Zyklen)

zu Fall 1)
--

(ET 1,...,ETm) +(I1,...,In ,I(n+1))>

 Wenn I(n+1) in der DTD gesetzt war, dann ist bei down(start) folgendes passiert: - init setzt den ersten Sohn auf die Anfangswerte - dann wird I(n+1) als Sohn von start gesetzt (down-a) – und in die Menge iS des ersten Sohnes gebracht (down-b)  Der Fall erster Sohn=I(n+1) kann nicht auftreten, da sonst start ein Blatt wäre - diese Schritte (in down) werden solange wiederholt, bis ein Blatt erreicht wird. (dort :

Seite 54t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS Ausnahmebehandlung  keine Weitergabe von included Types) - nach jedem down ist I(n+1) wieder der letzte in der Menge iS des betroffenen Sohnes - nach jedem down ist I(n+1) auch der ganz rechte Sohn des betroffenen Vaters.  Beim am weitesten linken und unteren Blatt des Teilbaumes von start (start2), wird mit succ der Bruder dieses Blattes erreicht, mit dem dann fortgefahren wird, wie mit start und die Weiterleitungen des Vaters übernimmt jetzt succ (succ-b und succ-c)! (also ist I(n+1) wieder immer ganz rechts) - Wenn der aktuelle Knoten ein Blatt ist, geht es jeweils mit succ sofort weiter. Die Ergebnisse hat dann der aktuelle Vater bereits durch down-b bekommen, denn ein Blatt hat keine Nachfolger - Wenn der aktuelle Knoten strukturiert ist, dann enthält der Knoten ja bereits alle sS-Mengen seines Unterbaumes jeweils durch succ-b und up-b. Diese gibt er alle seinem Vater weiter. - bis dann jeweils I(n+1) als ganz rechter Sohn erreicht wird  Das ist das erste Mal, daß I(n+1) behandelt wird. Jedesmal, wenn I(n+1) behandelt wird, gibt es eine Ausnahmebehandlung  keine Weitergabe des Vaters von {akt} an akt.iS (sonst Zyklus)

 Wenn I(n+1) dann behandelt wurde, ist er auch gleichzeitig der letzte Sohn eines Knotens !  Mit up wird dann wieder der Vater ermittelt und eine Ebene zurückgegangen und auch das Ergebnis des ganz rechten Sohnes (in diesem Falle I(n+1) ) zurückgeliefert.  Dort wird wieder weiterverfahren wie mit start2 (also ist I(n+1) in allen Knoten des DTD-Baumes ganz rechts, außer in sich selbst)  Schließlich gelangt man zum ganz rechten Knoten von start und liefert mit up-b das letzte Ergebnis.

Seite 55t

ABBILDUNGS- UND TABELLEN-VERZEICHNIS zu Fall 2)

In In In

In+1 In+1

In+1

Abbildung 6.4-12:

Die Auswirkungen im DTD-Baum , wenn I(n+1) Sohn eines included Types ist.

 um bei Fall 2 eine normale Behandlung wie bei Fall 1 zu erhalten werden in down und succ die Initialisierungen vorgenommen, d.h. jedesmal, wenn ein Sohn behandelt wird (durch down oder succ), werden die für die Steuerung notwendigen Mengen iS und sS auf den Startwert zurückgesetzt. Dadurch werden versteckte Zyklen zumindest unterbrochen (das Erkennen ist nicht das Aufgabe dieses Algorithmus)  Die einzigen Zyklen, die dann noch bleiben sind die direkten oder indirekten Zyklen, die als Vorbedingung ja nicht vorhanden sein dürfen (im Algorithmus wären sie zu erkennen, wenn ein Sohn im stack schon vorkommt)  Wenn die versteckten Zyklen nicht mehr entstehen können, dann kann man wie bei Fall 1 vorgehen, also : I(n) = start , denn dann wird der Baum von I(n) nur noch wie ein ganz normaler Teilbaum betrachtet und das jedesmal, als wenn das erste mal wäre ...



Da also auch n+1 gilt, arbeitet der Algorithmus mit den vorgegebenen Bedingungen korrekt.

Seite 56t

KAPITEL 7 EXPERIMENTE

7 Experimente Das Experiment-Kapitel im Folgenden besteht im Wesentlichen aus der Grundbeschreibung in Unterkapitel 7.1 und aus fünf Experimenten 7.2 bis 7.5. In jedem Experiment werden, nach einer Beschreibung des Experiments, die Ergebnisse vorgestellt und nachfolgend analysiert. 7.1

Basis-Elemente der Experimente Das folgende Unterkapitel definiert alle grundsätzlichen Experiment-Bedingungen für die

Experimente (I )– (V). 7.1.1 Die SGML-Test-Dokumente Für die Experimente wurden große SGML-Dokumente benutzt. Hierzu eigneten sich besonders Dramen von William Shakespeare, die sich im Internet befanden. Die ausgewählten Dramen waren : 

Hamlet



Richard der III. (rich_iii.sgm) mit 275 KB



Othello

(hamlet.sgm) mit 283 KB

(othello.sgm) mit 253 KB

Jedes dieser Dramen ist vom Dokumenttyp 'PLAY', was auch gleichzeitig der Name des Root-Elements ist. Weiterhin ist jedes Drama in fünf Akte (Elementtype 'ACT') aufgeteilt und im Schnitt beinhaltet jeder Akt vier Szenen (Elementtype 'SCENE'). Insgesamt wird jede Zeile (Elementtyp 'LINE') als eigenes Dokument-Element notiert. Durchschnittlich gibt es in einem Drama ca. 4000 Dokument-Elemente vom Typ 'LINE'.

KAPITEL 7 EXPERIMENTE 7.1.2 Die verschiedenen Konfigurationen Für die drei Dramen wurden verschiedene Konfigurationen ausgewählt. Identifizierend für die verschiedenen Konfigurationen ist jeweils der größte flache Teil. Die Summe aller flachen Teile ergibt ca. 300 KB, da noch Zusatzinformationen mit in die flachen Fragmente gespeichert werden. Die Konfiguration wird dem SP über eine Konfigurationsdatei vermittelt, in der alle strukturierten Elementtyp-Namen zeilenweise stehen (in Großbuchstaben). Zum korrekten Auswählen wurde der Algorithmus 'getAllContaining' entwickelt, dessen Beschreibung und Verifikation in Kapitel 6 zu finden sind. Hier nun die vier verschiedenen Konfigurationen im Einzelnen : 

300 KB

-> das SGML-Dokument wird in einem flachen Fragment gespeichert.

In der Konfigurationsdatei befindet sich nur : PLAY 

60 KB

-> hier wird das Dokument in fünf Akte á 60 KB gespeichert.

In der Konfigurationsdatei befinden sich : PLAY PLAYTITLE FM PERSONAE SCNDESCR PLAYSUBT INDUCT ACT 

15 KB

-> in ungefähr 22 Szenen á 15 KB wird das Dokument Fragmentiert.

PLAY PLAYTITLE FM PERSONAE SCNDESCR PLAYSUBT INDUCT ACT ACTTITLE SCENE

KAPITEL 7 EXPERIMENTE



0,22 KB -> es gibt 4000 bis 5000 Zeilen á 0,22 KB im Durchschnitt, als Unterteilung PLAY PLAYTITLE FM PERSONAE SCNDESCR PLAYSUBT INDUCT INDUCTTITLE SUBHEAD ACT ACTTITLE SCENE SCENETITLE SPEECH SPEAKER STAGEDIR LINE

Die Werte sind nur als -Werte zu sehen. Die genauen Zahlen sind für die Experimente nicht interessant. In allen Experimenten wurde von keinen zusätzlichen Indexstrukturen wie PCDATAIndex, attribIndex oder structIndex gebrauch gemacht. Es wurden natürlich Datenbankspezifische Indizes aufgebaut. Alle Experiment wurden mehrmals und auf verschiedenen Rechnern durchgeführt. Das ganze auch in verschiedenen Reihenfolgen. Daraus ergab sich, daß die Ergebnisse unabhängig von der Anzahl der Datensätze, der Reihenfolge der Operationen und der Leistung der Workstation war. 7.2 mit (I) (II)

Experiment (I+II): Dokumentbezogene Queries und Gesamt-Operationen (Einfügen, Ausgeben). Navigationsmitteln wie down, succ, um die Suche in Preorder durchzuführen speziellen Stringsuch-Operationen im Flachen, die massiv das datenbankinterne Wissen ausnutzen.

KAPITEL 7 EXPERIMENTE Die Experimente (I+II) sind Bestandteil dieses Kapitels. Die Beschreibung aller Experimente ist in drei Schritte gegliedert. Es wurden in beiden Experimenten die gleichen Funktionen benutzt, aber mit verschiedenen Vorraussetzungen. Die Funktionen sind im Einzelnen getAll, getElemText (Element-Ausgabe) und das Einfügen. 7.2.1 Beschreibung der Experimente Das Ziel des Experiments ist die Ermittlung der Vor- und Nachteile verschiedener Konfigurationen. Hierbei wurden die Dramen jeweils in die vier oben beschriebenen Konfigurationen aufgeteilt und in die Datenbank eingefügt. Dieses Einfügen wurde jeweils zeitlich gemessen und dann als Durchschnittszeit für die jeweilige Konfiguration ausgewertet. Als Gegenstück wurden diese Zeitmessungen auch für die Ausgabe des jeweils ganzen Dokuments ermittelt. Auch hier wurde die Druchschnittszeit jeder Konfiguration von allen drei Dokumenten berechnet. Die Funktion getAll(Wurzel-Element,Elementtyp-Name) ist dann die spezielle Abfragefunktion, die zeitlich gemessen wird. Die Elementtypen, die dabei in den Dokumenten in Preorder gesucht wurden waren die Elemente : 

SCENE

->

kommt ca.

20 mal vor



STAGEDIR ->

kommt ca.

140 mal vor



LINE

kommt ca.

4000 mal vor

->

KAPITEL 7 EXPERIMENTE

7.2.2 Ergebnisse des Experiments (I+II) In Tabelle 7.2-5 sind die Ergebnisse der Zeitmessung (in Sekunden). In den ersten drei Zeilen

(ohne

die

Überschrift)

sind

die

Ergebnisse

von

getAll(root,etype)

mit

root=getRootbyDocName("hamlet.sgm") und etype  {'SCENE', 'STAGEDIR', 'LINE'}. Das Ganze gilt auch für die 'root' von rich_iii.sgm und othello.sgm. In diesen Zeilen und in der Zeile der Ausgabe gibt es zwei Spalten pro Konfiguration. Die linke Spalte zeigt dabei die Zeit an, die mit String-Suchalgorithmen und spezielles Wissen über die datenbankinterne Repräsentation, in flachen Fragmenten, ausnutzt. Wenn dabei auf ein flaches Fragment gestoßen wurde, aktivierte es die Funktion getAllinFlat, um den flachen Teil mit String-C-Funktionen zu durchsuchen. Es handelt sich hierbei um das Experiment (II). Die rechte Spalte dagegen, liefert die Zeiten von Experiment (I), das beim Suchen in PreorderReihenfolge die Navigations-Funktionen down und succ verwendet (up wird durch einen 'stack' ersetzt). Das Einfügen geschieht über den SGML-Parser. Dieser hat seine eigenen Navigationsfunktionen. Somit gibt es hier keine, zwei zu unterscheidende, Navigationsmöglichkeiten. Das erklärt die einzelne Spalte. alles flach (1 x 300 KB) SCENE (20-ETypes) 2,0 s 582,0 s STAGEDIR (134 ETypes) 1,0 s 580,7 s LINE (4014 ETypes) 1,7 s 580,0 s Ausgeben 2,0 s 312,0 s Einfuegen 11,7 s Tabelle 7.2-5:

grob aufgeteilt (5 x 60 KB) 16,7 s 140,3 s 16,3 s 140,0 s 17,0 s 140,0 s 20,0 s 150,0 s 45,7 s

mittel aufgeteilt (22 x 15 KB) 52,0 s 110,3 s 53,3 s 110,3 s 53,3 s 110,3 s 65,3 s 123,3 s 113,7 s

fein (nur hamlet) (5000 x 0,22 KB) 4609,0 s 4602,0 s 4546,0 s 4555,0 s 4556,0 s 4585,0 s 5090,0 s 5098,0 s 7449,7 s

Experiment (I+II) zum vergleichen von verschiedenen Konfigurationen .

7.2.3 Analyse der Ergebnisse Die Konfiguration 'fein' ist mit den anderen Konfigurationen nicht mehr vergleichbar, was die frappanten Zahlen zeigen. Da es sich in dem Dokument um ca. 6000 Elementtypen handelt, wurden auch dementsprechend viele Datenbankoperationen benötigt. Diese sind mit Sicherheit teurer, als String-Operationen in 'C'. Ein 1:1 Abbildung von allen Dokument-Elementen auf Datenbankojekten scheint also eine zu feine Granularität zu besitzen und ist deshalb nicht empfehlenswert in diesem Zusammenhang. Da die Algorithmen speziell mit einem ganzen Dokument zu tun haben, schneidet in der Wertung von Experiment (II) die Konfiguration 'alles flach' am besten ab. Der eine, flache Teil wird mit einer Datenbankoperation geladen und dann im Speicher mit effizienten C-Funktionen

KAPITEL 7 EXPERIMENTE durchsucht. Je mehr Fragmente zu druchsuchen waren (5 und 22), desto mehr Datenbankoperationen wurden benötigt. Das schlägt sich auch in den Zeiten nieder. Betrachtet man jedoch das Resultat von Experiment (I), also die rechten Spalten, dann kann man einen deutlichen Zeitanstieg bei der Konfiguration 'alles flach' feststellen. Es wurde bei diesen Operationen zwar mit Cache gearbeitet, aber die Navigationen down und succ im flachen Teil stellten sich als nicht sehr effizient heraus. Das ist auch die Motivation für das Experiment (III), das im Folgenden beschrieben wird. Fazit : für Dokumentbezogene Queries, die massiv das interne Wissen ausnutzen, ist die Konfiguration 'alles flach' die für die Performanz am besten geeignete Konfiguration. Das gilt jedoch nicht für Einzel-Operationen wie die Navigations-Funktionen. 7.3

Experiment (III) : Dokumentbezogene Einzel-Funktionen In diesem Unterkapitel wird das Experiment (III) beschrieben. Die Funktionen, die hier

zum Evaluieren benutzt wurden, sind im wesentlichen Navigations-Funktionen und die Ausgabe von kleinen Elementen. 7.3.1 Beschreibung des Experiments (III) Ziel des Experiments war es, für die im Experiment (I+II) verwendeten Konfigurationen, (ohne die Konfiguration 'fein') einige Einzel-Funktionen zu vergleichen. Es handelte sich hierbei hauptsächlich um die Funktionen up, succ, pred sowie die Ausgabe von einzelnen Elementen vom Typ 'SCENE' und 'LINE'. Damit die Ergebnisse in den Sekundenbereich kamen, wurden bei den Navigations-Funktionen Verschachtelungen und Sequenzen ausgeführt. Die Ziele wurden nach verschiedenen Gesichtspunkten ausgewählt, die auch auf die Schwächen (worst case) des Navigierens in flachen Fragmenten eingingen. Im wesentlichen handelte es sich hierbei um folgende Dokument-Elemente im Dokument : 

LLP



Position des letzten Dokument-Elements vom Typ 'LINE'



FSFA



Position der ersten Szene ('SCENE') im ersten Akt ('ACT')



LSFA



Position der letzten Szene ('SCENE') im ersten Akt ('ACT')



4.LL



Position des viert letzten Elements vom Typ 'LINE'

7.3.2 Ergebnisse des Experiments (III) In Tabelle 7.3-6 sind die Ergebniszeiten zusammengefaßt. In der ersten Spalte von Tabelle 7.3-6, werden die Aktionen beschrieben, deren Zeiten für die verschiedenen

KAPITEL 7 EXPERIMENTE Konfigurationen (in Sekunden) in den darauffolgenden Spalten angegeben werden. Die Zahlen in dieser ersten Spalte geben dabei die Häufigkeit der dahinter beschriebenen Aktionen an. Alle Funktionsaufrufe wurden zehn mal durchgeführt, bis auf 'up', denn hier hatte der 'worst case' große Einwirkung auf das Zeitverhalten.

10 x Ausgabe : SCENE 10 x Ausgabe : LINE 3 x up(up(up(up(LLP)))) 10 x succ(succ(succ(succ(FSFA)))) 10 x pred(pred(pred(pred(LSFA)))) 10 x pred(pred(pred(pred(LLP)))) 10 x succ(succ(succ(succ(4.LL)))) Tabelle 7.3-6:

alles flach grob aufgeteilt (1 x 300 KB) (5 x 60 KB) 7,0 sec 4,0 sec 7,0 sec 3,0 sec 21,0 sec 5,0 sec 12,0 sec 5,0 sec 9,0 sec 4,0 sec 9,0 sec 4,0 sec 8,0 sec 4,0 sec

mittel aufgeteilt (22 x 15 KB) 14,0 sec 3,0 sec 6,0 sec 15,0 sec 15,0 sec 3,0 sec 3,0 sec

Ergebniszeiten von speziellen Funktions-Sequenzen

7.3.3 Analyse der Ergebnisse Man kann in erkennen, daß es auch ungünstige Fälle für die gröber aufgeteilten Konfigurationen gibt. In diesem Experiment hatte die Konfiguration '(5x60 KB)' die beste Performanz. Das liegt wohl daran, daß diese dokumentbezogenen Einzel-Funktionen von zwei Tatsachen profitieren. Erstens sind die flachen Fragmente nicht so groß und die Navigation im Flachen dauert nicht so lange und zweitens werden nur, im speziellen Falle, fünf Datenbankoperationen benötigt. Fazit : Bei dokumentbezogenen Einzel-Funktionen ist das Performanz-Verhalten bei den verschiedenen Konfigurationen eher durchwachsen. Insgesamt liegen die Vorteile bei der Konfiguration '(5x60 KB)'.

KAPITEL 7 EXPERIMENTE

7.4

Experiment (IV): Datenbank-Query mit verschiedenen Konfigurationen Im Gegensatz zu den Experimenten (I-III) handelt es sich bei der Query im

Experiment (IV), im folgenden Unterkapitel, nicht um eine dokumentbezogene Query sondern um eine datenbankbezogene Query. 7.4.1 Beschreibung des Experiments (IV) Die Funktion getObjs(etype) sucht (im Gegensatz zu getAll) die gesamte Datenbank nach etype ab, daß heißt, alle Dokumente, deren DTD diesen etype beinhalten. Zu diesem Zweck wurden die drei Dramen jeweils drei mal mit der gleichen Konfiguration eingefügt, getObjs(etype) mit den etype-Namen 'ACT' und 'SCENE' durchgeführt und zeitlich gemessen. Ziel des Experiments (IV) war, die verschiedenen Konfigurationen zu vergleichen und das Ergebnis auch neben die Ergebnisse der Experimente (I-III) zu halten. 7.4.2 Ergebnisse des Experiments (IV) alles flach (1 x 300 KB) 21,0 sec 21,0 sec

mittel aufgeteilt (22 x 15 KB) getObjs - act 3,5 sec getObjs - scene 4,0 sec In Tabelle 7.4-7 werden die Ergebniszeiten (in Sekunden) zusammengefaßt. Tabelle 7.4-7:

grob aufgeteilt (5 x 60 KB) 3,5 sec 71,0 sec

Ergebniszeiten von Datenbank-Query getObjs mit verschiedenen Konfigurationen

7.4.3 Analyse der Ergebnisse Durch die Tatsache, daß bei einer Aufteilung nach dem Elementtyp 'SCENE', alle Szenen auch strukturiert vorliegen, kann man alle Elementtypen 'SCENE' bzw. 'ACT' mit einer Query bestimmen. Das schlägt sich natürlich auch in den Zeiten in Tabelle 7.4-7 nieder. Die Konfiguration 'grob' kann nur Vorteile aus der Aufteilung nach 'ACT' ziehen. Was sich aber negativ bei getObjs(ID('SCENE')) ausgleicht. Bei der Konfiguration 'alles flach' spielt es keine Rolle, nach welchen Elementtypen gefahndet wird, genausowenig, wie oft diese Vorkommen. Es ist nichts anderes, als ein Hintereinanderausführen von getAll für alle in Frage kommenden Dokumente. Fazit : Wenn es um datenbankorientierte Queries geht, kann die Granularität nicht fein genug sein. In Experiment (I) war die optimale Konfiguration, in Bezug auf Performanz, die Konfiguration 'alles flach', während das Optimum in Experiment (III) von Konfiguration 'grob'

KAPITEL 7 EXPERIMENTE erreicht wurde. Im Experiment (IV) war dann die feinste Granularität gefragt und die Konfiguration 'mittel' war die optimale Fragmentierung. Aus technischen und zeitlichen Gründen konnten die Experimente (III+IV) nicht mit der Konfiguration 'fein' durchgeführt werden. Mit Sicherheit hätten aber, bei dieser Konfiguration, alle getObjs-Anfragen die vier Sekunden-Grenze nicht überschritten. Es gibt also keine optimale Konfiguration, denn für die verschiedenen Bedürfnisse gab es keine Konfiguration, die nicht mit Nachteilen behaftet gewesen wäre. Will man also die optimale Konfiguration, in Bezug auf Performanz erhalten, muß man sich im Klaren sein, welche Anforderungen das System optimal erfüllen soll.

7.5

Experiment (V) : Vorausparsen vs. ad-hoc-Parsen In dem letzten Unterkapitel der Experimente wird ein Vergleich zwischen zwei

grundsätzlich verschiedenen Behandlungsmethoden von flachen Elementen gezogen besonders in Bezug auf nicht vollständig markierte Dokument-Elemente. 7.5.1 Beschreibung des Experiments (V) Im Kapitel 5.2 in [Bö97] ist beschrieben, welche Vorteile es haben kann, alle Elementtypen mit vollständiger Markierung in die flachen Datenbank-Objekte zu speichern. In diesem Experiment sollen Strukturerkennungs-Mechanismen miteinander verglichen werden. Da gibt es zum ersten das 'Vorausparsen'. Wie eben erwähnt, findet dann eine Funktion, die die Struktur erkennen soll, in flachen Datenbankobjekten eine vollständige Markierung vor. Es werden dann keinerlei Information mehr von der DTD benötigt. Zum zweiten gibt es die Möglichkeit, Markups wegzulassen, wie es in SGML erlaubt ist. In diesem Fall ist also die Markierung nicht vollständig. Eine strukturerkennende Funktion benögtigt also eine (Fragment-)DTD, mit der dann das flache Datenbankobjekt erneut geparst wird ('ad-hoc-Parsen'). Als strukturerkennende Funktion wurden Navigations-Funktionen wie up und succ benutzt, um nach mehrmaligem Aufrufen einer Funktion ein 'worst-' bzw. 'best case' Verhalten zu ermitteln. Bei der 'ad-hoc' Version reicht es aus, das flache Datenbank-Objekt einmal zu Parsen, um die unterste Schranke für die Ausführungszeit zu ermitteln. Als Untersuchungs-Objekte wurden wieder Teile aus dem Drama 'Hamlet' ausgewählt. Es konnten allerdings nur zwei Konfigurationen zum Vergleich herangezogen werden, denn bei der Konfiguration 'mittel aufgeteilt' konnte die Zeit nicht mehr gemessen werden. Übrig

KAPITEL 7 EXPERIMENTE blieben die Konfigurationen 'alles flach' und 'grob aufgeteilt'. Für das adhoc-Parsen wurde für dieses Experiment eigens der erste Akt von Hamlet zum SGML-Dokument umgewandelt und dementsprechend wurde auch die Fragment-DTD für 'ACT' mit allen benötigten Definitionen erstellt. Die Zeit des Parsens von diesem neuen Dokument wurde dann ausgewertet 7.5.2 Ergebnisse des Experiments (V) In Tabelle 7.5-8 ist das Ergebnis (Zeit in Sekunden) abgebildet. Als 'worstcase' wurde die Navigationsfunktion 'up' mit dem schlechtesten Erfolgsfall aufgerufen. Das kann man erreichen, indem man vom letzten, enthaltenen Elementtyp von 'PLAY' bzw. 'ACT' wieder in diese VaterElemente zurückspringt. In diesem Fall müssen nämlich alle Elemente beim Suchen 'überquert' werden, bevor das Ziel erreicht wird. Im 'bestcase' sprang succ eine 'LINE' (ca. 200 Bytes) weiter.

SP 300 KB (Etype play) 60 KB (Etype act) Tabelle 7.5-8:

0,50 sec 0,18 sec

Vorausparsen worstcase bestcase 0,11 sec 0,05 sec 0,03 sec 0,01 sec

Ergebnis - Vorausparsen vs. adhoc-Parsen

7.5.3 Analyse der Ergebnisse Aus Tabelle 7.5-8 geht eindeutig hervor, das die Zeiten zwischen SP und Vorausparsen mindestens um den Faktor fünf auseinander liegen. Dieser Faktor ist nur eine Abschätzung, da es sich bei den Zeiten vom SP auch nur um eine untere Schranke handelt.

KAPITEL 8 SCHLUSSBEMERKUNG

8 Schlußbemerkung In dieser Arbeit wurde eine Implementiertung eines Verwaltungssystems für SGMLDokumente entworfen und realisiert. Hierzu wurde ein objektrelationales Datenbanksystem als Implementierungsgrundlage gewählt. Der Name dieses objektrelationalen Datenbanksystems ist IUS - Informix Universal Server. Als Vorlage zur Strategie der Verwaltung, diente das Datenbanksystem HyperStorM, das auf einem objektorientierten DBMS namens VODAK basiert. Die Verwaltungsform , die in diesem objektorientierten DBMS gewählt wurde, ist eine hybride Form. Man kann hierbei durch Konfiguration bestimmen, welche Dokument-Elemente 1:1 als Datenbankobjekt oder welche zusammengefaßt als flacher Text in ein Datenbankobjekt gespeichert werden. Zum Konfigurieren wird erstens eine Datei benutzt, in der alle strukturierten Elemente zeilenweise notiert werden und zweitens die SuperDTD-Instanz, die die DTD (Dokument Type Definition) als Dokument repräsentiert. Die SuperDTD-Instanz wird als Dokument in die Datenbank eingefügt und kann somit mit Funktionen und Methoden für Dokumente behandelt werden. Es müssen keine zusätzlichen Zugriffs-Funktionen implementiert werden. Außerdem enthält die SuperDTD-Instanz Informationen über zu erstellende Indexstrukturen und gesonderte Mengen von Inclusions und Exclusions. Mit diesen Mengen ist es möglich, komplexere Dokumenttypen zu behandeln. Zu diesem Zweck wurde ein Algorithmus entwickelt, der mit Hilfe dieser Inclusion/Exclusion-Mengen ein komplettes 'enthalten Modell' berechnen kann. Man ist mit diesem Ergebnis in der Lage, für jedes Dokument-Element, alle enthaltenen Elemente zu bestimmen – Inclusions eingeschlossen. Für diesen Algorithmus wurde ein Korrektheitsbeweis durchgeführt.

KAPITEL 8 SCHLUSSBEMERKUNG Ein weiteres Ziel dieser Arbeit war es, das objektrelationale Datenbanksystem zu evaluieren und dabei immer ein Vergleich mit dem Vorgängersystem im Auge zu behalten. Hierzu wurden fünf Experimente durchgeführt. Die Versuchs-Objekte waren hierbei drei große Dramen von William Shakespeare in SGML-Fassung. Im wesentlichen wurden diese Dokumente mit vier verschiedenen Konfigurationen in die Datenbank eingefügt und diverse Ausgabe- und Abfrage-Funktionen zeitlich gemessen. Wie auch schon im objektorientierten Vorgängersystem, gab es auch im objektrelationalen DBMS keine optimale Konfiguration für alle gestellten Aufgaben. Vielmehr machten die Experimente deutlich, wie vorteilhaft man die Konfigurationsmechanismen und Methoden, die die Dokumentstruktur ausnutzen, nutzen kann, um eine optimale Performanz für die individuellen Anforderungen zu erhalten. Dieser zum Testen entwickelte Prototyp eines objektrelationalen DBMS muß in Zukunft noch Funktionen und Operationen erhalten, die das Datenbanksystem zu einem kompletten Verwaltungssystem macht. Funktionen wie Ändern, Löschen oder, wie im Vorgängersystem vorhandene, semantische Auswertung von Hyperlinks, sind noch zu implementieren. Dazu kommt noch eine Benutzerschnittstelle im Internet, die gerade in Arbeit ist, sowie Schnittstellen zu den Sprachverwandten HTML und XML. Darüber hinaus wäre eine Automatisierung der Konfiguration denkbar. Beim aktuellen Stand wird die Konfiguration mit unterstützenden Hilfroutinen noch vom Benutzer, per Hand erstellt.

KAPITEL 8 SCHLUSSBEMERKUNG

Anhang A

Die DTD für Shakespeare Dramen


J. Bosak

1994.03.01, 1997.01.02

playtitle personaetitle acttitle scenetitle inducttitle fm p personae

- - (playtitle,fm,personae,scndescr, playsubt,induct?,act+)> - - (#PCDATA)> - - (#PCDATA)> - - (#PCDATA)> - - (#PCDATA)> - - (#PCDATA)> - - (p+)> - - (#PCDATA)> - - (personaetitle, (persona | pgroup)

pgroup persona grpdescr scndescr playsubt induct

-


-

(persona+, grpdescr)> (#PCDATA)> (#PCDATA)> (#PCDATA)> (#PCDATA)> (inducttitle,(scene+| (speech|stagedir|subhead)+))> - - (acttitle, scene+)> - - (scenetitle, (speech | stagedir | subhead)+)> - - (speaker+, (line | stagedir | subhead)+)>

KAPITEL 8 SCHLUSSBEMERKUNG


speaker line stagedir lstagedir subhead

-

-

(#PCDATA)> (lstagedir | #PCDATA)+> (#PCDATA)> (#PCDATA)> (#PCDATA)>

KAPITEL 8 SCHLUSSBEMERKUNG

Anhang B

Die SuperDTD-Instanz 'SDTDi_PLAY', erstellt von der DTD 'shaksper.dtd' aus Anhang A

<SUPERDTD version=2 rootElemName=PLAY> <ELEM id=e0 elemName=PLAY tagOmmission=NO contentModel='(PLAYTITLE,FM,PERSONAE,SCNDESCR,PLAYSUBT,INDUCT?, ACT+)' containedTypes='e1 e2 e4 e9 e10 e11 e22 e24 e26' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX=' '>

KAPITEL 8 SCHLUSSBEMERKUNG

<ELEM id=e1 elemName=PLAYTITLE tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=Y STRUCTINDEX=' '> <ELEM id=e2 elemName=FM tagOmmission=NO contentModel='P+' containedTypes='e3' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX=' '>

KAPITEL 8 SCHLUSSBEMERKUNG

<ELEM id=e3 elemName=P tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e4 elemName=PERSONAE tagOmmission=NO contentModel='(PERSONAETITLE,(PERSONA,PGROUP)+)' containedTypes='e5 e6 e7' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e5 elemName=PERSONAETITLE tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e6 elemName=PERSONA tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e7 elemName=PGROUP tagOmmission=NO contentModel='(PERSONA+,GRPDESCR)' containedTypes='e6 e8' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e8 elemName=GRPDESCR tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '>

KAPITEL 8 SCHLUSSBEMERKUNG

<ELEM id=e9 elemName=SCNDESCR tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e10 elemName=PLAYSUBT tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=Y STRUCTINDEX=' '> <ELEM id=e11 elemName=INDUCT tagOmmission=NO contentModel='(INDUCTTITLE,(SCENE+, (SPEECH,STAGEDIR,SUBHEAD)+))' containedTypes='e12 e13 e14 e16 e21 e20' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e12 elemName=INDUCTTITLE tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=Y STRUCTINDEX=' '> <ELEM id=e13 elemName=SCENE tagOmmission=NO contentModel='(SCENETITLE,(SPEECH,STAGEDIR,SUBHEAD)+)' containedTypes='e15 e13 e16 e21 e20' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX='SCENETITLE'>

KAPITEL 8 SCHLUSSBEMERKUNG

<ELEM id=e14 elemName=SCENETITLE tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=Y STRUCTINDEX=' '>

KAPITEL 8 SCHLUSSBEMERKUNG

<ELEM id=e15 elemName=SPEECH tagOmmission=NO contentModel='(SPEAKER+,(LINE,LSTAGEDIR,SUBHEAD)+)' containedTypes='e17 e18 e19 e20' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e16 elemName=SPEAKER tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=Y STRUCTINDEX=' '> <ELEM id=e17 elemName=LINE tagOmmission=NO contentModel='(LSTAGEDIR|(#PCDATA))+' containedTypes='e19 ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e18 elemName=LSTAGEDIR tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e19 elemName=SUBHEAD tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '> <ELEM id=e20 elemName=STAGEDIR tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=N STRUCTINDEX=' '>

KAPITEL 8 SCHLUSSBEMERKUNG

<ELEM id=e21 elemName=ACT tagOmmission=NO contentModel='(ACTTITLE,SCENE+)' containedTypes='e25 e13 e22 e14 e26' includedTypes=' ' excludedTypes=' ' FLAT=NOT ELEMINDEX=N STRUCTINDEX='ACTTITLE'> <ELEM id=e22 elemName=ACTTITLE tagOmmission=NO contentModel='(#PCDATA)' containedTypes=' ' includedTypes=' ' excludedTypes=' ' FLAT=YES ELEMINDEX=Y STRUCTINDEX=' '>

KAPITEL 8 SCHLUSSBEMERKUNG

Anhang C

Das SQL-Script 'create.sql' zum Erstellen der Datenbank-Typen und -Tabellen.

-------------------------------------------------------------- Erstellen von Typen und Tabellen für die SGML-Datenbank --------------------------------------------------------------- Ref-Typ benennen: zur besseren Lesbarkeit create distinct type id_type as integer; ---

Erweiterungen der Spezifikation: own_id' s in: etype, dtd, docElem, document

-------------------------------------------------------- Attribut-Paarung -- Die Instanz dieses Typs enthält das Attribut des DokumentElements mit der -- Referenz auf das entsprechende nonflatElem mit der own_id 'element' create row type attrRec ( element id_type, name varchar(128), value varchar(128) );

KAPITEL 8 SCHLUSSBEMERKUNG

-------------------------------------------------------- Elementtypen -- Für jeden Elementtyp, welcher in einer von der Datenbank unterstützten -- DTD enthalten ist, gibt es eine entsprechende Instanz von 'etype' create row type etype ( own_id id_type, name varchar(128), dtdref id_type, contentModel lvarchar, pcdataIndexed boolean, -- "f" oder "t" structIndexed set(varchar(128) not null) ); -------------------------------------------------------- Dokument Typ Definitionen -- Jeder Dokumenttyp hat eine entsprechende Instanz dieses Typs create row type dtd ( own_id id_type, name varchar(128), etypes set(id_type not null), config clob ); -------------------------------------------------------- Dokumente -- Die Instanz dieses Typs ist die Repräsentation eines Dokuments create row type document ( own_id id_type, name varchar(128), dtdref id_type, root id_type ); -------------------------------------------------------- Dokument- Elemente -- Das ist die generische Repräsentation eines DokumentFragmentes

KAPITEL 8 SCHLUSSBEMERKUNG

create row type docElem ( own_id id_type, doc id_type, --ref(document) up id_type, --ref(docElem) succ id_type, --ref(docElem) pred id_type --ref(docElem) ); -------------------------------------------------------- Strukturierte Dokument- Elemente -- Das ist die Repräsentation von Dokument- Elementen mit einer expliziten -- Datenbank- Repräsentation create row type nonflatElem ( down id_type, etName varchar(128) ) under docElem; -------------------------------------------------------- Flache Dokument Elemente -- Das ist die Repräsentation von Dokument-Fragmenten, die aus Dokument- Elementen -- bestehen, deren Repräsentation unstrukturiert ist. create row type flatElem ( flat clob ) under docElem; -------------------------------------------------------- PCDATA- Index -- Eine Instanz dieses Typs identifiziert das Vorkommen eines Text-Inhalts innerhalb -- eines Dokuments. create row type pcdataIndex ( elementType id_type, content varchar(128), positions set(varchar(128) not null) ); -- Jeder Wert von 'content' ist der Textinhalt des Elements vom Elementtyp 'elementType' -- 'positions' ist dann die Menge alle Index- Einträge in der Form : "oid|occurrence" -- 'oid' ist die own_id des Elementes, in dem der Inhalt vorkommt

KAPITEL 8 SCHLUSSBEMERKUNG

-- und 'occurrence' gibt die Anzahl an, wie oft 'content' in dem Dokument-Fragment -- vorkommt. Ist das betroffene Dokument- Element strukturiert, ist 'occurrence'=-1 . -------------------------------------------------------- Attribut- Index -- Eine Instanz dieses Typs identifiziert das Vorkommen eines Attributwertes create row type attrIndex ( elementType id_type, attrName varchar(128), attrValue varchar(128), positions set(varchar(128) not null) ); -- Jedes Attribut-Paar ('attrName','attValue') des Elements ist vom Elementtyp 'elementType' -- 'positions' -> siehe PCDATAIndex. -------------------------------------------------------- Structurierter Index -- Eine Instanz dieses Typs identifiziert das Vorkommen eines Textinhalts in einem -- verschachtelten Paar von bestimmten Elementtypen, -- bei denen der 2. Elementtyp in dem 1. Elementyp enthalten ist create row type structIndex ( extElemType id_type, intElemType id_type, content varchar(128), positions set(varchar(128) not null) ); -------------------------------------------------------- create Tables (etype, dtd, document, docElem) ------------------------------------------------------create table etypeTable of type etype ( PRIMARY KEY (own_id) ); ------------------------------------------------------create table dtdTable of type dtd ( PRIMARY KEY (own_id), UNIQUE(name) ); ------------------------------------------------------create table documentTable of type document ( PRIMARY KEY (own_id),

KAPITEL 8 SCHLUSSBEMERKUNG

UNIQUE(name) );

KAPITEL 8 SCHLUSSBEMERKUNG

------------------------------------------------------create table docElemTable of type docElem ( PRIMARY KEY (own_id) ); ------------------------------------------------------create table nonflatElemTable of type nonflatElem UNDER docElemTable; ------------------------------------------------------create table flatElemTable of type flatElem UNDER docElemTable; ------------------------------------------------------create table attrRecTable of type attrRec ( PRIMARY KEY (element , name , value) ); ------------------------------------------------------create table attrIndexTable of type attrIndex ( PRIMARY KEY (elementType , attrName , attrValue) ); ------------------------------------------------------create table structIndexTable of type structIndex ( PRIMARY KEY (extElemType,intElemType,content) ); ------------------------------------------------------create table PCDATAIndexTable of type pcdataIndex ( PRIMARY KEY (elementType,content) ); -------------------------------------------------------

KAPITEL 8 SCHLUSSBEMERKUNG

Anhang D

Das SQL-Skript 'inits.sql' zum Initialisieren der Datenbanktabellen

-- make casts implicit to avoid 0::id_type to get id_typenumbers... drop cast (integer as id_type); create implicit cast (integer as id_type); delete delete delete delete delete delete delete delete delete delete

from from from from from from from from from from

documentTable; docElemTable; nonflatElemTable; flatElemTable; dtdTable; etypeTable; PCDATAIndexTable; attrIndexTable; structIndexTable; attrRecTable;

-----------------------------------------------------------------Initialisieren aller Tabellen mit mindestens einem LeerDatensatz----------------------------------------------------------------- the ETypes for the DTD "SUPERDTD" insert into etypeTable values(0, "SUPERDTD",4,"(DOCTYPE, (ENTITY|ELEM| NOTATION|SHORTREF|USEMAP)*,(COMBI)*)","f",Null); insert into etypeTable values(1, "DOCTYPE",4,"EMPTY","f",Null); insert into etypeTable values(2, "ENTITY",4,"(#PCDATA)","f",Null); insert into etypeTable values(3, "ELEM",4,"(ATTRIBUTE*)","f",Null);

KAPITEL 8 SCHLUSSBEMERKUNG

insert into etypeTable values(4, "ATTRIBUTE",4,"EMPTY","f",Null); insert into etypeTable values(5, "COMBI",4,"EMPTY","f",Null); insert into etypeTable values(6, "NOTATION",4,"EMPTY","f",Null); insert into etypeTable values(7, "SHORTREF",4,"(REFLIST*)","f",Null); insert into etypeTable values(8, "REFLIST",4,"EMPTY","f",Null); insert into etypeTable values(9, "USEMAP",4,"EMPTY","f",Null); -- the ETypes for the DTD "VORLESUNGSVERZEICHNIS" insert into etypeTable values(10,"VORLESUNGSVERZEICHNIS",2,"((Termine), (Legende), (Fachbereich)+)","t",Null); insert into etypeTable values(11 , "TERMINE",2,"(Termin & Datum)*","t",Null); insert into etypeTable values(12 , "TERMIN",2,"(#PCDATA)," "t","SET{'String1','String2'}"); insert into etypeTable values(13 , "DATUM",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(14 , "LEGENDE",2,"(Alias & Erklaerung)*","t",Null); insert into etypeTable values(15 , "ALIAS",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(16 , "ERKLAERUNG",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(17 , "FACHBEREICH",2,"(Name , (Richtung?,Lehrveranst?, Eintrag+)+ )" ,"t",Null); insert into etypeTable values(18 , "NAME",2, "(#PCDATA)","t",Null); insert into etypeTable values(19 , "RICHTUNG",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(20 , "LEHRVERANST",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(21 , "EINTRAG",2,"(Kz?,Bezeich, Art, Tag, Zeit, Raum, Beginn, Prof, Fn?)" ,"t",Null); insert into etypeTable values(22 , "FN",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(23 , "KZ",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(24 , "BEZEICH",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(25 , "ART",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(26 , "TAG",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(27 , "ZEIT",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(28 , "RAUM",2,"(#PCDATA)" ,"t",Null);

KAPITEL 8 SCHLUSSBEMERKUNG

insert into etypeTable values(29 , "BEGINN",2,"(#PCDATA)" ,"t",Null); insert into etypeTable values(30 , "PROF",2,"(#PCDATA)" ,"t",Null); -- the ETypes for the DTD "PLAY" insert into etypeTable values(31 , "PLAY",3,"(playtitle, fm, personae, scndescr, playsubt, induct , act+))" ,"t",Null); insert into etypeTable values(32 , "FM",3,"(p+)" ,"t",Null); insert into etypeTable values(33 , "PERSONAE",3,"(personaetitle, (persona |pgroup)+)" ,"t",Null); insert into etypeTable values(34 , "PGROUP",3,"(persona+, grpdescr),"t",Null); insert into etypeTable values(35 , "INDUCT",3,"(inducttitle, (scene+|(speech|stagedir|subhead)+)" ,"t",Null); insert into etypeTable values(36 , "ACT",3,"(acttitle,scene+)," "t",Null); insert into etypeTable values(37 , "SCENE",3,"(scenetitle, (speech | stagedir | subhead)+)" ,"t",Null); insert into etypeTable values(38 , "PROLOGUE",3,"((stagedir | speech)+)" ,"t",Null); insert into etypeTable values(39 , "EPILOGUE",3,"((stagedir | speech)+)" ,"t",Null); insert into etypeTable values(40 , "SPEECH",3,"(speaker+, line | lstagedir | subhead)+)" ,"t",Null); insert into etypeTable values(41 , "LINE",3,"(lstagedir |#PCDATA)+","t",Null); insert into etypeTable values(42 , "PLAYTITLE",3, "(#PCDATA)","t",Null); insert into etypeTable values(43 ,"PERSONAETITLE",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(44 , "ACTTITLE",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(45 , "SCENETITLE",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(46 , "INDUCTTITLE",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(47 , "P",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(48 , "PERSONA",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(49 , "GRPDESCR",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(50 , "SCNDESCR",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(51 , "PLAYSUBT",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(52 , "SPEAKER",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(53 , "STAGEDIR",3,"(#PCDATA)" ,"t",Null);

KAPITEL 8 SCHLUSSBEMERKUNG

insert into etypeTable values(54 , "LSTAGEDIR",3,"(#PCDATA)" ,"t",Null); insert into etypeTable values(55 , "SUBHEAD",3,"(#PCDATA)" ,"t",Null);

KAPITEL 8 SCHLUSSBEMERKUNG

insert into documentTable values(0,"Test-DocumentName",0,Null); insert into docElemTable values(0,Null,Null,Null,Null); insert into nonFlatElemTable values(1,0,Null,Null,Null,2,"initName"); insert into attrRecTable values(1,"AName","AValue"); insert into flatElemTable values(2,0,1,Null,Null,Null); insert into dtdTable values(0,"INIT",Null,Null); insert into dtdTable values(1,"LIED",Null,Null); insert into dtdtable values(2,"VORLESUNGSVERZEICHNIS",Null,Null); insert into dtdtable values(3,"PLAY",Null,Null); insert into dtdtable values(4,"SUPERDTD",Null,Null); insert into dtdtable values(5,"MMFDOC",Null,Null); insert into dtdtable values(6,"VZ",Null,Null); insert into PCDATAIndexTable values(0,"PCDATAIndexInit","SET{'0|1'}"); insert into attrIndexTable values(0,"attrInitName","attrInitValue","SET{'0|1'}"); insert into structIndexTable values(0,1,"structIndexInit","SET{'0|1'}");

KAPITEL 8 SCHLUSSBEMERKUNG

Abbildungsverzeichnis Abbildung 3.1-1: Eine Beispiel-Dokumnet vom Dokumenttyp 'article' ................................................................................................................................. 13 Abbildung 3.1-2: Eine Beispiel-DTD vom Dokumenttyp 'article' ................................................................................................................................. 14 Abbildung 3.2-1: Repräsentation des Beispieldokuments – Dokumentelement = Knoten ................................................................................................................................. 15 Abbildung 3.2-2: Repräsentation des Beispieldokuments - zusammengefaßte Elemente ................................................................................................................................. 16 Abbildung 4.1-1: Architektur des Gesamtsystems ................................................................................................................................. 18 Abbildung 4.4-1 : Das Vererbungsverhältnis zwischen docElem, nonFlatElem und flatElem. ................................................................................................................................. 20 Abbildung 4.4-1: Zusammenspiel der Tabellen, die zur Speicherung der Dokumente beteiligt sind. ................................................................................................................................. 22 Abbildung 4.6-1: Ablaufdiagramm - Einfügen eines SGML-Dokuments in die Datenbank. ................................................................................................................................. 26 Abbildung 6.3-1: Algorithmus getAllContained in einem Struktogramm mit grafischer Erklärung ................................................................................................................................. 51 Abbildung 6.3-2: Sonderfall, beim Weiterleiten der included Types des Vaters an seine Söhne ................................................................................................................................. 52 Abbildung 6.4-1: Der Baum vor und nach dem Induktionsschritt ................................................................................................................................. 55 Abbildung 6.4-2: Die Auswirkungen im DTD-Baum , wenn I(n+1) Sohn eines included Types ist. ................................................................................................................................. 57

KAPITEL 8 SCHLUSSBEMERKUNG

KAPITEL 8 SCHLUSSBEMERKUNG

Tabellenverzeichnis Tabelle 4.2-1:

Datentypen von den verschiedenen Schnittstellen ................................................................................................................................. 18

Tabelle 4.3-1:

Selbsterstellte Datentypen und ihre Abstammung ................................................................................................................................. 19

Tabelle 6.2-1:

Illustration des benutzten Datentyps für den Algorithmus ................................................................................................................................. 49

Tabelle 6.3-1:

Darstellung der Funktionen down, succ, up links grafisch, rechts als Pseudo-Code ................................................................................................................................. 50

Tabelle 7.2-1:

Experiment (I+II) zum vergleichen von verschiedenen Konfigurationen . ................................................................................................................................. 62

Tabelle 7.3-1:

Ergebniszeiten von speziellen Funktions-Sequenzen ................................................................................................................................. 64

Tabelle 7.4-1:

Ergebniszeiten von Datenbank-Query getObjs mit verschiedenen Konfigurationen ................................................................................................................................. 65

Tabelle 7.5-1:

Ergebnis - Vorausparsen vs. adhoc-Parsen ................................................................................................................................. 67

KAPITEL 8 SCHLUSSBEMERKUNG

Literaturverzeichnis [Sto96]

M. Stonebraker, D. Moore : OBJECT-RELATIONAL DBMSs, the next great wave , Morgan Kaufmann Publishers. inc. San Francisco. Califonia, USA, 1996

[GBS92]

G.H. Gonnet, R. Baeza-Yates, T. Snider: Information Retrieval, Data Structures & Algorithms, S.66-82 : New Indices for Text: PAT Trees and PAT Arrays, Prentice Hall, New Jersey, USA 1992

[Bö97]

K. Böhm, Benutzung objektorientierter Datenbank-Technologie für die Speicherung strukturierter Dokumente, TU-Darmstadt, 1997

[Her94]

E.v.Herwijnen : Practical SGML, Second Edition , Kluwer Academic Publishers, Dordrecht, Niederlande 1994

[BAK95]

K. Böhm, K. Aberer, W. Klas : Building a Hybrid Database Application for Structured Documents, GMD Darmstadt, Deutschland 1995

[AHU72]

Aho, Hopcroft, Ullman : The Design and Analysis of Computer Algorithms , Addison Wesley Publishing Co., Massachusetts 1972

[BANY95] K. Böhm, K. Aberer, E.J. Neuhold, X. Yang : Structured Document Storage and Refined Declarative and Navigational Access Mechanisms in HyperStorM, GMD Darmstadt, Deutschland, 1995 [INF97]

INFORMIX : INFORMIX-Universal Server DataBlade API, User Manual , INFORMIX Press, CA, USA, 1997

[IPSI95]

IPSI : VODAK V4.0 User Manual , GMD Darmstadt,1995