[Zurück]

W. Fischl:
"Normal Forms for Non-Relational for Data";
Betreuer/in(nen): R. Pichler; Institut für Informationssysteme, 2013; Abschlussprüfung: 19.11.2013.

Die Menge an von Informationssystemen gespeicherten Daten wächst stetig. Für diesen Zweck
werden vorwiegend Datenbanksysteme eingesetzt. Jedoch gewinnen alternative Datenformate,
wie XML Dokumente und Graph-basierte Datenbanken, immer mehr an Einfluss. In all diesen
Datenformaten ist es wichtig, mit Hilfe des Datenbankdesigns Redundanzen zu vermeiden. Sol-
che können bei einem schlecht konzipierten Datenmodell auftreten. Deshalb wurden Normalfor-
men entwickelt, um Datenmodelle zu schaffen, welche keine vermeidbaren Redundanzen mehr
enthalten. Für das relationale Datenmodell wird Boyce-Codd Normalform (BCNF) verwendet.
Arenas und Libkin entwickelten 2004 XML Normalform für XML Dokumente. Normalformen
für Graph-basierte Datenbanken wurden bisher nicht untersucht. Unser Ziel ist es, diese Lücke
zu schließen. Wir wollen eine Normalform definieren, welche die Eigenschaften von BCNF auf
Graph-basierte Datenbanken überträgt.
Zuerst werden wir Boyce-Codd und XML Normalform betrachten. Ideen aus diesen Normalfor-
men verwenden wir dazu, um eine Normalform für Graph-basierte Datenbanken zu entwickeln.
Beschreibungslogiken (DLs) sind als formales Modell für Graph-basierte Datenbanken über-
aus passend. Da BCNF mittels funktionaler Abhängigkeiten definiert ist, muss es uns möglich
sein solche auch über DL Wissensbasen (DL KBs) auszudrücken. Ein naheliegender Kandidat
sind die von Calvanese et al. 2008 eingeführten path-based identification constraints verwen-
den. Allerdings zeigen wir, dass path-based identification constraints nicht ausdrucksstark genug
sind, um funktionale Abhängigkeiten in DLs zu modellieren. Deshalb erweitern wir path-based
identification constraints zu tree-based identification constraints. Mittels diesen untersuchen wir
Redundanzen in DL KBs.
Der Hauptbeitrag dieser Arbeit ist eine Definition der Beschreibungslogik Normalform (DLNF),
welche eine sinnesgetreue Erweiterung der BCNF zu DLs ist. Zusätzlich stellen wir eine direkte
Abbildung von relationalen Schemata auf DL KBs vor. Wir zeigen, dass jedes relationale Sche-
ma genau dann in BCNF ist, wenn auch die direkte Abbildung dieses Schemas auf eine DL KB
in DLNF ist und umgekehrt.

The amount of data stored in today´s information systems is increasing rapidly. Most widely
used for this task are relational database management systems. However, alternative data for-
mats, like XML documents or graph databases, continue to become more and more popular. In
all these data formats database design is an important task to avoid redundancies arising from
badly designed schemata. Therefore, Normal Forms were developed. Most prominently, Boyce-
Codd Normal Form (BCNF) is used for relational models. Arenas and Libkin introduced 2004
XML Normal Form for XML documents. So far, a normal form for graph databases has not
been considered yet. Our goal is to define a normal form that captures the intuition of BCNF for
graph databases.
We will recall Boyce-Codd Normal Form and XML Normal Form and will then use ideas from
these to define a normal form for graph databases. Description Logics (DLs) are ideally suited
as a formal model for graph databases. Since BCNF is formulated over functional dependencies
(FDs), we need to express FDs over DL knowledge bases (KBs). A first candidate are path-based
identification constraints introduced by Calvanese in 2008. However, we show that path-based
identification constraints are not powerful enough to model functional dependencies. Therefore,
we propose tree-based identification constraints as an extension of path-based identification con-
straints. Based on tree-based identification constraints we look at redundancy in DLs.
The main result of this thesis is a definition of Description Logic Normal Form, which is a
faithful translation of BCNF to Description Logics. Additionally, we introduce a direct mapping
from relational schemas to DL KBs and show that if a relational schema is in BCNF, then the
DL KB, directly mapped from this schema, is in DLNF and vice versa.

RDF

Projektleitung Reinhard Pichler:
Heterogene Information Integration

Projektleitung Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions