Benutzer:Dokumentarix/Erweiterte NF2-Relationen

Erweiterte NF2-Relationen, abgekürzt eNF2-Relationen, sind ein Datenmodell für Datenbanksysteme das festlegt, welche Datenstrukturen zur Speicherung von Daten und welche Operationen für Abfragen sowie zum Einfügen, Ändern und Löschen ein solches Datenbanksystem an seiner Benutzerschnittstelle anbietet. Die heute gängigen relationalen Datenbanksysteme speichern ihre Daten in Form von einfachen Tabellen, im Fachjargon Relationen genannt ab. Diese Art der Datenspeicherung hat viele Vorteile, bereitet jedoch Probleme, wenn komplex strukturierte Daten, wie z.B. die CAD-Daten für die Konstruktion eines Pkw, zu verwalten sind. Aus diesem Grund wurden diverse Erweiterungen vorgeschlagen[1], wie z.B. die sog. NF2-Relationen, die erlauben, dass diese Tabellen geschachtelt sein können. Diese Erweiterung ist für einige Anwendungen bereits hilfreich, reicht aber z.B. für die adäquate Darstellung der schon erwähnten CAD-Daten eines Pkw noch nicht aus. Die im Folgenden beschriebenen erweiterten NF2-Relationen, abgekürzt eNF2-Relationen, stellen eine erhebliche Erweiterung der NF2-Relationen dar.

Die eNF2-Relationen wurden in den 1980er Jahren am Wissenschaftlichen Zentrum der IBM in Heidelberg (WZH) im Rahmen des Projekts "Advanced Information Management Prototype" (AIM-P) [2][3] entwickelt. In diesem Projekt wurden viele technisch-wissenschaftliche sowie andere Anwendungen im Hinblick auf deren Anforderungen an Datenstrukturen untersucht, die ein "Next-Generation"-Datenbanksystem anbieten sollte, um Anwendungen der jeweiligen Art adäquat zu unterstützen.

Wissenschaftliche und praktische Bedeutung

Bearbeiten

Die eNF2-Relationen haben national international viele Forschungsarbeiten inspiriert, sei es mit direktem Bezug zu NF2 [4][5][6], für anspruchsvolle Anwendungen [7][8][9] oder für die semantische Datenmodellierung [10][11]. Sie haben Eingang in Lehrbücher im Bereich Datenbanksysteme [12][13][14] gefunden und sind fester Bestandteil vieler Datenbankvorlesungen an Universitäten und Hochschulen. Sie spielten Anfang der 1990er Jahre auch eine wichtige Rolle in der Diskussion im ISO-SQL-Gremium über die Erweiterungen von SQL in der nächsten Version des SQL-Standards.

Motivation

Bearbeiten

NF2-Relationen im Vergleich zu den klassischen Relationen, deren Attributwerte wegen der 1. Normalform stets atomar sein müssen (im Folgenden als "1 NF-Relationen" oder "flache Relationen" bezeichnet), bereits eine erhebliche Verbesserung dar wenn es darum geht, komplexe Datenobjekte zu speichern und als Anfrageergebnisse auszugeben (siehe Beispiel im NF2-Beitrag)).

Für die Anfragebeispiele wird im Folgenden die für das eNF2-Relationenmodell am WZH entwickelte Datenbanksprache HDBL ("Heidelberg Database Language") [2][15][16] verwendet. Die Beispiele und Graphiken in diesem Beitrag sind, mit dessen Einverständnis, dem Vorlesungsskript "Peter Dadam: Datenbanksysteme - Konzepte und Modelle" [17] entnommen.  

 
Abb. 1: Modelllierung eines Roboters (vereinfacht)
 
Abb. 2: Roboter-Objekte als Tupel einer NF2-Relation

