Benutzer:Dokumentarix/NF2-Relationen
Der Begriff NF2-Relationen wurde 1982 von Gerhard Jaeschke und Hans-Jörg Schek, Mitarbeiter in der Abteilung Advanced Information Management am Wissenschaftlichen Zentrum der IBM in Heidelberg (WZH), in ihrem Papier Remarks on the Algebra of Non First Normal Form Relations[1] eingeführt. Dort stellen sie eine Verallgemeinerung des Relationenmodells von Edgar F. Codd[2] vor, die als Attributwerte von Relationen neben atomaren Werten auch Relationen zulässt. Da in diesem verallgemeinerten Relationenmodell die 1. Normalform (1NF) des originären Relationenmodells aufgehoben wird, haben sie ihr Relationenmodell als Non-First-Normal-Form-Relationen bezeichnet und dafür die Abkürzung NF2 gewählt. Andere hierfür verwendete Bezeichnungen sind geschachtelte Relationen (nested relations)[3] und relationswertige Relationen (relation valued relations).[4]
Allgemein
[Bearbeiten | Quelltext bearbeiten]Da alle Operatoren der Relationenalgebra des 1NF-Relationenmodells entweder eine Relation (Selektion σ, Projektion π) oder zwei Relationen (Vereinigung , kartesisches Produkt , Verbund ⋈) als Eingabe erwarten und jeweils eine Relation als Ausgabe erzeugen, ist es letztlich egal, ob diese in 1NF oder NF2 vorliegen. Das heißt, man kann diese Operatoren auf der Modellebene praktisch unverändert übernehmen (muss ihre formale Definition in Bezug auf Codd aber natürlich entsprechend erweitern.[1]) Neu hinzu kommen bei Jaeschke und Schek die beiden Operatoren νA R für das „Einschachteln“ (nest) und μA R für das „Entschachteln“ (unnest) (weitere Details hierzu folgen unten). - Neben diesen „großen“ Erweiterungen bieten sich allerdings auch einige kleinerer Erweiterungen an,[1] wie z. B. mengenorientierte Filterprädikate (, …) für den Selektions- und den Verbund-Operator, um die volle Mächtigkeit des NF2-Relationenmodells auszuschöpfen zu können.
Nachstehend eine NF2-Relation (mit mengenwertigen Attributen Autor und Deskriptor) sowie die entsprechende Repräsentation dieser Daten als 1NF-Relationen 'Buch', 'Buch_Autor' und 'Buch_Deskriptor' (der „Schlüssel“ ist jeweils unterstrichen).
| Bücher | BuchID | Autor | Titel | Preis | Deskriptor |
|---|---|---|---|---|---|
| B1 | A1, A2 | T1 | P1 | D1, D2 | |
| B2 | A2 | T2 | P2 | D1, D2 | |
| B3 | A1 | T3 | P3 | D1, D2, D3 |
| Buch | BuchID | Titel | Preis |
|---|---|---|---|
| B1 | T1 | P1 | |
| B2 | T2 | P2 | |
| B3 | T3 | P3 |
| Buch_Autor | BuchID | Autor |
|---|---|---|
| B1 | A1 | |
| B1 | A2 | |
| B2 | A2 | |
| B3 | A1 |
| Buch_Deskriptor | BuchID | Deskriptor |
|---|---|---|
| B1 | D1 | |
| B1 | D2 | |
| B2 | D1 | |
| B2 | D2 | |
| B3 | D1 | |
| B3 | D2 | |
| B3 | D3 |
Bezeichne ⋈ den Operator für den natürlichen Verbund (natural join), dann würde der folgende Ausdruck etwa die nachstehende 1NF-Ergebnis-Relation zurückliefern :
Resultat = Buch ⋈ Buch_Autor ⋈ Buch_Deskriptor
| Resultat | BuchID | Autor | Titel | Preis | Deskriptor |
|---|---|---|---|---|---|
| B1 | A1 | T1 | P1 | D1 | |
| B1 | A1 | T1 | P1 | D2 | |
| B1 | A2 | T1 | P1 | D1 | |
| B1 | A2 | T1 | P1 | D2 | |
| B2 | A2 | T1 | P2 | D1 | |
| B2 | A2 | T1 | P2 | D2 | |
| B3 | A1 | T1 | P1 | D1 | |
| B3 | A1 | T1 | P1 | D2 | |
| B3 | A1 | T1 | P1 | D3 |
Wie man bereits an diesem einfachen Beispiel sieht, ist es deutlich schwerer, dieselbe Information aus dieser Ergebnis-Relation herauszulesen als bei der NF2-Relation. Man wird eine 1NF-Ergebnis-Relation dieser Art daher fast nie direkt dem Benutzer anzeigen, sondern sie per Anwendungsprogramm für die Ausgabe erst entsprechend aufbereiten, etwa im Stile einer NF2-Relation.
Der nest-Operator
[Bearbeiten | Quelltext bearbeiten]Bezeichne Attr(R) die Menge der Attribute einer 1NF-Relation R und A eine echte Teilmenge dieser Attribute, d. h. A Attr(R). Der nest-Operator νA R schachtelt Relation R entlang der Attributmenge A von R. Er wirkt hierbei ähnlich wie der GROUP-BY-Operator von SQL angewandt auf (Attr(R) \ A), d. h. bildet Gruppen von Tupeln, die in den restlichen Attributen (d. h. Attr(R) \ A) übereinstimmen. Im Unterschied zu GROUP BY ermittelt der nest-Operator die je Gruppe für A auftretenden Werte und erzeugt für diese das relationswertige Attribut der NF2-Ergebnis-Relation für A.
R1 := vAutor Buch_Autor und R2 := vDeskriptor Buch_Deskriptor würden z. B. die folgenden NF2-Ergebnis-Relationen lieferrn:
| R1 | BuchID | Autor |
|---|---|---|
| B1 | A1,A2 | |
| B2 | A2 | |
| B3 | A1 |
| R2 | BuchID | Deskriptor |
|---|---|---|
| B1 | D1,D2 | |
| B2 | D1,D2 | |
| B3 | D1,D2,D3 |
Der unnest-Operator
[Bearbeiten | Quelltext bearbeiten]Der unnest-Operator ist etwas komplexer in der Implementierung als der nest-Operator. Damit das „Entschachteln“ verlustfrei bzw. eine bijektive Abbildung ist, muss der „Schlüsselpfad“ in der resultierenden 1NF-Relation enthalten sein. Betrachten wir hierzu die NF2-Relation 'Bücher2'. Das Attribut 'Autor' ist jetzt eine zweistellige Relation mit dem atomaren Attribut 'Name' und dem relationswertigen Attribut 'Qualifikation'.
Jedes Tupel der Relation 'Bücher2' (mit Schlüssel 'BuchID') hat nun im Attribut 'Autor' eine „eigene“ Relation, die gemäß der Definition einer Relation jeweils einen Schlüssel hat. Dieser „innere“ Schlüssel bezieht sich jeweils nur auf die Relation im Attribut Autor eines Tupels der Relation Bücher2. Dieser „innere“ Schlüssel wird bei der Unnest-Operation mit in die Ergebnis-Relation übernommen und wird Teil ihres Schlüssels. Bei tieferen Schachtelungen relationswertiger Attribute gilt dies dann natürlich für alle Ebenen.
| Bücher2 | BuchID | Autor | Titel | Preis | |
|---|---|---|---|---|---|
| Name | Qualifikation | ||||
| B1 | A1 | Q1, Q2 | T1 | P1 | |
| A2 | Q3 | ||||
| B2 | A2 | Q3 | T2 | P2 | |
| B3 | A1 | Q1,Q2 | T3 | P3 | |
Die Operation R3 := μAutor Bücher2 erzeugt die folgende 1NF-Ergebnis-Relation:
| R3 | BuchID | A_Name | A_Qualifikation | Titel | Preis |
|---|---|---|---|---|---|
| B1 | A1 | Q1 | T1 | P1 | |
| B1 | A1 | Q2 | T1 | P1 | |
| B1 | A2 | Q3 | T1 | P1 | |
| B2 | A2 | Q3 | T2 | P2 | |
| B3 | A1 | Q1 | T3 | P3 |
Eine ausführlichere Beschreibung zur Relationenalgebra von NF2-Relationen findet sich im Beitrag Schek, H.J.; Scholl, M.H.:" The Relational Model with Relation-valued Attributes"[4] aus dem Jahr 1986, zu Normalformen für NF2-Relationen in Ozsoyoglu, Z.M; Yuan, L.-Y.: „A New Normal Form for Nested Relations“[5] aus dem Jahr 1987 sowie allgemein in vielen Lehrbüchern im Bereich „Datenbanksysteme“.
Zusammenfassend kann man sagen, dass 1NF-Relationen ein Spezialfall von NF2-Relationen sind, d. h. sie sind NF2-Relationen, in denen nur atomare Attribute vorkommen. Dadurch, dass man 1NF-Relation in NF2-Relationen transformieren kann und umgekehrt, kann man NF2-Relationen auf vielfältige Weise nutzen, wie z. B. zur
- kompakteren Speicherung von Relationen (insb. im Kontext komplexer Datenobjekte) im Datenbanksystem-Kern, wie z. B. im DASDBS-System[6]
- Speicherung von vorberechneten Joins, wie z. B. in der Verso-Datenbankmaschine[7]
- Realisierung einer NF2-Sicht auf Basis von 1NF-Relationen[8]
Verwendung der Relationenalgebra
[Bearbeiten | Quelltext bearbeiten]Die Relationenalgebra wurde nur von den ersten experimentellen Datenbanksystemen, wie z. B. dem IBM Peterlee Relational Test Vehicle (PRTV), als Anfragesprache für Benutzer eingesetzt. Heute dient sie als eine Art „Zwischensprache,“ in welche die heute übliche Anfragesprache SQL systemintern übersetzt wird. Dies ist bei NF2-Relationen nicht anders. Für diese wurde im Forschungsbereich „Advanced Information Management“ des WZH die SQL-ähnliche Datenbanksprache HDBL („Heidelberg Database Language“) entwickelt[9][10] und war die Datenbanksprache des experimentellen Datenbanksystems „Advanced Information Management Prototype (AIM-P)“[11][12].
Daten- und Anfragebeispiele
[Bearbeiten | Quelltext bearbeiten]Die folgenden Beispiele und Abbildungen sind mit freundlicher Genehmigung aus dem Vorlesungsskript von P. Dadam: „Datenbanksysteme: Konzepte und Modelle“[13] entnommen. Die Anfragen sind in der Originalsyntax der oben erwähnten Datenbankbanksprache HDBL verfasst.
Als (stark vereinfachtes) Datenbeispiel dient die Beschreibung eines Roboters mit Informationen über seine Arme, den Achsen dieser Arme, über der Gelenkwinkel (JA_min, JA_max) und „DH-Matrixen“ sowie den anschließbaren Endeffektoren.
.jpg)
Roboter-Objekt in „klassischer“ 1NF-Darstellung/Verarbeitung und dessen Folgen
[Bearbeiten | Quelltext bearbeiten]Als 1NF-Relationen dargestellt, könnte dies etwa wie folgt aussehen:
Eine SQL-Anfrage zur Ausgabe aller Daten zu Roboter 'Rob1' könnte man dann z. B. so formulieren:
Das Resultat dieser Anfrage wäre dann die folgende Tabelle:
Diese Tabelle enthält etwa 8 % „Nutzinformation“ und 92 % redundante Einträge. Würde man ganze Fertigungszellen (also Roboter nebst Umgebung) modellieren, kommt man auf ein Vielfaches an benötigten Tabellen. Eine entsprechende Anfrage würde dann mehrere Hundert Spalten und tausende von Zeilen aufweisen und wäre damit völlig unpraktikabel.
Die heutige „Lösung“ des Problems sieht daher in der Regel so aus, dass per Anwendungsprogramm diese Information mittels einer Serie von einzelnen Anfragen iterierend aus der Datenbank geholt wird, um sie dem Anwender in geeignet strukturierter Form anzeigen zu können. Die folgende Abbildung illustriert diese Vorgehensweise. Die Pfeile deuten an, welche Ergebnisse der einen Anfrage als Suchbedingung in eine davon abhängige Folge-Anfrage eingehen.
Bei dieser Vorgehensweise degradiert man die relationale Datenbank praktisch zu einem (etwas komfortableren) Dateisystem.
Roboter-Objekt als NF2-Relation dargestellt
[Bearbeiten | Quelltext bearbeiten]Im NF2-Relationenmodell könnte diese Information für die Ausgabe sehr viel kompakter realisiert werden, wie die beiden folgenden Abbildungen illustrieren.
Die Anweisung zur Erzeugung der oben dargestellten Relation 'RobotNF2' lautet in HDBL wie folgt:
„{ }“ ist hierbei ein Mengenkonstruktor und „[ ]“ ein Tupel-Konstruktor. (HDBL kann mehr als „nur“ NF2, deshalb diese expliziten Festlegungen.) - In dieser CREATE-OBJECT-Anweisung wird angenommen, dass die Endeffektoren jeweils einem Roboter fest zugeordnet sind, deshalb können sie hier im Attribut 'Endeffectors' wie dargestellt komplett „eingeschachtelt“ werden. Können Endeffektoren hingegen mehrfach verwendet werden, dann sollten sie in einer separaten Relation gespeichert werden und die RobotNF2-Relation nur Verweise darauf in Form eines mengenwertigen, einspaltigen Attributs zur Aufnahme der Eff_ID enthalten.
Anfragebeispiele
[Bearbeiten | Quelltext bearbeiten](1) Ausgabe aller Roboter, (2) Ausgabe des Roboters 'Rob1', (3) Ausgabe aller Roboter, die den Endeffektor 'SR200' anschließen können:
.jpg)
Es soll das in der folgenden Abbildung illustrierte Anfrage-Resultat erzielt werden:
.jpg)
Es soll das in der folgenden Abbildung skizzierte Anfrage-Resultat erzielt werden:
Anmerkung zur obigen Anfrage: HDBL kennt unbenamte Attribute. Diese werden über ihren Positions-Index im Tupel referenziert. Ein SELECT auf einem mengen-wertigen Attribut liefert ein solch unbenamtes Attribut zurück. Soll dieses einen Namen erhalten, so muss dieser (wie im Beispiel hier) explizit angegeben werden. Dieser Name ist frei wählbar und kann auch der alte Attributname sein.
Es soll das in der folgenden Abbildung skizzierte Anfrage-Resultat erzielt werden:
.jpg)
.jpg)
Es soll das in der folgenden Abbildung skizzierte Anfrage-Resultat erzielt werden:
Anmerkung: Bei dieser Anfrage werden alle RobotNF2-Tupel ausgegeben. Das Attribut „Endeffektors“ enthält jedoch nur noch Tupel, deren Attribut 'Function' den String „Screw Driver“ enthält.
Es soll das in der folgenden Abbildung skizzierte Anfrage-Resultat erzielt werden:
Anmerkung: HDBL hat hierfür keinen speziellen „Unnest“-Operator, sondern realisiert diese Funktionalität mittels „Self-Join“. Das Tupel [r.RobID, r.Rob_Descr] wird hierbei so häufig mit den Attributen [re.Eff_ID, re.Function] verknüpft, wie die Menge r.Endeffektors für ein gegebenes r Tupel enthält.
Es soll das in der folgenden Abbildung skizzierte Anfrage-Resultat erzielt werden:
Anmerkung: HDBL hat hierfür keinen speziellen „Nest“-Operator, sondern realisiert diese Funktionalität mittels Join-Operation.
Die folgende Anfrage würde eine zur oben abgebildeten RobotsNF2-Relation äquivalente NF2-Ergebnis-Relation ausgeben.
Wurde man diese Anfrage in SQL-Manier als „Sicht“ (view) speichern, dann könnte man dem Benutzer bei Anfragen auf die NF2-Sicht beziehen, obwohl systemintern diese Daten in Form von 1NF-Relationen gespeichert sind.
Anfrage 10 erzeugt allerdings eine NF2-Ausgabe-Relation, die nur „äquivalent“ zu der oben abgebildeten RobotsNF2-Relation ist. „Äquivalent“ bedeutet in diesem Zusammenhang, dass die Reihenfolge der Elemente in allen in der NF2-Relation auftretenden Mengen ohne Belang ist. D. h. weder die Reihenfolge der Roboter, noch die ihrer Arme, ihrer Axen und ihrer Endeffektoren müssen der Reihenfolge in der abgebildeten RobotsNF2-Relation entsprechen. Um eine identische Darstellung zu erhalten, müssen die alle Mengen in der Ergebnis-Relation geeignet sortiert werden. HDBL bietet die Sortierfunktion nur für Listen an, man muss daher eine Menge zunächst mittels der Funktion MLIST in eine Liste umwandeln um darauf dann die ORDER-Funktion anwenden zu können.[14] Die entsprechend ergänzte Anfrage ist nachfolgend dargestellt.
Die mittels Anfrage 11 erzeugte Datenstruktur „verlässt“ das NF2-Datenmodel und könnte daher nicht in einem reinen NF2-Datenbanksystem gespeichert werden. Für Datenobjekte dieser Art benötigt man ein Datenbanksystem wie das oben erwähnte AIM-P mit seiner Datenbanksprache HDBL, das „erweiterte NF2-Relationen“ (eNF2-Relationen)[11][14] unterstützt. Weitergehende Ansätze, wie etwa die Realisierung benutzerdefinierter Datentypen und Funktionen, werden im Artikel Advanced Information Management Prototype' im Kapitel AIM-P - Weiterentwicklung und Erprobung im R2D2-Projekt behandelt.
Endbenutzeraspekte
[Bearbeiten | Quelltext bearbeiten]Ganz am Anfang der Entwicklung der relationalen Datenbanken hatte man noch die Illusion, dass Endbenutzer mittels der Anfragesprache SEQUEL[15] (die später in SQL umbenannt wurde) direkt mit einem relationalen Datenbanksystem interagieren und selbst ihre Anfragen am Bildschirm-Terminal eingeben können. Dies funktioniert auch für einfache Anfragen an eine einzelne Relation und auch die Ausgabe des Ergebnisses als Tabelle ist hierfür gut geeignet. Sobald jedoch mehrere Relationen benötigt werden und deshalb Anfragen mittels Verbundanweisungen (JOIN) formuliert werden müssen, wird es für die meisten Endbenutzer schon zu kompliziert und auch das Anfrage-Resultat ist nun in vielen Fällen nicht mehr so einfach zu verstehen. Mit NF2-Relationen hat man die Möglichkeit, Informationen dieser Art kompakt in einer NF2-Relation darzustellen (entweder als gespeicherte Relation oder als Sicht). Dies vereinfacht zwar die Anfrageformulierung zwar erheblich, da die JOINS entfallen, wird in der Regel aber für Endbenutzer immer noch (viel) zu kompliziert sein.
Mit ESCHER wurde daher im Stile von „Query By Example“ eine vielversprechende graphisch-interaktive Schnittstelle geschaffen, die den gewünschten Objekttyp in seiner NF2-Struktur anzeigt und in der dann vom Benutzer per Anklicken und Eingabe von Auswahlbedingungen die Anfrage näher spezifiziert werden kann.[16][17]
Literaturbelege
[Bearbeiten | Quelltext bearbeiten]- ↑ a b c G. Jaeschke, H. J. Schek: Remarks on the algebra of non first normal form relations. In: Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems (= PODS '82). Association for Computing Machinery, New York, NY, USA 29. März 1982, S. 124–138, doi:10.1145/588111.588133.
- ↑ E. F. Codd: A relational model of data for large shared data banks. In: Communications of the ACM. Band 13, Nr. 6, 1. Juni 1970, ISSN 0001-0782, S. 377–387, doi:10.1145/362384.362685.
- ↑ S. Abiteboul, P. C. Fischer, H.-J. Schek (Hrsg.): Nested relations and complex objects in databases. Springer-Verlag, Berlin 1989, ISBN 0-387-51171-7.
- ↑ a b H.-J. Schek, M.H. Scholl: The relational model with relation-valued attributes. In: Information Systems. Band 11, Nr. 2, Januar 1986, S. 137–147, doi:10.1016/0306-4379(86)90003-7 (elsevier.com [abgerufen am 7. Oktober 2022]).
- ↑ Z. Meral Ozsoyoglu, Li-Yan Yuan: A new normal form for nested relations. In: ACM Transactions on Database Systems. Band 12, Nr. 1, März 1987, ISSN 0362-5915, S. 111–136, doi:10.1145/12047.13676 (acm.org [abgerufen am 7. Oktober 2022]).
- ↑ H.-J. Schek: Ein Datenbank-Kernsystem für anwendungsspezifische Schichten - Architektur der DASDBS-Familie / A Database Kernel System Supporting Application-Specific Layers- Architecture of the DASDBS Family. In: itit. Band 29, Nr. 3, März 1987, ISSN 2196-7032, S. 153–164, doi:10.1524/itit.1987.29.3.153 (degruyter.com [abgerufen am 7. Oktober 2022]).
- ↑ M. Scholl, S. Abiteboul, F. Bancilhon, N. Bidoit, S. Gamerman: Verso: A database machine based on nested relations. In: Nested Relations and Complex Objects in Databases. Band 361. Springer Berlin Heidelberg, Berlin, Heidelberg 1989, ISBN 3-540-51171-7, S. 27–49, doi:10.1007/3-540-51171-7_19 (springer.com [abgerufen am 7. Oktober 2022]).
- ↑ R. Lorie, H. -J. Schek: On dynamically defined complex objects and SQL. In: Advances in Object-Oriented Database Systems. Band 334. Springer Berlin Heidelberg, Berlin, Heidelberg 1988, ISBN 3-540-50345-5, S. 323–328, doi:10.1007/3-540-50345-5_30 (springer.com [abgerufen am 7. Oktober 2022]).
- ↑ H.-J. Schek, P. Pistor: Data Structures for an Integrated Data Base Management and Information Retrieval System. In: VLDB '82: Proc.8th International Conference on Very Large Data Bases, Mexico City, Mexico. September 1982, S. 197–207 (vldb.org [PDF]).
- ↑ P. Pistor, F. Andersen: Designing a Generalized NF2 Model with an SQL-Type Language Interface. In: Proc. VLDB'86, Int. Conf. on Very Large Databases, Kyoto, Japan. 1986, S. 278–285.
- ↑ a b Peter Pistor, Peter Dadam: The advanced information management prototype. In: Nested Relations and Complex Objects in Databases. Band 361. Springer Berlin Heidelberg, Berlin, Heidelberg 1989, ISBN 3-540-51171-7, S. 1–26, doi:10.1007/3-540-51171-7_18 (springer.com [abgerufen am 20. Oktober 2022]).
- ↑ P. Dadam, K. Kuespert, F. Andersen, H. Blanken, R. Erbe: A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies. In: ACM SIGMOD Record. Band 15, Nr. 2, 15. Juni 1986, ISSN 0163-5808, S. 356–367, doi:10.1145/16856.16889 (acm.org [abgerufen am 20. Oktober 2022]).
- ↑ Peter Dadam: Datenbanksysteme - Konzepte und Modelle (Vorlesung). Kapitel 7: Relationales Datenmodell III:NF2- und eNF2-Relationenmodell, 2013, S. 269–342 (researchgate.net).
- ↑ a b P. Pistor, R. Traunmueller: A database language for sets, lists and tables. In: Information Systems. Band 11, Nr. 4, Januar 1986, S. 323–336, doi:10.1016/0306-4379(86)90012-8 (elsevier.com [abgerufen am 28. Oktober 2022]).
- ↑ Donald D. Chamberlin, Raymond F. Boyce: SEQUEL: A structured English query language. In: Proceedings of the 1976 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control - FIDET '76. ACM Press, Not Known 1976, S. 249–264, doi:10.1145/800296.811515 (acm.org [abgerufen am 4. November 2022]).
- ↑ K. Küspert, J. Teuhola, L. Wegner: Design issues and first experiences with a visual database editor for the extended NF/sup 2/-data model. In: Twenty-Third Annual Hawaii International Conference on System Sciences. ii. IEEE Comput. Soc. Press, Kailua-Kona, HI, USA 1990, S. 308–317, doi:10.1109/HICSS.1990.205202 (ieee.org [abgerufen am 4. November 2022]).
- ↑ Lutz M. Wegner: Let the fingers do the walking: Object manipulation in an NF2 database editor. In: New Results and New Trends in Computer Science. Band 555. Springer-Verlag, Berlin/Heidelberg 1991, ISBN 3-540-54869-6, S. 337–358, doi:10.1007/bfb0038201 (springer.com [abgerufen am 4. November 2022]).