Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

21.09.1984 - 

Automatisierter logischer Entwurf einer Codasyl-Datenbank:

Semantik der Datenelemente bestimmt das Novum

MÜNCHEN (CW) - In den letzten Jahren habe Methoden zum Entwurf von Datenbanken wachsende Aufmerksamkeit gefunden. Eine davon ist die Dataid Methode, die von Italian National Research Council (CNR) entwickelt wurde. Dataid ist eine "Schreibtisch"-Methode zum Entwurf einer Codasyl-Datenbank, die im gesamten Entwicklungsprozeß Anwendung findet. An der Universität von Turin wurde letzt ein Tool (genannt ERCMAP) entwickelt, das einen Teil dieses Entwicklungsprozesses automatisiert. Der folgende Artikel gibt noch einmal einen kurzen Überblick über die Problematik von Datenbankentwürfen und erläutert dann die Besonderheiten der italienischen Methode.

Ideal wäre eine Datenbank, wenn es gelänge, alle in einem Unternehmen vorhandenen und benötigten Daten darin zu speichern - und zwar jede Information nur einmal (Redundanzfreiheit) - und doch jedem einzelnen Anwender die Informationen so zu präsentieren, wie es seiner Sichtweise auf die Daten und seinen Verarbeitungserfordernissen entspricht. Das Problem besteht darin, daß zwischen diesem Ideal und der zu realisierenden physischen Organisation der Daten ein weiter Weg liegt und, daß es leider notwendig ist, eine Reihe von Abstraktionen oder Vereinfachungen zu vollziehen, bis eine Information als binärer Code gespeichert werden kann.

Es gibt verschiedene Datenmodelle die diese Aufgabe, die Beschreibung der realen Welt in für Computer verarbeitbarer Form, mehr oder weniger gut, daß heißt mit mehr oder weniger Informationsverlust leisten. Die Modellbildung besteht darin, daß die Dinge der wirklichen Welt als Objekte, sogenannte "Entities" aufgefaßt werden, zwischen denen gewisse Beziehungen bestehen. Die verschiedenen Modelle unterscheiden sich darin, wie die Entities und Beziehungen formal beschrieben werden. Die drei zur Zeit gebräuchlichsten sind:

- Das hierarchische Modell, das aus konventionellen Dateisystemen zur Verwaltung von Dateien mit komplex-variabel langen Sätzen hervorging und noch sehr der physischen Organisation der Daten verhaftet ist. Obwohl dieses System gravierende Mängel aufweist, ist es noch sehr verbreitet, weil eine Umstellung auf andere Systeme nur sehr schwer möglich und mit hohen Kosten verbunden ist. Das bekannteste derartige System ist das von IBM benutzte IMS (Information Management System).

- Das Netzwerkmodell, das auf die Codasyl-Vorschläge zurückgeht und weiter unten näher beschrieben wird. Beim Netzwerkmodell geht man von beliebigen Beziehungen zwischen den Entities aus, es wird deshalb auch als Entity Relationship Model bezeichnet. Stellt man die Entities und ihre Beziehungen zu einander grafisch dar, so erhält man einen beliebigen gerichteten Graphen, ein Netzwerk.

- Das relationale Modell, bei dem ein Entity nicht als ein einzelnes Element, sondern als Menge von Attributen, die in Relation zu einander stehen aufgefaßt wird. Naheliegenderweise lassen sich auch Beziehungen in dieser Form beschreiben. Im relationalen Modell haben Entities und Beziehungen also dieselbe formale Beschreibung, was die Datenbankoperationen erheblich erleichtert, aber auch zu einigen Anomalien führen kann.

Neben diesen drei Modellen gibt es eine Reihe von Systemen, die nicht in diese Kategorien eingeordnet werden können. Dazu gehören zum Beispiel Adabas, System 2000 und Total.

Ein wesentlicher Mangel ist allen diesen Modellen jedoch gemeinsam: Sie sind formale Beschreibungen der wirklichen Welt und lassen viele inhaltliche Zusammenhänge außer acht. Es existiert deshalb die Forderung nach Datenmodellen, die die inhaltliche Bedeutung (Semantik) der Datenelemente berücksichtigen. Derartige semantische Modelle sind im konzeptionellen Bereich schon verschiedentlich entwickelt worden, für die Verwendung bei kommerziellen Anwendungen allerdings noch zu unhandlich.

Bei dem Entwurf von Datenbanken hat sich inzwischen eine allgemeine Struktur des Entwicklungsprozesses durchgesetzt. Er wird unterteilt:

1. Bedarfsfeststellung und -analyse

2. konzeptioneller Entwurf

3. logischer Entwurf

4. physischer Entwurf

In den ersten beiden Phasen werden die Anforderungen des Benutzers zusammengestellt und in einer sogenannten konzeptionellen Beschreibung, die unabhängig von dem zur Verwendung vorgesehenen Datenbankmodell ist, dargestellt. Durch den logischen und physischen Entwurf wird das Konzept dann in die Strukturen der Zieldatenbank umgewandelt.