NF2-Relationen haben allerdings dasselbe Problem wie 1NF-Relationen: Sie handhaben 'Mengen von Tupeln' und Mengen haben - wie in der Mathematik - keine feste Reihenfolge ihrer Elemente. Sowohl bei 1NF- als auch bei NF2-Relationen muss man in Anfragen daher Sortieroperationen einfügen, um das Resultat in der gewünschten Reihenfolge ausgeben zu können. Dies ist bei kleinen Datenmengen noch hinnehmbar, wird allerdings bei großen Datenmengen zum Problem. Nehmen wir der Einfachheit halber an, wir haben bei vielen Objekten eine Liste von bis zu 10.000 Integerwerten (z.B. als Messergebnisse eines Sensors) zu speichern. Da deren Reihenfolge natürlich relevant ist, müssen wir die Werte als 2-stelliges Tupel für die Aufnahme des Werte und dessen Position in der Liste speichern; und beim Auslesen müssen wir diese Tupelmenge dann auch noch nach der Positionsnummer sortieren. Andere Beispiele dieser Art treten z.B. beim Hinterlegen von Bahnkurven auf, welche etwa mittels Polygonzügen die Bewegung der Endpunkte eines Roboterarms für die Durchführung einer bestimmten Aufgabe im Zeitverlauf beschreiben und z.B. für die Kollisionserkennung verwendet werden. Hier sind die Einträge dann z.B. Tupel der Form [ zeitpunkt, x, y, z ]. Auch diese Listen können, je nach geforderter Genauigkeit der Approximation der realen Bahnkurve, ebenfalls sehr lang werden. - Diese Beispiele legen nahe, dass das Datenmodell eines "Next-Generation"-Datenbanksystems neben Mengen von Tupeln zumindest auch 'Listen von Tupeln' sowie 'Listen von atomaren Werten' unterstützen sollte.

Aber Listen von Tupeln und Listen von atomaren Werten sind auch noch nicht ausreichend. Betrachten wir hierzu die NF2-Relation in Abb. 2. Das mengenwertige Attribut DH_Matrix ist eine mögliche Speicherung einer 4x4-Matrix. Nehmen wir an, wir möchten auf das Element (3,2), d.h. in der 3-ten Zeile und der 2-ten Spalte dieser Matrix von Roboter 'Rob1' im Arm 'A1' und Achse 1 zugreifen. Dann müssen wir in der Sub-Anfrage für das Attribut DH_Matrix eine SELECT-Anweisung etwa der folgenden Art (in HDBL-Syntax) verwenden, was spätestens bei höherdimensionalen Matrizen sehr unschön wird.

 
HDBL-Bsp. 1

Wesentich einfacher wird es, wenn das Datenmodell auch Listen von Listen von Tupeln oder atomaren Werten unterstützt, wie in der folgenden Abbildung für das Roboter-Objekt dargestellt. In diesem Beispiel sind 'Axes' und 'DH_Matrix' als listenwertige Attribute realisiert, was durch die Klammern "< ...>" angezeigt wird.

 
Abb. 3: Roboter-Objekte als Tupel einer eNF2-Relation

Der in Anfrage 1 beschriebene Zugriff auf das Matrix-Element (3,2) könnte in HDBL in der Sub-Anfrage für das Attribut DH_Matrix wie folgt formuliert werden:

 
HDBL-Bsp. 2

Auch die Forderung, dass das Anfrageergebnis immer eine Menge von ... oder eine Liste von ... sein muss, ist nicht immer problem-adäquat. Es gibt im jeweils betrachteten Kontext oftmals eine ganze Reihe von singulären Datenobjekten, wie z.B. das eigene Unternehmen (als ein komplex strukturiertes Datenobjekt), die höchste bereits vergebene Rechnungsnummer (lange, positive Ganzzahl) usw. - Wie im nächsten Abschnitt ausgeführt, gibt es aber noch viel gewichtigere Gründe, auch atomare Werte als "Top-Level"-Datenbankobjekte zuzulassen.

Das eNF2-Relationen-Modell

Bearbeiten

Zielsetzung

Bearbeiten

Das Ziel beim Entwurf des eNF2-Datenmodells war, das NF2-Datenmodell so zu erweitern, dass

  1. es alle als relevant identifzierten Datenstrukturen anbietet
  2. dafür eine adäquate SQL-ähnliche Hochsprache geschaffen werden kann
  3. das Ergebnis jeder Anfrage wieder ein legales Objekt dieses Datenmodells zurück liefert

