|

 

Dbis.cs.uni-frankfurt.de

Formale Betrachtung von Anfragen auf
RDF Datenbanken
im Fachbereich Biologie und Informatik an der Johann Wolfgang Goethe Universität Frankfurt am Main bei Herrn Prof. Dott. Ing. Zicari betreut von Dipl. Math. Karsten Tolle Bartholomäus Ende Inhaltsverzeichnis Bartholomäus Ende Matr.-Nr. 2063702 1. Kurzfassung
Dieses Dokument befasst sich mit der formalen Analyse von Anfragen auf RDF-Datenbanken. Zu diesem Zweck wird zunächst eine kurze Einführung in das Resource Description Framework (RDF) gegeben. Für die folgende formale Betrachtung der Abfrageverarbeitung werden sodann eine einfache Ab-fragesprache sowie zwei mögliche Definitionen von Antworten eingeführt und analysiert. Des Wei-teren werden Aspekte wie die statische Optimierung von Abfragen, die Entfernung von Redundan-zen aus Antworten sowie die Besonderheiten, die sich durch blank Nodes und Reification ergeben, behandelt. Den Abschluss bildet eine Motivation von RAL, einer RDF-Algebra, die zukünftig nicht nur die Definition sondern auch den Vergleich von unterschiedlichen Abfragesprachen ermöglichen könn-te. Zudem bietet sie auch das Potential, die bei relationalen Datenbanken üblichen algebraischen Optimierungen auch auf RDF Anfragen anzuwenden. 2. Einleitung
Die rasante Entwicklung von Informationstechnologien führt zu immer neuen Herausforderungen für die Verwaltung von Daten. Hierbei generiert speziell die Realisierung einer effizienten Nutzung der Inhalte, die durch das WWW bereitgestellt werden, neue Herausforderungen für den Zugriff auf die gebotene Flut von multimedialen Informationen. Eine davon ist die Definition einer Repräsentationsform für Inhalte, die nicht nur für Menschen sondern auch für Maschinen verständlich ist. Erst mit dieser kann das WWW sein gesamtes Poten-tial als ein Medium entfalten, das es seien Benutzern, zu denen auch automatisierte Prozesse gehö-ren, ermöglicht mit Informationen in einer wohldefinierten Art und Weise umzugehen. Diese Vision, die weit über die bloße Darstellung von Inhalten reicht, wurde von dem W3C Kon-sortium unter dem Begriff des Semantic Web definiert und basiert zum großen Teil auf dem Re-source Description Framework (RDF), das die Automatisierung, Integration und somit die Wie-derverwendung von Informationen über eine Vielzahl von Anwendungen ermöglicht, in dem es eine standardisierte Form für Metadaten ermöglicht. Unter Metadaten wird hier nichts anderes als eine Beschreibung und Charakterisierung der tatsäch-lichen Inhalte verstanden, d.h. Daten über Daten, die das Ziel verfolgen, die Semantik von Aussa-gen für Maschinen verständlich zu machen. Dabei ermöglichen sie bei Uneindeutigkeiten der Spra-che die beabsichtigte Bedeutung von Aussagen zu identifizieren Zu diesen Problemfällen gehören zum Beispiel Homonyme, d.h. mehrfache Bedeutungen eines Wortes (z.B. Maus), Synonyme, d.h. mehrere Wörter mit äquivalenten Bedeutungen (z.B. Compu-ter und Rechner) oder Mehrdeutigkeiten, die erst aus dem Kontext aufgeklärt werden können. Al-len drei Fällen ist gemein, dass es bei Suchanfragen, die sich lediglich auf die orthographische Übereinstimmung von Ausdrücken beschränken, zu einer Einschränkung der Ergebnismenge kommt. Durch den Einsatz von Metadaten kann dieses Problem größtenteils vermieden und somit die Qualität der Suchergebnisse deutlich verbessert werden. Die Verwendung von Metadaten ist aber nicht nur auf die Recherche von Informationen be-schränkt. Es ist auch möglich weiterreichende Informationen wie beispielsweise Urheberrechte, Vertragsbedingungen oder die Informationsformate selbst so darzustellen, dass sie für Maschinen verständlich werden um, so Tätigkeiten, die derzeit noch manuell vorgenommen werden müssen, automatisiert zu können. Nachdem die Möglichkeiten des RDF kurz umrissen wurden, folgt im nächsten Abschnitt eine grundlegende Einführung in letzteres. Bartholomäus Ende Matr.-Nr. 2063702 3. Resource Description Framework 3. Resource Description Framework
RDF basiert auf einfachen Aussagen der Form „Subjekt, Prädikat, Objekt", die jeweils einer Res-source eine Eigenschaft (Property) zuordnen, wobei das Prädikat die Art dieser Eigenschaft und das Objekt die Ausprägung definiert. Als Ressourcen werden alle Objekte angesehen, denen man für eine eindeutige Identifizierung einen URI (Uniform Resource Identifier) zuweisen kann. Da die Vergaben von eindeutigen URIs nicht nur auf digitale Daten, die über das WWW abrufbar sind, beschränkt ist, können somit auch Gegenstände wie ein Haus oder ein Baum beschrieben werden. Des Weiteren existieren zusätzlich noch anonyme Ressourcen, so genannte blank Nodes, denen keine explizite URI zugewiesen wird, die jedoch innerhalb einer RDF Beschreibung bzw. Applika-tion eine eindeutige URI durch den RDF Prozessor zugewiesen bekommnen, damit ihre Verwen-dung nicht nur auf ein einziges Statement beschränkt bleibt. Die dritte und letzte Art von Elemen-ten innerhalb des RDFs bilden die Literale, die Zeichenketten entsprechen, welche zusätzlich für die Kennzeichnung des kodierten Datentyps eine Typisierung aufweisen können. Bei der Verwendung dieser Elemente in RDF Statements gilt die Regel, dass Subjekte einer Res-source bzw. einem blank Node, Prädikate stets einem URI und Objekte einer beliebigen der drei möglichen Elementarten entsprechen. Aus dieser Definition folgt, dass Prädikate selbst Ressourcen sind und somit ihre Bedeutung mittels entsprechender Vokabulare klar definiert werden kann. Hierfür wurde das RDF Schema (RDFS) eingeführt. Es ist selbst ein Vokabular, das die Möglich-keit bietet eigene Vokabulare, bestehend aus speziellen Klassen von Ressourcen sowie Properties, zu definieren und damit Anwendungen, die für dieses so geschaffene Vokabular zugeschnitten sind, ein tieferes Verständnis der Aussagen zu verschaffen. Für eine einfache Definition sowie Wiederverwendung der eindeutigen Identifier einer jeden Res-source bedient sich das RDF dem Konzept der Namensräume (Namespaces). Dies sind Dateien, die eine Menge von Ressourcen mittels eines Schemas beschreiben. Die Verwendung der Ressourcen wird dadurch realisiert, dass der zu verwendende URI der Konkatenation des Unique Resource Locater (URL) des Namespaces, einer Raute als Trennzeichen und der innerhalb des Namespaces verwendeten ID als Suffix entspricht. Zudem werden für eine kürzere Schreibweise qualified Names (QName) verwendet, die einer Substitution der URL des Namespaces samt Trennraute ent-sprechen. Die folgende Tabelle listet alle in diesem Dokument verwendeten QNames auf: Präfix Namespace rdf http://www.w3.org/1999/02/22-rdf-syntax-ns# rdfs http://www.w3.org/2000/01/rdf-schema# dc http://purl.org/dc/elements/1.1/ imaginärer Namespace für Beispiele Tab. 1: Definition der verwendeten Präfixe
Den Abschluss dieser Einführung in RDF bilden die drei verschieden Repräsentationsmodi von RDF Statements, die jeweils anhand eines Beispiels verdeutlicht werden. 3.1. Tripelschreibweise
Diese Schreibweise repräsentiert jedes RDF Statement als ein geordnetes Tripel der Form: (Subjekt, Prädikat, Objekt)
Bartholomäus Ende Matr.-Nr. 2063702 3. Resource Description Framework Zusätzlich gelten die folgenden Vereinbarungen für die Kennzeichnungen der einzelnen Elementar-ten. Doppelte Hochkommas signalisieren, dass der Text zwischen ihnen einem Literal entspricht, während die Schreibweise ‹I› andeutet, dass der Eintrag der Ressource entspricht, die mit dem aus-geschriebnen URI I identifiziert wird. Außerdem ist im Folgenden der Präfix _: blank Nodes vor-angestellt. Bei dieser Repräsentationsform sollte man sich stets vor Augen halten, dass eine RDF Datenbank einer Menge von Tripel entspricht und es somit keine doppelten Einträge gibt. Beispiel 1:
Die Aussage, dass die mit der URI http://www.example.org identifizierte Ressource eine Homepa-
ge ist und von einem Objekt mit dem Namen "JohnSmith" kreiert wurde, entspricht den folgenden
drei RDF Statements:
( ‹http://www.example.org›, dc:creator, _:JohnSmith) ( _:JohnSmith, i:name, "JohnSmith") 3.2. Graphdarstellung
Die Darstellung mittels RDF Graphen ermöglicht es auf intuitive Weise den Zusammenhang zwi-schen einer überschaubaren Menge von RDF Sta-tements zu erlangen. Ein RDF Tripel entspricht dabei genau einer gerichteten Kante, die mit dem Prädikat beschriftet ist. http://www.example.org Ressourcen werden bei dieser Darstellungsform mittels Ovalen repräsentiert, wobei diese für expli- zite Objekte mit deren URI beschriftet werden, während blank Nodes leeren Ovalen entsprechen. Literale hingegen werden durch Rechtecke darge-stellt. Abb. 1: RDF Graph für Beispiel 1
3.3. XML/RDF
Diese Art der Kodierung dient dem Ziel der Seria-lisierung und des Austauschs von RDF Statements, wobei durch die Verwendung von XML eine Schnittstelle geschaffen wurde, die die Kompatibilität unabhängig entwickelter Applikationen ma-ximieren soll. Eine genaue Einführung in XML/RDF kann [1] entnommen werden. Beispiel 2:
Die serialisierte Form der im Beispiel 1 beschriebenen Tripel könnte wie folgt aussehen:
<?xml version="1.0" ?> <!DOCTYPE rdf:RDF [<!ENTITY rdfs "http://www.w3.org/2001/SMLSchema#">]> <rdf:RDF </rdf:RDF> Bartholomäus Ende Matr.-Nr. 2063702 4. Grundlegende Definitionen 4. Grundlegende Definitionen
Nach der vorangegangenen Einführung in RDF folgt in diesem Abschnitt eine formale Charakteri-sierung von RDF Graphen. Zudem werden die für die Analyse von Anfragen auf RDF Datenban-ken entscheidenden Begriffe der Vererbung und Kompaktheit von RDF Graphen definiert. 4.1. RDF Graphen
Ein RDF Graph ist ein gerichteter Graph, dessen Kanten und Knoten benahmt sind. Es sind Multi-kanten erlaubt, wobei diese der Einschränkung unterliegen, dass alle Kanten zwischen zwei Knoten eindeutige Namen tragen müssen. Des Weiteren kann der Graph zyklisch sein und aus mehreren Zusammenhangskomponenten bestehen. Für die weiteren Definitionen sowie die Analyse von RDF Graphen werden drei disjunkte Mengen benötigt. Zunächst repräsentiert U die Menge aller RDF URI Referenzen, B die Menge aller ano-nymen Ressourcen und L die Menge aller RDF Literale. Zusätzlich entspricht R (Menge aller Res-sourcen) der Vereinigungsmenge von U und B. Für eine einfachere Schreibweise wird noch mit UBL die Vereinigung der drei Grundmengen U, B und L abgekürzt. Die Knotenmenge V des Graphen entspricht der Vereinigungsmenge der Ressourcen und der Lite-rale. Für jeden Knoten, der keiner anonymen Ressource entspricht, ist die Funktion ID definiert als: Für die Unterscheidung von anonymen Ressourcen wird noch eine zusätzliche nur intern verwendete KnotenID definiert, die jedem Knoten einen innerhalb des RDF Graphen eindeutigen Identifier zuordnet. Die Kanten symbolisieren die Properties der beschriebenen Ressourcen und entsprechen somit den Prädikaten der RDF Statements. Sie sind dabei vom Subjekt zum Objekt gerichtet. Bemerkung 1:
Eine unmittelbare Konsequenz der obigen Festlegung ist, dass anonyme Ressourcen nur mittels
Properties abgefragt werden können, die auf sie verweisen.
Definition 1:
1. Ein Tripel T = (s, p, o) nennt man RDF Tripel, wenn T ∈ R × U × UBL gilt.
2. Ein RDF Graph G wird durch die Menge seiner Kanten definiert, die mittels RDF Tripeln rep-
räsentiert werden. Des Weiteren bildet jede Teilmenge dieser Tripel einen Teilgraphen von G. 3. Ein Graph, der frei von anonymen Ressourcen ist, wird einfach (ground) genannt.
Definition 2:
1. Zwei Knoten, die keinen anonymen Ressourcen entsprechen, sind äquivalent wenn ihre URI
gleich ist. Zwei anonyme Ressourcen werden als identisch angesehen, wenn ihre Properties gleich sind und zudem auch äquivalente Ausprägungen aufweisen. 2. Zwei RDF Graphen sind isomorph, wenn sie sich lediglich in den KnotenIDs der anonymen
Ressourcen unterscheiden. 3. Unter dem Mergen zweier RDF Graphen G1 und G2 versteht man den RDF Graphen, der der
Vereinigung der beiden Tripelmengen entspricht, wobei zuvor mittels einer adäquaten Umbe-nennung der KnotenIDs von anonymen Ressourcen Namenskonflikte vermieden werden. Die unter Drittens erwähnte Umbenennung wird dadurch realisiert, dass G1 mit einem Graphen G 2 vereinigt wird, der zu G2 isomorph ist und keine gemeinsamen KnotenIDs für anonyme Ressourcen mit G1 teilt. Zudem folgt unmittelbar, dass das Ergebnis des Mergens eindeutig ist. Bartholomäus Ende Matr.-Nr. 2063702 4.2 Pseudographen 4.2. Pseudographen
Für den Vergleich von RDF Graph mit anderen Graphen wird der Begriff des Pseudographen ein-geführt, der eine präzisere Charakterisierung ermöglicht. Definition 3:
1. Ein Pseudograph ist ein Viertupel (V, E, lV, lE) mit den beiden endlichen Mengen V (Knoten)
und E (Kanten) sowie den beiden Bezeichnungsfunktionen lV, lE. 2. Zwei Pseudographen Gi = (Vi, Ei, lv , l ) sind isomorph wenn ein Graphisomorphismus
Φ : G1 → G2 existiert, für den zusätzlich Φ o lV = l V2 o Φ sowie Φ o lE1 Mit der oberen Definition entsprechen Pseudograph gerichteten Graphen die Eigenschleifen (Zyk-len) und Mehrfachkanten erlauben. Aus diesem Grund lässt sich ein RDF Graph als ein spezieller Pseudograph definieren, bei dem V := UBL sowie E := U gesetzt werden. Zudem gelten die beiden Einschränkungen, dass Knoten, in denen Kanten beginnen keinen Literalen entsprechen dürfen und dass das Bild(l) in U enthalten sein muss. Korrolar 1:
Zwei RDF Graphen G1, G2 sind isomorph wenn ein Isomorphismus für Pseudographen Φ: G1 → G2
existiert, der folgende Eigenschaft erfüllt, ∀u ∈U : Φ(u) = u, d.h. für URI Referenzen entspricht
der Isomorphismus der Identitätsabbildung.
Bemerkung 2:
Aus der vorherigen Charakterisierung von RDF Graphen wird unmittelbar ersichtlich, dass man mit
ihnen Standardgraphen wie folgt kodieren kann. Für den Graphen G = (V, E) benötigt man hierzu:
(URI, die G eindeutig zugewiesen wird) 2. A ⊂ B : A = V
(anonyme Ressourcen zur Knotenkodierung) 3. c : V → A : c bijektiv (Bijektion zwischen V und A)
Dann wird der ursprüngliche Graph durch die folgende Menge von RDF Tripeln kodiert: GRDF = {(c(i), u, c(j)) (i, j) ∈ E} 4.3. Interpretation von RDF Graphen
Der folgende Abschnitt orientiert sich an den Definitionen des RDF Semantik Dokuments [2] und dient der Einführung von einfachen Interpretationen, d.h. von Interpretationen eines RDF Graphen, die nicht auf den Bedeutungen basieren, die einem speziellen Vokabular angeheftet sind. Eine In-terpretation ist hierbei definiert als eine Menge von Annahmen, die die Aussagen des RDF Gra-phen nicht falsifizieren. Das Ziel der folgenden Betrachtung ist die Motivation des Begriffs der Vererbung (Entailment), der durch das Interpolations Lemma charakterisiert wird. Ihm wird besondere Bedeutung beigemessen, da er die Beziehung des Enthaltenseins von Aussagen, die RDF Graphen innewohnen, beschreibt und somit ein Bindeglied zwischen der modell-theoretischen Semantik von RDF und realen Appli-kationen bildet. Zusammenfassend heißt dies, dass die Aussage G vererbt an G' äquivalent damit ist, dass jede In-terpretation, die G wahr macht ebenso auch G' wahr macht und somit jede Behauptung über G eine gewisse Aussage über G' impliziert. Für den Anfang wird zunächst die Definition einer einfachen Interpretation betrachtet: Bartholomäus Ende Matr.-Nr. 2063702 4.3 Interpretation von RDF Graphen Definition 4:
Eine einfache Interpretation I eines Vokabulars V besteht aus:
1. Einer nicht leeren Menge IR von Ressourcen, die der Domäne oder dem Universum von I ent-
2. Einer Menge IP, die alle Properties von I enthält.
3. Einer Abbildung IEXT : IP → { x x ⊂ IR × IR }
IEXT(x) wird als extension von x bezeichnet und umfasst die Menge aller Paare, für die die bi-näre Eigenschaft x wahr ist. 4. Einer Abbildung IS : U → V (V ≡ IR ∪ IP)
5. Einer Abbildung IL von den typisierten Literalen in V nach IR.
6. Einer ausgewählten Teilmenge LV von IR, die zumindest alle Strings sowie allen Paaren beste-
hend aus Strings und Sprach-Tags enthält. Bevor nun die rekursiv definierte Bedeutung eines RDF Graphen eingeführt werden kann, bedarf es des Begriffs des Mappings. Definition 5: Mapping
1. Eine Abbildung µ : UBL → UBL, die für alle Literale und URI Referenzen der Identitätsfunkti-
on entspricht, d.h. diese Parametertypen bewahrt, wird ein Mapping genannt. 2. Für einen gegebenen Graphen G wird µ(G) definiert als:
µ(G) = { (µ(s), µ(p), µ(o)) (s, p, o) ∈ G} 3. Ein Mapping µ ist konsistent wenn µ(G) wieder einem RDF Graphen entspricht, d.h. für alle
Elemente (µ(s), µ(p), µ(o)) ∈ R × U × UBL gilt. Ist dies der Fall, dann heißt µ(G) eine Instanz des ursprünglichen Graphen G. 4. Von einer echten Instanz ist die Rede, wenn die Anzahl der anonymen Ressourcen in µ(G) ge-
ringer ist als die in G. Dies kann durch die Instanziierung oder das Zusammenlegen zwei ano-nymer Ressourcen geschehen. Definition 6: Graphinterpretation
Die Interpretation eines Graphen ist wie folgt rekursiv definiert:
- X ist ein einfaches Literal "Text" → I(X) ≡ Text - X ist ein einfaches Literal "Text"@xy → I(X) ≡ ‹ Text, xy › - X ist ein typisiertes Literal aus V → I(X) ≡ IL(X) - X ist eine URI Referenz aus V → I(X) ≡ IS(X) - X ist ein einfaches Tripel ‹ s, p, o › → aus s, p, o ∈V, I(p)∈IP und (I(s), I(o)) ∈ IEXT(I(p)) folgt I(X) ≡ true, ansonsten gilt I(X) ≡ false - X ist ein einfacher RDF Graph → wenn I(X) ≡ false für ein Tripel T∈X, ansonsten gilt Bei der Verwendung von anonymen Ressourcen benötigt man noch zusätzlich: - X ist eine anonyme Ressource → [I+µ](X) ≡ I(µ(X)) - X ist ein RDF Graph → wenn [I+µ](X) ≡ true für ein Mapping µ mit dem Bild(µ) IR, dann folgt I(X) ≡ true ansonsten gilt I(X) ≡ false Bartholomäus Ende Matr.-Nr. 2063702 4.3 Interpretation von RDF Graphen Definition 7: Subinterpretation
Eine Interpretation I ist eine Subinterpretation, dargestellt durch I << J, einer zweiten Interpretation
J wenn eine Abbildung k : (IRI ∪ IPI) → (IRJ ∪ IPJ) mit folgenden Eigenschaften existiert:
1. x∈IRI
2. x∈IPI
3. x ist ein String oder ein Paar von Strings → k(x) = x
4. x∈(U ∪ L)
→ J(x) = k(I(x)) 5. (x, y)∈IEXTI(p)
→ (k(x), k(y))∈IEXTJ(k(p)) Lemma 1: Subinterpretations Lemma
Aus I << J und I(G) ≡ true folgt J(G) ≡ true.
Beweis:
Nach Voraussetzung existiert ein Mapping µ, so dass [I +µ]((s, p, o)) ≡ true für alle (s, p, o)∈G gilt.
→ ([I +µ](s), [I +µ](o))∈IEXTI(I(p)) → für die Abbildung k der Subinterpretation gilt dann (k([I +µ](s)), k([I +µ](o)))∈IEXTJ(k(I(p))) → Sei Φ(x) := k(µ(x)) und [J+Φ](x) ≡ k([I +µ(x)]) dann gilt ([J+Φ](s), [J+Φ](o))∈IEXTJ(J(p)) → J(G) ≡ true Definition 8: Herbrand Interpretation
Die Herbrand Interpretation eines Graphen G, abgekürzt durch HerbG ist wie folgt definiert:
- LV ist die Menge aller in G vorkommenden Literale - IR beinhaltet LV sowie alle Namen und alle anonymen Ressourcen, die als Objekte oder Subjek- te in Tripeln aus G auftreten - IP beinhaltet alle URI Referenzen, die als Properties in G verwendet werden - IS ist die Identitätsabbildung für das Vokabular von G - IL ist die Identitätsabbildung für alle typisierten Literale - IEXT wird definiert als (s, o) ∈ IEXT(p) ↔ (s, p, o) ∈ G Aus dieser Definition folgt unmittelbar, dass HerbG + µ, mit der Identitätsabbildung auf den ano- nymen Ressourcen als µ, alle Tripel in G erfüllt und deshalb HerbG(G)≡ Definition 9: einfache Vererbung
Ein RDF Graph G1 vererbt an einen weiteren RDF Graphen G2, dargestellt durch G1 = G2, wenn
jede Interpretation I des Vokabulars von (G1 ∪ G2) mit I(G1) ≡ true auch I(G2) ≡ true impliziert.
Nach diesen grundlegenden Definitionen kann jetzt das für die Vererbung bedeutende Interpola-tions Lemma eingeführt werden, dass Vererbung auf einfache Beziehungen unter Graphen zurück-führt. Zuvor werden jedoch noch drei Lemmata von Herbrand betrachtet, deren unmittelbare Kon-sequenz das Interpolation Lemma ist. Lemma 2: Herbrand Lemma
I(G) ≡ true ↔ HerbG << I Bartholomäus Ende Matr.-Nr. 2063702 4.3 Interpretation von RDF Graphen → man wähle einen Teil von HerbG als Abbildung VHerb → V → I(HerbG(a)) = I(a) ∧ ∀ (s, p, o) ∈ G gilt (s, o)∈IEXTHerb (Herb → da (I(s), I(o)) ≡ (I(HerbG(s)), I(HerbG(o))) gilt (I(HerbG(s)), I(HerbG(o)))∈IEXTI(I(p)) → (I(HerbG(s)), I(HerbG(o)))∈IEXTI(HerbG)(I(HerbG(p))), was der Forderung an die subin- terpretations Abbildung HerbG → → HerbG << I ←: HerbG << I → per Definition gilt HerbG ≡ true → mit dem Subinterpretations Lemma gilt I(G) ≡ true Lemma 3: Herbrand Entailment Lemma
G = G' ↔ HerbG(G') ≡ true = G' ∧ HerbG(G) ≡ true → ∃µ : µ(G') ⊆ G → [HerbG + µ](G') ≡ true → HerbG(G') ≡ true ←: HerbG(G') ≡ true → ∀ I : I(G) ≡ true gilt HerbG << I → I(G') ≡ true Definition 10:
Seien G und G' RDF Graphen, dann ist G' mit G verbunden, wenn eine Instanz von G' ein Teil-
graph von G ist. Insbesondere ist ein einfaches Tripel T mit G verbunden wenn T∈G gilt.
Lemma 4: Herbrand Separations Lemma
HerbG(G') ≡ true ↔ G' ist mit G verbunden
Beweis:
HerbG(G') ≡ true
↔ ∃µ : [HerbG + µ](G') ≡ true
↔ ∃µ : µ(G') ⊆ G
↔ G' ist mit G verbunden
Die Kombination der Implikationen aus dem Entailment- und dem Separation Lemmas von Herb-rand führt unmittelbar auf das Interpolation Lemma, das für die weitern Betrachtungen von großer Bedeutung ist: Bartholomäus Ende Matr.-Nr. 2063702 4.3 Interpretation von RDF Graphen Lemma 5: Interpolation Lemma
Seien G1 und G2 zwei RDF Graphen. Dann gilt G1 = G2, genau dann wenn eine Instanz von G2 ein
Teilgraph von G1 ist.
Beispiel 3:
1. Ein Graph G vererbt trivialer Weise an alle seine Teilgraphen.
2. Für die folgenden drei Graphen gilt G1 = G3 aber G1 = G2
G1 = { (a, b, c), (_:X, b, c), (a, b, _:Y) } G2 = { (_:U, _:V, c), (_:V, b, c) } G3 = { (a, _:V, c), (_:X, b, _:Y) } Korrolar 2:
1 und G2 sind äquivalent, dargestellt durch G1 4.4. Minimale Repräsentation
Durch die Verwendung von anonymen Ressourcen können Redundanzen innerhalb eines RDF Graphen auftreten, deren Vermeidung wünschenswert ist. Die Frage nach einer minimalen Reprä-sentation von Daten ist unmittelbar an den Begriff des kompakten Graphen gebunden. Dieser Abschnitt beschäftigt sich mit Graphen, die kompakt sind, wobei schon die Definition dieser Graphenart unterstreicht, dass es sich um Graphen handelt, die frei von Redundanzen sind. Definition 11: Kompaktheit von Graphen
Ein Graph G wird kompakt genannt, wenn kein Mapping µ existiert, so dass µ(G) ein echter Teil-
graph von G ist, d.h. jede echte Instanz von G ist kein Teilgraph von G.
Beispiel 4:
Seien die beiden RDF Graphen G1 und G2 wie folgt definiert
G2 = { (a, b, c), (_:X, b, c), (_:X, c, d) } dann ist G2 kompakt während G1 diese Eigenschaft nicht besitzt, d.h. die Eigenschaft der Kom- paktheit eines Graphen ist unter Teilmengenbildung nicht abgeschlossen. Das folgende Lemma zeigt, dass mit der Hilfe des im vorherigen Abschnitt eingeführten Interpola-tions Lemmas unmittelbare Konsequenzen für die Vererbung zwischen zwei RDF Graphen getrof-fen werden können, wenn letztere in bestimmten Verhältnissen zueinander stehen. Lemma 6: Anonymity Lemma
1. Ein kompakter Graph vererbt nicht an seine echten Instanzen.
2. Wenn G' aus einem kompakten Graphen G durch Zusammenlegung zweier anonymer Ressour-
cen hervorgeht, dann vererbt G nicht an G'. Bartholomäus Ende Matr.-Nr. 2063702 4.4 Minimale Repräsentation Beweis:
1. Sei G ein kompakter Graph und G' eine echte Instanz von G. Des Weitern gilt G = G', d.h. G
→ ∃ein konsistentes Mapping µ, so dass die Instanz µ(G') ein Teilgraph von G ist → ∃ein weiteres konsistentes Mapping ψ : ψ(G) ist Teilgraph von G, da die Eigenschaft In- stanz von transitiv ist → G kann nicht kompakt sein → ein kompakter Graph kann nicht an seine echten Instanzen vererben 2. Sei G ein kompakter Graph und gehe G' durch Zusammenlegung zweier anonymer Ressourcen → G' kann kein Teilgraph von G sein → keine Instanz von G' ist ein Teilgraph von G, da die Eigenschaft Instanz von transitiv ist → G = G' Ansonsten sind die Eigenschaften von kompakten Graphen zu großen Teilen noch unerforscht und bedürfen deshalb einer eingehenden Betrachtung. Zwei grundlegende Aspekte, die im Folgenden beantwortet werden, sind die Frage nach einer eindeutigen Zuordnung von kompakten Graphen sowie der Komplexität, die der Bestimmung eines solchen Graphen innewohnt. Die beiden folgenden Sätze widmen sich diesen Fragestellungen. Satz 1:
Für jeden RDF Graph G existiert ein eindeutig bestimmter kompakter Graph, zu dem G äquivalent
ist.
Beweis:
Zunächst definieren wir innerhalb der Menge der RDF Graphen die zweistellige Relation →. Es
gilt G1 → G2, wenn G1 ein echter Teilgraph von G2 ist und ein konsistentes Mapping µ existiert, so
dass G2 ≡ µ(G1) gilt. Für den Beweis werden von der Relation zwei Eigenschaften gefordert. Erstens darf sie für den Nachweis der Existenz von kompakten Graphen keine endlosen Ketten von Hintereinanderausfüh-rungen besitzen. Und Zweitens müssen die Endgraphen, die beim Auftreten von Wahlmöglichkei-ten resultieren, äquivalent zueinander sein, so dass die Eindeutigkeit des kompakten Graphen ge-währleistet ist. Die erste Forderung folgt unmittelbar aus der Definition der Relation, da nur endliche Graphen verwendet werden. Für die Zweite muss man den Fall G1 ← G → G2 betrachten, für den der transi- tive Abschluss →* mit der Eigenschaft G1 →* G* und G2 →* G* benötigt wird. Diese Eigenschaft wird jedoch von der Relation gewährleistet, wie die folgende Überlegung zeigt. Angenommen es gebe kein eindeutiges G* sondern zwei kompakte Graphen G * ∃ (s', p, o') ∈ G2 in das (s, p, o) in ein oder mehreren Schritten gemappt wurde, da in beiden Hintereinanderausführungen vom gleichen Graphen G ausgegangen wurde µ(G1) so dass µ(G1) ein echter Teilgraph von G1 ist → G *1 kann nicht kompakt sein! Aus dem obigen Argument folgt, dass die Relation → konvergiert und deshalb für jeden Graphen G ein eindeutiges G* existiert, so dass G →* G* gilt und G* im Sinne der Relation irreduzibel ist. D.h. G* ist der gewünschte kompakte Graph. Nachdem die eindeutige Zuordnung von kompakten Graphen sichergestellt ist, stellt sich nun die Frage nach einer effizienten Berechnung, die in dem folgenden Satz beantwortet wird. Bartholomäus Ende Matr.-Nr. 2063702 4.4 Minimale Repräsentation Satz 2:
Die Beantwortung der Frage, ob ein RDF Graph kompakt ist, ist NP-vollständig.
Beweis:
Für die Motivation des Beweises wird an die Bemerkung 2 (aus 4.2) erinnert, in der gezeigt wird,
dass jeder Graph in Form eines RDF Graphen, dessen Knoten nur aus anonymen Ressourcen be-
steht, dargestellt werden kann. Da die dort gegebene Konstruktionsvorschrift bijektiv ist, lässt sie
sich eindeutig umkehren und man erhält bereits für diese spezielle Teilmenge von RDF Graphen
die NP-Vollständigkeit der Frage, ob ein solcher RDF Graph kompakt ist.
Der Grund hierfür ist, dass die obige Frage äquivalent zu dem Problem COREG ist, in dem für ei- nen gegebenen Graphen G nach der Existenz eines nicht surjektiven Endomorphismus G → G gefragt wird. Zusätzlich wurde von Hell und Nestril in [6] nachgewiesen, dass das Problem COREG NP-vollständig ist. Eine unmittelbare Aussage des letzten Satzes ist, dass die minimale Repräsentation eines RDF Graphen schwer zu berechnen ist. 5. Anfragen auf RDF Datenbanken
Durch die Definition eines RDF Graphen als eine Menge von RDF Tripeln kann dieser als eine relationale Datenbank interpretiert werden, die eine Relation mit den drei Attributen Subjekt, Prä-dikat und Objekt enthält. Dabei entsprechen die Tripel des RDF Graphen den Tupeln dieser Relati-on. Der einzige Unterschied zu einer relationalen Datenbank, ergibt sich durch die Anwesenheit von anonymen Einträgen, die im Gegensatz zu nur einem NULL Wert eindeutig unterschieden werden können und zudem auch noch Properties besitzen. Somit wird im Folgenden eine RDF Datenbank als ein RDF Graph angesehen. 5.1. Abfragesprache
Für die Formulierung von Abfragen wird eine Menge von Variabeln V, die disjunkt mit UBL ist, eingeführt. Im Folgenden werden Variablen durch Bezeichner dargestellt, die den Präfix „?" auf-weisen. Die hier verwendete Abfragesprache bedient sich des in der Datenbankliteratur weit ver-breiteten Begriffs des Tableaus [7], der wie folgt modifiziert wird: Definition 12: Abfrage
Eine Abfrage wird definiert als ein Tripel (H, B, C), das aus einem Header H, einem Body B und
einer Menge von Einschränkungen C (Constraints) besteht. Für die Elemente bestehen folgende
Beziehungen:
1. H ist ein RDF Graph über V ∪ UBL, mit der Eigenschaft var(H) ⊆ var(B)
2. B ist ein RDF Graph über V ∪ UL
3. C ⊆ var(H)
Der Body dient dabei der Einschränkung der Ergebnismenge, indem er nur Variabeln zulässt, die bestimmte Properties aufweisen. Diese werden dann auf die im Header definierte Formatierung gemappt, weshalb oft die Schreibweise H ← B Verwendung findet. Durch die Menge C wird die Ergebnismenge dahingehend eingeschränkt, dass alle Variablen, die in C auftreten nicht mit ano-nymen Ressourcen belegt sein dürfen. Bartholomäus Ende Matr.-Nr. 2063702 5.1 Abfragesprache Beispiel 5:
Die folgende Abfrage, die keine Einschränkungen besitzt, würde einfach alle Personen die eine
Rechnung bezahlen müssen, als solche definieren, die ein Telefon besitzen, dem diese Rechnung
zugeschrieben wird.
(?Person, pays, ?Bill) ← (?Person, owns, ?Phone), (?Phone, causes, ?Bill) Sinnvoll wäre es noch mittels C := { ?Person }, die Ergebnismenge auf alle Personen einzuschrän-ken, die mittels einer nicht anonymen Ressource identifiziert werden können. Bemerkung 4:
Durch die Bedingung var(H) ⊆ var(B) wird verhindert, dass ungebundene Variablen im Header der
Abfrage auftauchen können. Des Weiteren sind anonyme Ressourcen im Body einer Anfrage
redundant, da sich zeigen wird, dass sie in diesem Abfrageteil äquivalent zu Variablen sind. Hinge-gen ist ihre Anwesenheit im Header wünschenswert, da somit Reification (auf die in 5.3 näher ein-gegangen wird) mittels Abfragen ermöglicht wird. Technisch gesehen entsprechen sie dort freien Termen der Form f(X1, … , Xn), wobei die X1, …, Xn einer Teilmenge der in der Abfrage auftreten- den Variablen bzw. Konstanten entsprechen. 5.2. Antworten auf Anfragen
Die Antwort auf eine Anfrage entspricht einer Belegung der Variablen, so dass alle Bedingungen
erfüllt sind. Für eine formale Definition wird der Begriff der Bewertung benötigt. Darunter versteht
man eine Abbildung v : V → UBL. Falls die Anfrage Einschränkungen besitzt, d.h. die Menge C
nicht leer ist, dann werden diese von der Bewertung v erfüllt (dargestellt durch v = C), wenn für
alle x∈C, v(x) keiner anonymen Ressource entspricht.
Unter einem Matching eines Graphen G in einer Datenbank D versteht man eine Bewertung v, so
dass eine Instanz von v(B) ein Teilgraph von D ist, insbesondere heißt das, dass D = v(B) gilt. Von
besonderem Interesse sind natürlich die Matchings, die die Einschränkungen erfüllen.
Definition 13:
Für eine Anfrage q = (H, B, C) auf eine Datenbank D definiert man ihre Vorantwort (pre-answer)
wie folgt als eine Menge von RDF Graphen:
Dabei bezeichnet man jeden Graph v(H) als eine einfache Antwort (single answer) der Anfrage q auf die Datenbank D. Für die Kombination aller einfachen Antworten zu der endgültigen Antwort auf eine Abfrage exis-tieren die folgenden zwei Möglichkeiten, die zu unterschiedlichen Semantiken führen: 1. Die Antwort, die mit ans (q,
D) bezeichnet wird, entspricht der mengentheoretischen Vereini- gung (Union-Semantik) aller einfachen Antworten. Dieser Ansatz zeichnet sich dadurch aus, dass anonyme Ressourcen zu Bindegliedern zwischen den einzelnen einfachen Antworten wer-den können und somit die Möglichkeit für die Modellierung von neuen Zusammenhängen in der Antwort besteht. 2. Der alternative Ansatz, dessen Ergebnis mit ansm(q, D) bezeichnet wird entspricht dem Mergen
der einzelnen einfachen Antworten (Merge-Semantik). Dies hat zur Folge, dass der RDF Graph, der die endgültige Antwort symbolisiert, einem Wald von einfachen Antworten entspricht. Für den Fall, dass die Datenbank D ein einfacher RDF Graph ist, d.h. keine anonymen Ressourcen besitzt sind beide Ansätze äquivalent, da diese Situation einer Anfrage auf eine klassische Daten-bank entspricht. Bartholomäus Ende Matr.-Nr. 2063702 5.2 Antworten auf Anfragen Beispiel 6:
Die beiden hier aufgelisteten Fälle skizzieren Szenarien, in denen die Union-, der Merge-Semantik
überlegen ist, weshalb in den folgenden Abschnitten stets von der Union-Semantik ausgegangen
wird, falls nichts anderes vermerkt wird.
1. Mit der Merge-Semantik ist eine datenunabhängige Identitätsabfrage nicht möglich, während
mit der Union-Semantik für die Abfrage q = ({ (?s, ?p, ?o) }, { (?s, ?p, ?o) }, Ø) und einer belie-bigen Datenbank D stets ans (q, 2. Wenn in einer Datenbank eine anonyme Ressource existiert, die das Objekt eines Statements
(s, p _:B) ist und diese anonyme Ressource selber mehrere Properties besitz, d.h. es existieren mehrere Einträge der Form (_:B, pi, oi) : i ∈[1.n], dann ist es nicht möglich alle Properties von _:B mit einer datenunabhängigen Abfrage zu ermitteln, wenn man von der Merge-Semantik ausgeht. Die folgende Abfrage q = ({ (?s, „feature", ?p) }, { (s, p, ?s), (?s, ?p, ?o) }, Ø) führt hin-gegen bei der Verwendung der Union-Semantik zum Erfolg. Behauptung 1:
Für beliebige Datenbanken D und D' sowie eine beliebige Anfrage q gilt für beide Semantiken:
D = D' → ans(q, D) = ans(q, D')
Beweis:
Nach Voraussetzung existiert ein Mapping µ, so dass µ(D') ein Teilgraph von D ist. Des Weiteren
sei H der Header und B der Body der Anfrage.
→ ∀ v(H)∈preans(q, D') ∃ v(B) : v(B) ⊆ D' → für dieses v(B) gilt wiederum µ(v(B)) ⊆ D → µ(v(H))∈preans(q, D) → ∀ G∈preans(q, D') ∃ G' ∈preans(q, D) : G ⊆ G' → ans(q, D) = ans(q, D') Behauptung 2:
Für alle Anfragen q und alle Datenbanken D gilt:
ans (q,
D) = ansm(q, D) Beweis:
Die Aussage folgt unmittelbar aus der Tatsache, dass die Vereinigung zweier Graphen G1, G2 an
das Ergebnis des Mergens der beiden vererbt. Für eine Überprüfung führe man einfach das Map-ping auf dem Ergebnis des Mergens aus, das die Umbenennung der anonymen Ressourcen währen-de des Mergens invertiert. Bemerkung 5:
Die Umkehrung der letzten Behauptung gilt im Allgemeinen nicht. Für ein Gegenbeispiel genügt
bereits eine Anfrage, die zwei einfache Antworten besitzt, die eine anonyme Ressource gemeinsam
haben, wie z. B. die Identitätsabfrage q auf die Datenbank D = { (_:X, b, c), (_:X, b, d) }. In diesem
Fall ist ans (q,
D) ≡ D, während ansm(q, D) ≡ { (_:X1, b, c), (_:X2, b, d) }, so dass natürlich kein Mapping von D auf ansm(q, D) existiert. Bartholomäus Ende Matr.-Nr. 2063702 5.2 Antworten auf Anfragen Bemerkung 6: Redundanz
Für eine effiziente Verarbeitung von Anfragen ist die Vermeidung von Redundanz von großer Be-
deutung. Deshalb werden im Folgenden einige Beobachtungen für die Vermeidung von Redundan-
zen aufgelistet.
1. Abfragen sollten kompakte Header besitzen, da ansonsten in der generierten Ergebnismenge
Redundanzen auftreten, die vermieden werden könnten. 2. Die Verwendung eines nicht kompakten Bodies lässt sich nicht immer vermeiden. Dies ist z.B.
immer dann der Fall wenn alle Ausprägungen einer bestimmten Property einer Ressource ver-langt werden, wobei nur solche Ressourcen aufgelistet werden sollen, die eine bestimmte Aus-prägung dieser Property aufweisen. 3. Selbst wenn die Datenbank sowie die Abfrage kompakt gehalten werden, können in der Ergeb-
nismenge Redundanzen, in Form von nicht kompakten RDF Graphen, auftreten, da die Eigen-schaft der Kompaktheit unter Teilmengenbildung nicht abgeschlossen ist (siehe hierzu Bsp. 2) 5.3. Reification
Nach den vorherigen Betrachtungen von RDF Graphen, deren Interpretationen sich lediglich auf
ihre Syntax beziehen, wird im Folgenden ein Vokabular, d.h. eine Menge von Ressourcen einge-
führt, denen eine wohldefinierte Bedeutung angeheftet ist. Dieses Vokabular beschränkt sich auf
die folgende, selbsterklärende Teilmenge des RDF Schemas (RDFS), das eine Erweiterung von
RDF ist:
rdf:statement rdf:subject rdf:object rdf:type Durch die Verwendung von RDFS stehen Mechanismen bereit, die es ermöglichen verwandte Res-sourcen sowie die Relationen zwischen ihnen zu beschreiben. Jedoch beschränken wir uns mit der obigen Teilmenge auf die Betrachtung von Reification. Hierunter versteht man Aussagen über RDF Aussagen, mit denen ein Model des RDF Graphen beschrieben wird, wie z.B. „Das Tripel (s, p, o) ist ein Statement". Diese Aussage lässt sich mit dem oben erwähnten Vokabular durch die folgen-den vier Tripel beschreiben, die jedes Element der oben getroffenen Aussage näher charakterisie-ren: { (_:Aussage, rdf:type, rdf:statement), (_:Aussage, rdf:subjekt, s), (_:Aussage, rdf:object, o), (_:Aussage, rdf:predicate, p) } Beispiel 7:
Mit der folgenden Abfrage kann die oben beschriebene Reification der Aussage (s, p, o) generiert
werden, wobei für die Erzeugung einer eindeutige anonyme Ressource noch eine Skolem Funktion
benötigt wird:
(f(a, b, c), rdf:type, rdf:statement), (f(a, b, c), rdf:subjekt, s), (f(a, b, c), rdf:object, s), (f(a, b, c), rdf:predicate, p) Wenn man die Reification, von allen Tripeln in einer Datenbank erzeugen möchte, dann müssen in der oberen Abfrage lediglich alle Vorkommen der Konstanten s, p, o durch die entsprechenden Variablen ?s, ?p, ?o ersetzt werden. Beispiel 8:
Die Ermittlung aller Properties, die einer ausgezeichneten Ressource r innerhalb einer Datenbank
angeheftet sind, lässt sich mit folgender Abfrage realisieren:
(?Property, rdf:type, rdf:predicate) (r, ?Property, ?Object) Bartholomäus Ende Matr.-Nr. 2063702 Damit lässt sich die Leibnitz'sche Identität mittels zweier Abfragen auf eine Datenbank testen, da diese besagt x ≡ y ↔ ∀ Properties P gilt P(x) ≡ P(y). Bemerkung 7:
Für die Behandlung von Aussagen bieten sich zwei Möglichkeiten an. Zunächst können Aussagen
selbst als Objekte angesehen werden. Dies führt jedoch zu der problematischen Situation, dass bei
der Einführung von Reification, jedes Statement selbst wieder ein neues Objekt darstellt, das be-
schrieben werden kann und somit eine unendliche Menge von Aussagen der Form
(_:Aussagei+1, rdf:subject, _:Aussagei) gültige Bestandteile einer Datenbank sind. Dies widerspricht jedoch der Definition von RDF Gra-phen, die als eine endliche Menge definiert sind. Die zweite Alternative, die dem Vorgehen im RDFS entspricht, betrachtet Aussagen nicht als eige-ne Objekte, sondern verwendet Namen als Referenzen, was dazu führt, dass die Existenz einer Aussage nicht die Existenz ihrer Reification impliziert sowie vice versa. Ein weiterer Vorteil dieses Vorgehens ist, dass durch die Einführung von Reification, die Größe des RDF Graphen lediglich um einen konstanten Faktor ansteigt. 6. Komplexitätsbetrachtungen
Dieser Abschnitt analysiert die Komplexität, die der Beantwortung von Anfragen auf eine RDF Datenbank zugrunde liegt. Er ist hierfür in drei Abschnitte unterteilt. Zunächst wird die bloße Be-antwortung von Anfragen betrachtet. Die zwei weiteren Abschnitte beschäftigen sich mit effizien-ten Antworten, die kompakten Graphen entsprechen. Dafür werden sowohl die Minimierung von Anfragen sowie die Minimierung von Antworten, d.h. die Eliminierung von Redundanzen aus der Antwort, betrachtet. 6.1. Berechnung von Antworten
Für ein Verständnis der Komplexität, die der Berechnung von Antworten zugrunde liegt, wird ein einfacheres Problem betrachtet, nämlich die Frage, ob die Antwort einer Abfrage leer ist. Zudem erfolgt die Bewertung einer Abfrage q auf eine Datenbank D von den folgenden zwei Standpunk-ten: 1. Abfrage Komplexität: Die Datenbank D ist fixiert, während die Abfrage q beliebig ist.
2. Daten Komplexität:
Die Abfrage q ist fixiert, während die Datenbank D variabel bleibt. Satz 3:
Das Bewertungsproblem ist NP-hart für die Version Abfrage Komplexität während es in der Versi-
on Daten Komplexität in polynomieller Zeit in der Größe der Datenbank lösbar ist.
Beweis:
1. Daten Komplexität:
Aus der Reduktion 3-SAT ≤ P Bewertungsproblem einer konjugierten Abfrage folgt unmittelbar die NP-Härte, da das Erfüllungsproblem bereits selbst NP-vollständig ist. Bei der Reduktion kann dabei wie folgt vorgegangen werden: In der Datenbank existieren zwei Arten von Ressourcen, Verweisressourcen und Belegungsres-sourcen. Bartholomäus Ende Matr.-Nr. 2063702 6.1 Berechnung von Antworten Bei letzteren entspricht jede Ressource einer eindeutigen Kombination aus einer Klausel der maxi-malen Länge drei sowie einer Belegung, die sie erfüllt. Zwischen dieser Ressourcenart existiert zusätzlich eine Hand von Properties (satisfyTyp) die anzeigen, wann zwei solche Klauseln simultan erfüllbar sind. Dabei unterscheiden sich die URI Referenzen der Properties in Abhängigkeit davon wie viele Literale identisch sind und an welchen Positionen der beiden Klauseln diese stehen. Durch diese Konstruktion wird erreicht, dass ein Tripel (s, p, o) mit den beiden Belegungsressour-cen s und o äquivalent dazu ist, dass die Klauseln mit der Belegung, die den Ressourcen s und o entsprechen gleichzeitig erfüllbar sind. Wichtig hierbei ist, dass die Anzahl der Belegungsressour-cen sowie der zwischen ihnen befindlichen Properties endlich ist. Dies folgt aus der Tatsache, das es lediglich polynomiell viele unterschiedliche Klauseln der maximalen Länge 3 gibt, jede dieser Klauseln maximal 23-1∈poly(x) viele erfüllende Belegung besitzt und es nur 7 mögliche Properties für jedes Paar von Belegungsressourcen gibt. Insgesamt ist die Menge der Belegungsressourcen sowie Properties durch ein Polynom begrenzt und damit endlich. Die Verweisressourcen dienen lediglich der Auflistung aller Möglichen Klauseln der maximalen Länge 3 von denen wir wissen, dass es maximal polynomiell viele gibt. Dieser Ressourcentyp be-sitzt nur eine einzige Art von Properties (set). Nämlich einen Verweis auf alle möglichen Belegun-gen in Form von Belegungsressourcen, die die Klausel erfüllen. Dies hat zur Folge, dass diese Art von Ressourcen und Ihre Properties ebenfalls einer endlichen Menge entsprechen. Nachdem die fixierte und somit konstante Datenbank beschrieben ist, kann das vorgehen der trans-formierenden TM beschrieben werden. Für jede Kombination zweier Klausel ki und kj der KNF mit i, j∈[1.n] werden die folgenden Bedingung dem Body der Abfrage hinzugefügt: { (ki, set, ?Xi), (kj, set, ?Xj), (?Xi, satisfyMatch(i, j), ?Xj), (?Xj, satisfyMatch(j, i), ?Xi) } Hierbei sind die kx die Verweisressourcen, die den Klauseln entsprechen, während, die Variablen ?Xk wegen der Datenbankdefinition nur von Belegungsressourcen instanziiert werden können. Die Funktion Match(k1, k2), dient zudem der Bestimmung der Übereinstimmung von Variabeln inner- halb der beiden Parameterklauseln und somit der Auswahl des richtigen Typs der Property satisfyTyp. Die Abfrage besitz keine Einschränkungen, d.h. C ≡ Ø und der Header ist ein beliebiger konstanter Ausdruck. Aus der Definition folgt unmittelbar, dass die gegebene KNF lösbar ist wenn die Ant-wort nicht leer ist. 2. Daten Komplexität:
Da die Abfrage fixiert ist, ist die Größe q , d.h. die Anzahl der Tripeln des zu matchenden Graphen ebenfalls fixiert. Hieraus folgt, dass es nur polynomiell viele Möglichkeiten für einen zu matchen-den Graphen gibt, genau genommen D q , wobei D der Größe der Datenbank D entspricht. Da der Test jedes potentiellen Graphen in Konstantzeit gelingt, ist die Bewertung in dieser Version in po-lynomieller Zeit berechenbar. Eine weitere Folge des obigen Beweises ist, dass die Größe des Antwortgraphen stets durch das Polynom D q nach oben begrenzt wird. Daran ändert auch die Verwendung von Reification nichts, da dies die Datenbank nur um einen konstanten Faktor vergrößert. 6.2. Minimierung von Abfragen
Der statischen Optimierung von Abfragen muss eine große Bedeutung beigemessen werden, da wie aus Satz 3 ersichtlich wird, die Auswertung einer Abfrage eine exponentielle Laufzeit in der Ab-fragegröße aufweisen kann. Bartholomäus Ende Matr.-Nr. 2063702 6.2 Minimierung von Abfragen Definition 14: Abfragehomomorphismus
Unter einem Homomorphismus h : q1 → q
2 für zwei Abfragen qi ≡ (Bi, Hi, Ci) : i { 1, 2 } versteht man eine Ersetzung Φ von Variablen und anonymen Ressourcen, so dass folgende Bedingungen gelten: 1. Φ(H1) = H2
2. Φ(B1) ⊆ B2
3. C1 ⊆ C2
Des Weiteren gilt stets q1 ⊆ q2, wenn für alle Datenbanken D stets ans(q1, D) ⊆ ans(q2, D) erfüllt ist. Lemma 7:
Für zwei Abragen q1, q2 gilt:
q2 ⊆ q1 ↔ ∃ein Homomorphismus h : q1 → q
→: Nach Annahme gilt q2 ⊆ q1, des Weiteren sei D die Datenbank, die aus B2 hervorgeht, wenn jede Variable ?X in B2 durch die entsprechende Konstante c?X ersetzt wird. Die Bewertung v sei hiezu die entsprechende Abbildung, d.h. v bildet jede Variable ?X auf c?X ab → v(H2) ∈ ans(q2, D) ⊆ ans(q1, D) → ∃ eine Bewertung v' : D = v'(B1) ∧ v'(H1) = v(H2) → Entspreche h der Ersetzung v-1 ◦ v', die Bedingung C1 ⊆ C2 folgt aus q2 ⊆ q1 → ∃ein Homomorphismus h : q1 → q ←: ∃ein Homomorphismus h : q1 → q → ∀ Datenbanken D ∧ ∀ Bewertungen v gilt: D = v(B2) → D = v(Φ(B1)) → ∀ v(H2)∈preans(q2, D) gilt v(H1)∈preans(q1, D) da Φ(H1) = H2 und C1 ⊆ C2 → q2 ⊆ q1 Eine Abfrage q = (H, B, C) wird minimal genannt, wenn keine andere Abfrage q' = (H', B', C') existiert, die äquivalent zu q ist und für die gleichzeitig B' < B gilt, wobei B die Anzahl der E-lemente des Bodies bezeichnet. Lemma 8:
Für jede Abfrage q = (H, B, C) existiert eine minimale Abfrage qm = (Hm, Bm, Cm) die äquivalent zu
q ist und für die Bm ⊆ B und Cm ⊆ C gilt. Beweis:
Entweder ist q bereits die minimale Abfrage dann ist die obere Aussage trivialer Weise erfüllt oder
es existiert eine minimale Abfrage q', die äquivalent zu q ist. Da q' eventuell die oberen Bedingun-
gen für den Body und die Einschränkungen nicht erfüllt, muss sie zu der gesuchten Abfrage qm
transformiert werden. Man beachte, dass wegen q ≡ q' ebenfalls q' ⊆ q sowie q ⊆ q' gilt. Deshalb existieren die beiden folgenden Homomorphismen Φ1 : q → q' sowie Φ2 : q' → q. Die Hinterein-anderausführung dieser führt dann zur gesuchten minimalen Abfrage, da stets qm = Φ2 ◦ Φ1(q) gilt. Bemerkung 7:
Man muss sich stets vor Augen halten, dass die Minimierung einer Abfrage nicht mit der Umwand-
lung des Bodies einer Abfrage zu einem äquivalenten kompakten Graphen übereinstimmt. Der
Grund hierfür ist, dass der Homomorphismus zur Minimierung der Abfrage zusätzlich den Header
der Abfrage unverändert lassen muss.
Bartholomäus Ende Matr.-Nr. 2063702 6.2 Minimierung von Abfragen
Lemma 9:
Für zwei Abfragen q1, q2 sind die folgenden Probleme NP-vollständig:
1. Gilt q1 ≡ q2?
2. Gilt q1 ⊆ q2?
Beweis:
1. Für den Nachweis, dass das Problem NP-hart ist verweise ich auf die Behauptung in [4], dass
das Äquivalenzproblem für zwei Tableaus ebenfall NP-hart ist. Da für die Äquivalenz zweier Abfragen stets C1 = C2 gelten muss, lassen sich diese zudem problemlos als klassisches Tableau mit drei Attributen kodieren. 2. Da sich q1 ≡ q2 auf die Lösung der zwei Teilproblem Probleme q1 ⊆ q2 sowie q2 ⊆ q1 reduzieren
lässt, folgt dass diese Problem NP-hart ist unmittelbar aus der NP-Vollständigkeit des Problems q1 ≡ q2. Die Zugehörigkeit beider Probleme zu NP folgt unmittelbar, aus der Tatsache, dass ein Homo-morphismus ein polynomiell verifizierbarer Zeuge ist. 6.3. Eliminierung von Redundanzen
Wie bereits die Bemerkung 7 gezeigt hat, weisen Antworten typischer Weise Redundanzen auf, die vermieden werden sollten. Ideal wäre es wenn die Antwortmenge ans(q, D) einem kompakten Gra-phen entsprechen würde und somit frei von Redundanz wäre. Die folgende Betrachtung verfolgt dieses Ziel und untersucht dabei die auftretende Komplexität. Der triviale Ansatz eine redundanzfreie Antwort zu erhalten, besteht zunächst aus der Bestimmung des Graphen G = ans(q, D) und der folgenden Berechnung eines kompakten Graphen der äquiva-lent zu G ist. Wie wir bereits gesehen haben ist die letzte Berechnung schwierig, jedoch existiert für den Worst-Case keine bessere Alternative, wie der folgende Satz beweist. Satz 4:
Die Beantwortung der Frage, ob für eine beliebige Datenbank D und Anfrage q ans (q,
ist, ist NP-Vollständig (in der Größe von D). Beweis:
Dieser Satz ist eine unmittelbare Konsequenz aus der Reduktion des Problems aus Satz 2 auf dieses
Problem, wobei die Reduktion ausnutzt, dass für die Union-Semantik eine datenunabhängige Iden-
titätsabfrage existiert (Beispiel 6).
Bei der Verwendung der Merge-Semantik kann die obige Frage unter bestimmten Vorbedingungen effizient, d.h. bereits in polynomieller Zeit beantwortet werden, wie wir gleich sehen werden. Satz 5:
Für eine beliebige kompakte Datenbank D und eine beliebige Abfrage q mit kompakten Header,
kann die Frage, ob ansm(q, D) kompakt ist, bereits in polynomieller Zeit gelöst werden.
Beweis:
Sei M = ansm(q, D), des Weiteren sollen mit dem Begriff einfaches Mapping solche Mappings be-
zeichnet werden, die Abbildungen von einfachen Antworten nach M entsprechen. Bartholomäus Ende Matr.-Nr. 2063702 6.3 Eliminierung von Redundanzen Die Hauptidee ist, dass bei der Verwendung von der Merge-Semantik die einfachen Antworten keine Variablen teilen und somit alle Mappings µ : M → M genau der Vereinigung von einfachen Mappings µj : Hj → M für jede einfache Antwort Hj entsprechen. Deshalb muss ein Algorithmus der ein Mapping µ : M → M sucht, das zu einer echten Instanz führt lediglich einfache Mappings betrachten, wobei zwei Test durchzuführen sind. Der erste ist, die Frage ob zumindest ein Mapping besteht, das zu einer Instanz eines anderen führt und der zweite ist, die Frage, ob es zwei Mappings gibt, die sich lediglich in ihren anonymen Ressourcen unterscheiden. Da beide Tests in poly(# einfache Mappings) durchführbar sind, folgt dass sie in poly( D ) realisiert werden können, da wir bereits im zweiten Teil des Beweises von Satz 3 gesehen haben, dass die Anzahl der einfachen Mappings durch poly( D ) begrenzt sind. 7. Schlussfolgerungen und RAL
Die angestellten Betrachtungen haben gezeigt, dass mit der Verwendung von RDF Datenbanken neuen Anforderungen an Abfragesprachen einhergehen. Dies ist eine unmittelbare Folge von Kon-strukten wie den anonymen Ressourcen und Reification, die dem RDF eine enorme Ausdruckskraft bieten, ohne dabei die Komplexität der Abfragen erheblich zu erhöhen. Dabei spielen vor allem die anonymen Ressourcen eine entscheidende Rolle, da wie wir gesehen haben durch die existierenden Interpretationsmöglichkeiten zwei unterschiedliche Semantiken ent-stehen, die zu verschiedenen Anforderungen an die Bestimmung von Anfrageergebnissen führen. Dies zeigt, dass die theoretischen Aspekte, auf denen RDF Abfragesprachen basieren, noch weiter untersucht werden müssen. Insbesondere das Fehlen von einer Algebra, die die Definition sowie den Vergleich von unter-schiedlichen RDF Abfragesprachen ermöglicht, zeigt, dass auf diesem Gebiet noch Forschungsbe-darf existiert, obwohl mit der Definition von RAL in [5], eine Algebra für RDF Abfragesprachen vorgeschlagen wird, die einen ersten Schritt in diese Richtung unternimmt. Jedoch ist dies erst der Anfang, der aber bereits ein Hauptproblem von RDF Abfragesprachen aufzeigt. Nämlich dass sie (die hier vorgestellte Abfragesprache ist davon nicht ausgenommen) nur einer bloßen Definition der Logik für die Definition von Abfragen entsprechen und die interne Arbeitsweise hinter API-Aufrufen verbergen, so dass keine einheitlicher Standard existiert. Darüber Hinaus zeigt RAL, dass man sich nicht nur auf Operatoren für die Extraktion der Daten beschränken darf, sondern aufgrund der RDF zugrunde liegenden Struktur ebenfalls Operatoren für Wiederholungen sowie für die Konstruktion von RDF Datenbanken benötigt. Bartholomäus Ende Matr.-Nr. 2063702 8. Literaturverzeichnis 8. Literaturverzeichnis
[1] Manola F., Miller E.: RDF Primer. W3C Working Draft 10 October 2003
[2] Hayes P.: RDF Semantics. W3C Working Draft 10 October 2003
[3] Tolle K.: Analyzing and Parsing RDF. Diplomarbeit, Universität Hannover, Fachbereich Ma-
thematik, Studienrichtung Informatik, Januar 2000 [4] Gutierrez C., Hurtado C., Mendelzon A.: Formal aspects of querying RDF databases
[5] Barna P., Frasincar F., Houben G., Vdovjak R.: RAL: an Algebra for Querying RDF
wwwis.win.tue.nl/ hera/papers/WISE2002/ral.pdf [6] Hell P., Nestril J.: The core of a graph. In: Discrete Mathematics 109. North-Holland 1992,
[7] Ullman J. D.: Principles of DATABASE SYSTEMS. 2nd ed. Rockville: Computer Science
Press, 1984. – ISBN 0-7167-8069-0 Bartholomäus Ende Matr.-Nr. 2063702

Source: http://www.dbis.cs.uni-frankfurt.de/~tolle/RDF/DBISResources/Sem_WS0304/Formale_Betrachtung.pdf