Der Entwurf einer Datenbank ist eine sehr komplexe Angelegenheit und die Effizienz der verwendeten Methoden kann durch computerunterstützte Hilfsmittel deutlich gesteigert werden. An der Universität von Turin hat man sich das Ziel gesetzt, eine Reihe von integrierten Tools zu entwickeln, die den logischen und physikalischen Entwurf von Datenbanken in einer Codasyl-Umgebung unterstützen. Eine Prototypversion für die Phase des logischen Entwurfs genannt ERCMAP (Entity Realationship to Codasyl Mapping) ist bereits implementiert und wurde mit zufriedenstellendem Erfolg getestet. Das System läuft auf einem VAX 11/780 unter Unix.

Ausgehend von der konzeptionellen Beschreibung der Operationen, die auf der Datenbank ablaufen sollen, wird mit ERCMAP der logische Entwurf optimiert. Das Schema wird einer Reihe von leistungsorientierte Transformationen unterzogen, mit dem Ziel, durch Umstrukturierung und Verfeinerung der Struktur ein logisches Schema zu erhalten, das den Aufwand für jede DB-Operation so gering wie möglich hält. Schritt für Schritt werden alternative Lösungen geprüft, und die Lösung, die am wenigsten kostet, ausgewählt. Als Hauptoptimierungskriterium wird die Anzahl der logischen Entity-Zugriffe pro Zeiteinheit benutzt.

In der Phase des Entwurfs einer Datenbank wird die wirkliche Welt beschrieben in Form

- eines globalen Datenschemas: eine Darstellung der für die Anwendung relevanten Daten (statische Beschreibung)

- einer Aufwandsbeschreibung: eine Darstellung aller Operationen (Abfragen und Transaktionen), die auf der Datenbank ablaufen sollen (dynamische Beschreibung)

- einer quantitativen Beschreibung: sie liefert sogenannte Kardinalitätsinformationen, das sind Information über den Vorrang bestimmter Daten und Datenstrukturen und die Häufigkeit der verschiedenen Operationen.

Die verschiedene Beschreibung werden einer Übereinstimmungskontrolle unterzogen, um eine kohärente und verläßliche Darstellung sicherzustellen.

Ein Datenmodell, das auf der konzeptionellen Ebene eingesetzt wird, sollte dafür taugen, die Semantik der wirklichen Welt in einem klaren Formalismus auszudrücken und dabei flexibel genug sein, um die verschiedenen Umwandlungen einer Beschreibungsebene in eine andere zu erleichtern.

Das bei der Dataid-Methode benutzte Modell ist eine Erweiterung des Netzwerkmodells. Im Netzwerkmodell werden ursprünglich drei verschiedene Klassen von Begriffen festgelegt: Entities, Attribute und Beziehungen. (Präzise unterscheidet man zwischen Entity-Typen, zum Beispiel Angestellter und den konkreten Entity, zum Beispiel der Angestellte Müller; desgleichen bei Beziehungen.) Die Begriffe sollen an einem Beispiel erläutert werden.

Abbildung 1 zeigt das konzeptionelle Schema zur Beschreibung des Projektmanagement eines Unternehmens. "WORKER" und "PROJECT" sind Entities, "salary" und "name" sind Attribute, "Work" eine Beziehung. Die Komplexität von Beziehungen wird mit Hilfe der (minimal, maximal)-Notation ausgedrückt, die angibt, wie oft ein Entity mindestens und höchstens an der Beziehung teilhaben kann. In dem Beispiel muß ein Manager mindestens ein Projekt leiten und jedes Projekt muß mindestens und höchstens einen, also genau einen Manager haben. Attribute können wie bei "adress" zu Aggregaten zusammengefaßt sein.

Eine Menge I von Attributen und/ oder Entities, die ein Entity E eindeutig beschreiben heißt Kennzeichen (identifier) von E. Wenn dieses Kennzeichen nur aus Attributen von E besteht, heißt es internes, sonst externes Kennzeichen. Die Kennzeichen sind in der Abbildung als gestrichelte Pfeile dargestellt. In dem Beilspiel ist "ids" ein internes Kennzeichen (eine Aufgabe wird identifiziert durch den Projektnamen und die Aufgabennummer innerhalb dieses Projektes) und "ida" und "idp" sind externe Kennzeichen.

Die Attribute können zwei Characteristika tragen: funktional/nichtfunktional (F/N) und total/partial (T/P). Nicht funktionale Attribute werden auch wiederholend oder mehrwertig genannt (zum Beispiel "skill" in Abbildung 1).

Aufwands- und quantitative Beschreibung

Das Modell wird schließlich noch durch zwei Abstraktionsmechanismen erweitert: die Begriffe Verallgemeinerung und Untermenge, die nur für Entities definiert sind. Ein Entity-Typ E1 ist eine Untermenge (Ggs. Obermenge) eines anderen Entity-Typs E2, wenn jedes Element von E1 auch ein Element von E2 ist. Ein Entity E ist eine Verallgemeinerung (Ggs. Spezialisierung) der Entity-Typen E1, . . ., En, wenn jedes Element von E ein Element genau einer der Entity-Typen E1, . . ., En ist.