Das dritte Teilziel ist wichtig, damit jedes solches "Resultat-Objekt" sowohl als Zwischenergebnis in geschachtelten Anfrageausdrücken auftreten als auch "as is" als legales Datenobjekt wieder in der Datenbank gespeichert werden kann.

Das Ergebnis dieser Untersuchungen und Überlegungen führen zu dem nachstehend illustrierten eNF2-Datenmodell. Abb. 4 veranschaulicht die Evolution des relationalen Datenmodells von 1NF via NF2 zu eNF2.

 
Abb. 4: Evolution der relationalen Datenmodelle

Im eNF2-Datenmodell können alle Konstruktoren (list, set, tuple) und atomaren Werte sowie alle Kombinationen von diesen sowohl als singuläre Objekte, als Top-Level-Objekte oder als Attributwerte oder Elemente von Mengen oder Listen auftreten.[16]

Die folgende Tabelle zeigt im Detail die Unterschiede der strukturellen Ausdruckmächtigkeit der drei relationalen Datenmodelle. Die Einträge in der Spalte 'Toplevel-Typ' zeigen an, welcher Objekttyp z.B. mit CREATE object ... erzeugt werden kann. Die 1NF- und NF2-Relationen kennen nur die Menge ("Relation") als Toplevel-Typ, während bei eNF2 alle Typen zugelassen sind. Die Spalten im Bereich 'kann enthalten' zeigen an, mit welchen Typen der in Spalte 'Typ' stehende Typ kombiniert werden kann. Bei 1NF und NF2 kommt nur der Toplevel-Typ 'Menge' in Frage und der kann in beiden Fällen nur mit 'Tupel'" kombiniert werden. Beim 'Tupel'-Typ tun sich dann die Unterschiede auf: Bei 1NF kommt nur 'Atom' in Frage, während bei NF2 'Atom' und 'Menge' möglich sind und eNF2 alle Kombinationen erlaubt.

kann enthalten
Toplevel-Typ Typ Menge Liste Tupel Atom
1NF + Menge - - + -
NF2 + + - + -
eNF2 + + + + +
1NF - Liste - - - -
NF2 - - - - -
eNF2 + + + + +
1NF - Tupel - - - +
NF2 - + - - +
eNF2 + + + + +
1NF - Atom - - - -
NF2 -
eNF2 +
Abb. 5: 1NF-, NF2- und eNF2-Strukturen im Vergleich

Typ-Konstruktoren, -Konversionen und typbezogene Operationen von HDBL (Auswahl)

Bearbeiten
Art für Syntax Wirkung / Anmerkung
Konstruktor Tupel [ elem1, elem2, ..., elemn ] 1..n homogene oder heterogene Elemente
Menge { elem1, elem2, ..., elemn } 0..n homogene Elemente
Liste < elem1, elem2, ..., elemn > 0..n homogene Elemente
Typumwandlung Menge → Liste MLIST( menge )
Liste → Menge ELEMS( liste )
Abb. 6: Konstruktoren und Typumwandlungen (für Objektdeklarationen und in Anfragen)
anwendbar auf Art der Operation Operator (Syntax) Resultat-Typ
Menge, Liste Iteratoren (zum Zugriff auf Elemente) FOR_EACHINDO ... wie Input
Menge, Liste Löschen eines Elements DELETE element -
Menge Vereinigung menge1 UNION menge2 Menge
Menge Durchschnitt menge1 INTERSECT menge2 Menge
Menge Differenz menge1 MINUS menge2 Menge
Menge Einfügen INSERT menge1 INTO menge2 Menge
Menge Ermitteln Kardinalität CARD( menge ) Zahl
Liste Konkatenation liste1 || liste2 Liste
Liste Positioniertes Einfügen EXTEND liste1 WITH liste2 { BEFORE | AFTER } pos Liste
Liste Zugriff auf Teillisten SUBLIST( startpos, anzElemente, liste ) Liste
Liste Ermitteln Länge LEN ( liste ) Zahl
Liste Sortierung ORDER x IN liste BY x { ASC | DESC } Liste
Menge, Liste Gruppierung GROUP x IN { menge | liste } BY x { Menge von Mengen | Liste von Listen }
Menge, Liste Duplikateliminierung UNIQUE ( { menge | liste } ) wie Input
Abb. 7: Operationen auf eNF2-Objekten

