Tripel-Tabelle

RDF Graph Triples
Subj.	Prop.	Obj.
ID1	type	BookType
ID1	title	“XYZ”
ID1	author	“Fox, Joe”
ID1	copyright	“2001”
ID2	type	CDType
ID2	title	“ABC”
ID2	artist	“Orr, Tim”
ID2	copyright	“1985”
ID2	language	“French”
ID3	type	BookType
ID3	title	“MNO”
ID3	language	“English”
ID4	type	DVDType
ID4	title	“DEF”
ID5	type	CDType
ID5	title	“GHI”
ID5	copyright	“1995”
ID6	type	BookType
ID6	copyright	“2004”

Diskussion

• Eine simple Anfrage wie "Alle Bücher von Joe Fox im Jahr 2001" erfordert wiederholte Zugriffe auf die selbe Tabelle - teuer!
• RDBMS hat keine Struktur über Tabellen zur Verfügung, die zur Optimierung genutzt werden können
  • keine statistische Auswertung
  • kein paralleler Zugriff

Tripel-Store, extremer Ansatz: Zum Teil wird mit dezidierten Triple-DB Implementierungen experimentiert

• Freebase-Backend: http://blog.freebase.com/2008/04/09/a-brief-tour-of-graphd/
• das ist Forschung, die beobachtet werden muss: curriculare Folgen?
• für die Praxis nur mit besonderer Begründung relevant

Unsere Frage: Wie können wir Tripel optimiert in klassischen RDBMS speichern?

Ansatz: property table mit Zuordnung von Attributen zu Klassen

• Bemerke: Properties können in mehreren Tabellen vorkommen: ggf. sind UNION-Operationen erforderlich

Class: BookType
Subj.	Title	Author	copyright
ID1	“XYZ”	“Fox, Joe”	“2001”
ID3	“MNP”	NULL	NULL
ID6	NULL	NULL	“2004”

Class: CDType
Subj.	Title	Artist	copyright
ID2	“ABC”	“Orr, Tim”	“1985”
ID5	“GHI”	NULL	“1995”

Left-Over Triples
Subj.	Prop.	Obj.
ID2	language	“French”
ID3	language	“English”
ID4	type	DVDType
ID4	title	“DEF”

Einsicht: generische zeilenorientierte Datenhaltung ist nicht optimal

• Speicherung von Zeilen als Data-Records
• Postgres: 27 Byte Metadaten per Reihe
  • id
  • last upgrade
• bei gezipptem content reichen weitere 8 Byte für die eigentliche Datenhaltung meist aus
• der gesamte Record muss gelesen werden, bevor auf einzelne Attribute zugegriffen werden kann: Projektionen sind nicht Bandbreiten-optimal
• Problem Nullwerte

Ansatz: De- (!) Normalisierung von Tabellen durch Clusterung von unabhängigen, sachlogisch zusammengehörenden und nicht mehrwertigen Properties

Bemerke:

• jede Property ist in genau einer Tabelle enthalten
• NULLs können die Tabelle ggf. sogar dominieren
• multi valued attributes (MVA) und n:m-Relationen müssen separat vorgehalten werden
• Property Tables müssen sorgfältig konstruiert werden
  • ggf. manuell
  • Datenanalyse: Welche Properties sind paarweise unabhängig?

Clustered Property Table
Subj.	Type	Title	copyright
ID1	BookType	“XYZ”	“2001”
ID2	CDType	“ABC”	“1985”
ID3	BookType	“MNP”	NULL
ID4	DVDType	“DEF”	NULL
ID5	CDType	“GHI”	“1995”
ID6	BookType	NULL	“2004”

Left-Over Triples
Subj.	Prop.	Obj.
ID1	author	“Fox, Joe”
ID2	artist	“Orr, Tim”
ID2	language	“French”
ID3	language	“English”

Idee: Lege für jede Property eine eigene Tabelle an

Vorteile der vertikalen Partitionierung