Zusätzlich zu der konzeptionellen Beschreibung der Daten, die in der Datenbank gespeichert werden sollen, benötigt der DB-Designer Information über die zu erwartenden Verarbeitungsanforderungen. Jede Datenbankoperation kann beschrieben werden durch den Zugriffspfad und die Funktion, die die dabei benutzten Attribute für den Datenbankaufruf haben. Jedes Attribut das bei einer Operation benutzt wird, wird mit einem Label versehen, das die Art der Benutzung kennzeichnet. Attribute können zum Beispiel folgendermaßen benutzt und entsprechend gekennzeichnet werden:

k/s: Das Attribut wird für den direkten oder sequentiellen Zugriff auf ein Entity benutzt.

p: Das Attribut wird als Prädikat benutzt, um aus einer Menge von Entities oder Beziehungen ein bestimmtes Vorkommen auszuwählen.

o/v: Das Attribut wird ausgegeben (output) oder nur überprüft (view).

W/d: Das Attribut wird verändert oder gelöscht.

In Abbildung 2 ist eine einfache Operation mit diesen beiden Formalismen beschrieben: "Finde den Namen und die Adresse aller Mitarbeiter, die an Projekt C arbeiten."

Die quantitative Beschreibung liefert Information über die statistische Struktur der Daten. Dazu gehören die zu erwartende Zugriffshäufigkeit auf bestimmte Entities oder Beziehungen und Wahrscheinlichkeitsverteilungen der verschiedenen Werte eines Attributs. Außerdem werden für jede Operation die Frequenz (Zahl der Aufrufe pro Zeiteinheit) und die zeitliche Verteilung festgestellt.

Man muß hier noch einmal betonen, daß der konzeptionelle Entwurf völlig unabhängig von der späteren physischen Realisierung ist und das deshalb die konzeptionelle Zugriffshäufigkeit von der späteren tatsächlichen Zugriffshäufigkeit auf bestimmte Daten abweichen kann. Die statistischen Informationen der quantitativen Beschreibung sind jedoch wichtig, um verschiedene logische Realisierungen des konzeptionellen Schemas auf ihre Effektivität bewerten zu können.

In der Phase des logischen Entwurfs wird das konzeptionelle Schema in ein logisches umgewandelt, das den Codasyl Vorschlagen entspricht. Der Umwandlungsprozeß besteht im wesentlichen aus zwei Verarbeitungsschritten: Vereinfachung des konzeptionellen und Verfeinerung des vereinfachten Schemas.

In dem ersten Schritt werden Datenstrukturen die nicht direkt in das logische Modell überführbar sind, wie zum Beispiel Hierarchien (Verallgemeinerung und Untermenge) und mehrstellige Beziehungen, in einfachere umgewandelt. Man erhält ein vereinfachtes Schema, das nur nicht-hierarchische Entities und zweistellige Beziehungen enthält.

Alternativen optimiert

Im zweiten Schritt wird das vereinfachte Schema einer Reihe von leistungsorientierten Transformationen unterzogen und dabei zwischen möglichen Alternativen so entschieden, daß die Ausführung der wichtigsten Operationen optimiert wird.

Die verschiedenen Lösungen die bei jedem Übersetzungschritt möglich sind, werden überprüft auf die Anzahl der logischen Entity-Zugriffe jeder Operation und die Datenmenge die zwischen Massen- und Hauptspeicher ein- und ausgegeben werden muß und die nach diesen Kriterien optimalste Lösung ausgewählt.

In einem dritten Verarbeitungsschritt wird schließlich die Codasyl Beschreibung generiert.

Abbildung 3 zeigt das fertige Codasyl-Schema. Die Datenbeschreibungssprache die an dieser Stelle benutzt wird, ist eine Untermenge der 1973 vom Codasyl DDL Commitee festgelegten Sprache. Für jedes Entity wird ein Record mit dem gleichen Namen und den gleichen Attributen geschaffen. Die Attribute bilden die Felder des Records und das Hauptkennzeichen (identifier) wird zum Primärschlüssel. Die Beziehungen werden als Sets aufgefaßt, bei denen "Owner" und "Member" festgelegt sind.

Der letzte Verarbeitungsschritt besteht schließlich darin, die in der konzeptuellen Phase festgelegten Operationen so umzustrukturieren daß sie auf das logische Schema anwendbar sind. Abbildung 4 zeigt den Datenbankaufruf des Beispiels als Folge von Befehlen, die auf das Codasyl-Schema angewandt werden.

Der Beitrag basiert auf einem Referat von A. DiLeva und P. Giolito von der Universität Turin anläßlich der 4. Jerusalem Conference on Information Technologies mit dem Titel: "Automatic logical database design in a Codasyl environment".