Abb. 7 listet auf, welche Operatoren die Sprache HDBL zur Verwendung in Datenbankanfragen und -änderungsanweisungen zur Verfügung stellt. Die Operatoren Vereinigung, Durchschnitt, Differenz und Kardinalität dürften einigen Lesern von der Mengenlehre her bekannt sein. Die danach folgenden Operationen dienen dazu Listen von Elementen (z.B. Zahlen, Tupel, usw.) zu bearbeiten. Wer schon einmal mit der Datenbanksprache SQL zu tun hatte, dem wird vielleicht der GROUP-Operator bekannt vorkommen. Der GROUP-Operator macht aus einer Menge von Elementen eine 'Menge von Mengen' von Elementen, in dem angegebenen 'x' (das kann ein Attribut oder eine Listen von Attributen sein) übereinstimmen. In SQL kann dieser Operator aber immer nur in Verbindung mit einer sog. Aggregtatfunktion (wie SUM, ADD, COUNT, ...) verwendet werden, die dafür sorgt, dass jede dieser Teilmengen jeweils wieder auf ein Tupel "geschrumpft" wird.

So ganz trivial ist die Implementierung von Operatoren zur Gruppierung, Sortierung sowie Duplkatateliminierung im eNF2-Kontext nicht, da hier nun (ggf. auch geschachtelte Mengen oder Listen) als "Vergleichsobjekte" auftreten können. Fragen wie z.B.: "Ist { 1,3,8 } größer oder kleiner als { 2,4,5,6 } ?" erfordern eine präzise Beschreibung der Semantik dieser Operationen, um sie in einem Datenbanksystem sinnvoll realisieren und verwenden zu können.[18][19]

Daten- und Anwendungsbeispiele

Bearbeiten

Da die reinen NF2-Strukturen des eNF2-Datenmodells bereits ausführlich im Betrag zu den NF2-Relationen behandelt werden, beschränken sich die folgenden Beispiele auf die zusätzlichen Eigenschaften, die das eNF2-Datenmodell mit sich bringt.

Beispiele für CREATE-Anweisungen für Objekte

Bearbeiten
  • Erzeugen einzelnes (flaches) Tupel als Datenbank-Objekt
     
    HDBL-Bsp. 3
     
  • Erzeugen einzelnen Integerwert als Datenbank-Objekt
     
    HDBL-Bsp. 4
     
  • Erzeugen einzelne Liste von Integer-Werten als Datenbank-Objekt
     
    HDBL-Bsp. 5
     
  • Erzeugen Robot_eNF2-Objekt
     
    HDBL-Bsp. 6

Beispiele für SELECT-Anweisungen

Bearbeiten
  • Ausgabe der kompletten Robot_eNF2-Relation
     
    HDBL-Bsp. 7 + 8
  • Ausgabe aller Roboter, die mindestens 2 Arme haben
     
    HDBL-Bsp. 9
  • wie HDBL-Bsp. 9 + Greifer 'GR800' muss anschließbar sein
     
    HDBL-Bsp. 10
  • Ausgbe der RobID aller Roboter, die im 4. Element jeder 3. Matrixzeile den Wert 40 aufweisen
     
    HDBL-Bsp. 11
  • Wie HDBL-Bsp. 11, jedoch sollen zudem noch die Menge der ArmIDs ausgeben werden, deren Matrizen diese Bedingung erfüllen
     
    HDBL-Bsp. 12
    Erläuterung zu HDBL-Bsp. 12: In der äußeren WHERE-Bedingung (1) werden alle Toplevel-Tupel in Roboter-eNF2 ausgewählt, bei denen mindestens ein Roboter-Arm diese Bedingung erfüllt. Die innere WHERE-Bedingung (2) regelt, welche Arme von diesen Robotern die Anfragebedingung erfüllen und nur deren ArmID wird ausgewählt und ausgegeben.