• triviale Unterstützung mehrwertiger Attribute
• trivialerweise keine Nullwerte
• triviale Projektionen

Konsequenz: Ein dezidiertes spaltenorientiertes RDBMS für RDF-Tripel

• muss weniger allgemeine Lösungen bereitstellen als ein generisches RDBMS für beliebige Schemata
• kann speziell auf spaltenorientierte Operationen hin optimiert werden

spaltenorientierte Datenhaltung

• Metadaten zu den Spalten sind in eigenen Spalten abgelegt (und können selektiv ignoriert werden)
• sortierte Spalten können besonders effektiv durchsucht werden
• Vereinigen von sortierten Spalten (Einfügen neuer Tupelmengen) ist besonders schnell
• Sortierung ist besonders relevant
• Persistenz: Speichere jede Spalte in einer eigenen Datei - die im Query-Fall parallel gelesen werden kann (extensive prefeching)

Offene Fragestellung: In Bezug auf welche Queries hin optimieren wir?

• Randbedingung jeder Datenhaltung: die Queries!
• RDF-Modelle sehen anders aus als XML- oder eben relationale Modelle
• im Ggs. zur RDMBS-Praxis kennen wir in RDF-Umgebungen die zukünftigen Queries i.A. nicht

In Bezug auf welche Queries hin optimieren wir? Anfragen an das RDF-Datenmodell bedingen typische Query-Strukturen

• RDF wurde als Datenmodell eingeführt, nämlich als gerichteter Graph.
• Queries gegen einen RDF-Graphen sind sog. Graph-Queries
• Sind alle Graph-Queries 1:1 nach SQL übersetzbar?

(Quelle: http://www.cloudera.com/wp-content/uploads/2010/03/kurt3.png )

Wer fragt einen RDF-Graphen an?

• User, vermittelt durch Applikationen
• Inferencing-Engines! (z.B. Sesame2 RDF Store, enthält RDFS Inferencing Komponente;, früher: Deduktive Datenbanken, insbes. Datalog, heute: z.B. OntoBroker)

Anfragesprache: Nicht mehr SQL (ANSI 1986), sondern SPARQL (W3C Recommendation 15 January 2008)

• SELECT ?person WHERE { ?person :owns ?car .  ?car :madeIn :Detroit . }

Alternative Anfragesprache: F-Logic:

• QUERY Q_PersonOwsDetroitCar : ?- ?person [ owns -> ?car ] AND ?car : Car AND ?car [ madeIn -> Detroit ] .
• (Namespaces omitted)

Die Ontologie dazu: DemoOnto_PersonOwnsDetroitCar

Ergebnis:

• Übersetzung von SPARQL nach SQL oder F-Logic in Abhängigkeit der jeweiligen Datenmodellierung in RDBMS
• Es geht nicht mehr um SQL Query Optimierung, sondern um die Optimierung der Auswertung von SPARQL oder F-Logic Modellen gegen eine Tripelbasis

RDF Query-Optimierung durch Übersetzung von SPARQL oder F-Logic nach SQL ist derzeit Industrie-Spitzenforschung.

• OpenRuleBench: An Analysis of the Performance of Rule Engines http://rulebench.projects.semwebcentral.org/

Herausforderungen

• zirkuläre Graphen erzeugen rekursive SQL-Queries
• SQL2 kann nur End-Rekursion optimieren, keine generelle transitive Hülle möglich
• für komplexere Graph-Anfragen muss die Inferencing-Engine Zwischenergebnisse explizit zwischenspeichern
• User-Anfragen an RDF Daten in Triplestores werden durch meist durch ein Inferencing-System analysiert und ausgewertet
• Das Inferencing-System setzt komplexe Abfolgen von SQL-Statements an ein RDBMS ab, "kann" also mehr als SQL selbst

Optimierung der Datenhaltung jetzt in Bezug auf Aufgaben der Inferencing-Optimierung

Letzte Folie: Vortrag_DHBW2010_Zusammenfassung