Beispiele für Einfüge-Anweisungen

Bearbeiten
  • Ein neuer Roboter 'Rob4' soll eingefügt werden
     
    HDBL-Bsp. 13
  • Roboter 'Rob2' soll weitere Endeffektoren erhalten
     
    HDBL-Bsp. 14

Beispiele für Änderungs-Anweisungen

Bearbeiten
  • Die Funktionsbeschreibung des Sensors SN200 von 'Rob1' soll geändert werden
     
    HDBL-Bsp. 15
    Anmerkung: Wenn die Eff_ID eindeutig ist, kann man die obere WHERE-Bedingung "… WHERE r.RobID = 'Rob1' " weglassen.
  • Ersetzen der kompletten Endeffektor-Menge von 'Rob4'
     
    HDBL-Bsp. 16
  • Zuweisung an das singuläre Objekt 'Mitarbeiter_Heinze' (siehe oben)
     
    HDBL-Bsp. 17
  • Zuweisungen an das singuläre Listenobjekt 'MessreiheEinzeln' (siehe oben)
    • Komplettes Ersetzen des Inhalts
       
      HDBL-Bsp. 18
    • Hinzufügen am Ende
       
      HDBL-Bsp. 19
    • Einfügen am Anfang
       
      HDBL-Bsp. 20

Beispiele für Lösch-Anweisungen

Bearbeiten
  • Screw Driver 'SD200' steht 'Rob1' nicht mehr zur Verfügung
     
    HDBL-Bsp. 21
  • Die Einträge des singulären Objekts 'Mitarbeiter_Heinze' sollen gelöscht werden
     
    HDBL-Bsp. 22

Abschließende Bemerkungen

Bearbeiten

Insbesondere für technisch-wissenschaftliche Datenobjekte reicht es nicht aus, für diese nur geeignete Speicherstrukturen bereitzustellen, sondern man benötigt in der Regel auch objekt-spezifische Funktionen um die Datenobjekte (oder Teile davon) zu erstellen, zu verändern und evtl. auch für ihre graphische Visualisierung. Im Rahmen des eingangs erwähnten AIM-P-Projektes wurde HDBL daher durch Benutzerdefinierte Datentypen und Benutzerdefinierte Funktionen erweitert.

Die eNF2-Relationen Anfang der 1990er Jahre in der Diskussion im ISO-SQL-Gremium über die Erweiterungen von SQL in der nächsten Version des SQL-Standards. Wie diese Diskussion verlief und für welchen Ansatz man sich am Ende entschieden hat, kann man hier nachlesen.

Einzelnachweise

Bearbeiten
  1. 30 Jahre „Datenbanksysteme für Business, Technologie und Web“: Die BTW im Wandel der Datenbank-Zeiten. In: Datenbank-Spektrum. Band 15, Nr. 1, März 2015, ISSN 1618-2162, S. 81–90, doi:10.1007/s13222-015-0183-4 (springer.com [abgerufen am 31. Dezember 2022]).
  2. 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 978-3-540-51171-7, S. 1–26, doi:10.1007/3-540-51171-7_18 (springer.com [abgerufen am 20. Oktober 2022]).
  3. 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]).
  4. L. Wegner, M. Paul, R. Colomb: Variants and Recursive Types in the eNF2 Data Model. In: Technical Report, Dept. of Computer Science, Univ. of Queensland, Brisbane, Australia. Band 233, Juni 1992 (researchgate.net [PDF]).
  5. N. Lachmann: Operationen auf komplexen Objekten in ORDBMS: Analyse, Vergleich und Optimierung. In: M. Samia, S. Conrad (Hrsg.): Tagungsband zum 16. GI-Workshop Grundlagen von Datenbanken, Mohnheim. Juni 2004, S. 83–87 (uni-duesseldorf.de [PDF]).
  6. Gunter Saake, Ralf Jungclaus, Cristina Sernadas: Abstract data type semantics for many-sorted object query algebras. In: MFDBS 91. Band 495. Springer Berlin Heidelberg, Berlin, Heidelberg 1991, ISBN 978-3-540-54009-0, S. 291–307, doi:10.1007/3-540-54009-1_21 (springer.com [abgerufen am 20. Oktober 2022]).
  7. Manfred Gärtner: Die Eignung relationaler und erweiterter relationaler Datenmodelle für das Data Warehouse. In: Das Data Warehouse-Konzept. Gabler Verlag, Wiesbaden 1998, ISBN 978-3-409-32216-4, S. 195–217, doi:10.1007/978-3-322-99372-4_6 (springer.com [abgerufen am 20. Oktober 2022]).
  8. Eitel von Maur: Object Warehouse - Konzeption der Basis objektorientierter Management Support Systems am Beispiel von Smalltalk und dem ERP Baan. In: Fachbereich Wirtschaftswissenschaften, Universität Osnabrück, Dissertation. Mai 2000 (uni-osnabrueck.de [PDF]).
  9. Alfons Kemper, Mechtild Wallrath: An analysis of geometric modeling in database systems. In: ACM Computing Surveys. Band 19, Nr. 1, März 1987, ISSN 0360-0300, S. 47–91, doi:10.1145/28865.28866 (acm.org [abgerufen am 20. Oktober 2022]).
  10. S. Thelemann: Semantische Anreicherung eines Datenmodells für komplexe Objekte. Dissertation, Fachbereich Mathematik/Informatik der Universität Gesamthochschule Kassel, Mai 1996 (uni-kassel.de [PDF]).
  11. Saulius Gudas, Andrius Valatavicius: Normalization of Domain Modeling in Enterprise Software Development. In: Baltic Journal of Modern Computing. Band 5, Nr. 4, Dezember 2017, doi:10.22364/bjmc.2017.5.4.01 (lu.lv [PDF; abgerufen am 20. Oktober 2022]).
  12. Stefan M. Lang, Peter C. Lockemann: Das NF2-Modell. In: Datenbankeinsatz. Springer Berlin Heidelberg, Berlin, Heidelberg 1995, ISBN 978-3-642-63353-9, S. 97–118, doi:10.1007/978-3-642-57782-6_5 (springer.com [abgerufen am 20. Oktober 2022]).
  13. Andreas Heuer, Gunter Saake, Kai-Uwe Sattler: Datenbanken - Konzepte und Sprachen Buch, 6. Auflage. mitp, 2018, ISBN 978-3-95845-776-8 (vdoc.pub).
  14. Gunter Saake, Ingo Schmitt, Can Türker: Objektdatenbanken - Konzepte, Sprachen, Architekturen. 2003 (uni-magdeburg.de [PDF]).
  15. Peter Pistor, Flemming Andersen: Designing A Generalized NF2 Model with an SQL-Type Language Interface. In: Proc. VLDB'86, 12th International Conference on Very Large Data Bases, Kyoto, Japan. 1968, S. 278–285 (researchgate.net).
  16. 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 29. Oktober 2022]).
  17. Peter Dadam: Datenbanksysteme - Konzepte und Modelle (Vorlesung). 2013, Kapitel 7: Relationales Datenmodell III: NF2- und eNF2-Relationenmodell, S. 269–342 (researchgate.net).
  18. G. Saake, V. Linnemann, P. Pistor, L. Wegner: Sorting, Grouping and Duplicate Elimination in the Advanced Information Management Prototype. In: VLDB '89: Proc. 15th Int. Conf. on Very Large Data Bases, Amsterdem. 1989 (acm.org).
  19. K. Küspert, G. Saake, L. Wegner: Duplicate detection and deletion in the extended NF2 data model. In: Foundations of Data Organization and Algorithms. Band 367. Springer Berlin Heidelberg, Berlin, Heidelberg 1989, ISBN 978-3-540-51295-0, S. 83–100, doi:10.1007/3-540-51295-0_120 (springer.com [abgerufen am 21. Oktober 2022]).

Kategorie:Datenbanktheorie