Graph Pattern Semantik
Michael Schmidt, 06.05.2008
1
RDF Formalisierung
3 disjunkte Mengen URIs (U) Blank Nodes (B) Literale (L) Wir schreiben UB für die Vereinigung von
U und B usw. RDF Tripel
(s,p,o) UB x U x UBL RDF Datenbank: Menge von Tripeln
2
Basic Graph Patterns
Unendliche Menge von Variablen V Basic Graph Pattern
(t1, t2, t3) UV x UV x ULV Beispiele für Basic Graph Patterns
(?person, rdf:type, foaf:Person) (lx:Person1, ?y, ?z) (?x,?y,?z) (lx:Person1, foaf:name, „Linus Torvalds“)
3
Filter-Bedingungen
Atomare Filter-Bedingungen (A op B), where
A ULV B ULV op {<,<=,=,>=,>}
Filter-Bedingungen Verknüpfung von atomaren Filter-Bedingungen
durch Operatoren && (and), || (or), or ! (not) Beispiele:
Atomar: (?a = „test“), (?a < ?b) Zusammengesetzt: ((?a = „a“) && !(?b < ?c))
4
Allgemeine Graph Patterns
Rekursive Definition Ein Basic Graph Pattern ist ein Graph
Pattern Wenn G1 und G2 Graph Patterns sind,
dann auch G1 UNION G2
Wenn G1 und G2 Graph Patterns sind, dann auch G1 AND G2
Wenn G1 und G2 Graph Pattern sind, dann auch G1 OPTIONAL G2
Wenn G ein Graph Pattern ist, und R eine (ggf. atomare) Filter-Bedingung, dann ist auch G FILTER R ein Graph Pattern
5
Mappings zur Ergebnisrepräsentation
Graph Patterns werden auf RDF Dokumenten ausgewertet
Darstellung einer möglichen Lösung als Mapping von Variablen im Graph Pattern zu Elementen im Eingabegraphen
Mapping ist eine partielle Funktion
μ : V UBL
6
Beispiel: Mapping
?person ms:Person1
?name „Bill Gates“
?type foaf:Person
μ
myns:salary
7
Mappings
Domäne eines Mappings Menge der Variablen, für die die Abbildung
definiert ist
Für das Mapping oben:dom(μ)={?person,?name,?type}
?person ms:Person1
?name „Bill Gates“
?type foaf:Person
μ
8
Mapping: Kompatibilität
Zwei Mappings μ1, μ2 kompatibel, wenn
für alle x dom(μ1) dom(μ2): μ1(x)=μ2(x)
?person ms:Person1
?name „Bill Gates“
?type foaf:Person
?person ms:Person1
?name „Bill Gates“
?salary „1000000“
μ1 μ2
dom(μ1)={?person,?name,?type) dom(μ2)={?person,?name,?salary)
dom(μ1) dom(μ2)={?person,?name)
μ1(?person) = μ2(?person) = ms:Person1
μ1(?name) = μ2(?name) = „Bill Gates“
9
kompatibel
Mapping: Kompatibilität
?person lx:Person1μ2
?person ms:Person1
?name „Bill Gates“
?type foaf:Person
μ1
dom(μ1)={?person,?name,?type) dom(μ2)={?person)
dom(μ1) dom(μ2)={?person)
μ1(?person) = ms:Person1
μ2(?person) = lx:Person1
Zwei Mappings μ1, μ2 kompatibel, wenn
für alle x dom(μ1) dom(μ2): μ1(x)=μ2(x)
10
nichtkompatibel
Auswertung von Graph Patterns
Ergebnis: Menge von Mappings Beispiel:
(?x,rdf:type,foaf:Person)
?x ms:Person1μ1
?x lx:Person1μ2
Ergebnis S={μ1, μ2}11
Auswertung von Graph Patterns
Ergebnis: Menge von Mappings Beispiel:
(?x,rdf:type,foaf:Person)
?x ms:Person1μ1
?x lx:Person1μ2
S={{?x -> ms:Person1},
{?x -> lx:Person1}} 12
Operationen auf Mapping-Mengen
UNION
JOIN
SETMINUS
LEFTJOIN
13
UNION von Mapping-Mengen
{{?a -> x}, {?a -> x, ?b -> y}} {{?a -> x}, {?b -> y}}= {{?a -> x}, {?a -> x, ?b -> y}, {?b -> y}}
UNION
Beispiel
14
JOIN von Mapping-Mengen
JOIN
{{?a -> w}, {?a -> x, ?b -> y}}{{?a -> y}, {?b -> y, ?c -> z}}= {{?a -> w, ?b -> y, ?c -> z}, {?a -> x, ?b -> y, ?c -> z}}
Beispiel
15
MINUS von Mapping-Mengen
SETMINUS
{{?a -> w}, {?a -> x, ?b -> y}} \{{?a -> y}, {?a -> x, ?b -> y, ?c -> z}}= {{?a -> w}}
Beispiel
16
LEFTJOIN von Mapping-Mengen
LEFTJOIN
{{?a -> w}, {?a -> x, ?b -> y}} {{?a -> y}, {?a -> x, ?b -> y, ?c -> z}} =({{?a -> w}, {?a -> x, ?b -> y}} {{?a -> y}, {?a -> x, ?b -> y, ?c -> z}})({{?a -> w}, {?a -> x, ?b -> y}} \ {{?a -> y}, {?a -> x, ?b -> y, ?c -> z}})= {{?a -> x, ?b -> y, ?c -> z}} {{?a -> w}}= {{?a -> x, ?b -> y, ?c -> z}}, {{?a -> w}}
Beispiel
17
Graph Pattern Semantik
Definiert mit Hilfe der vorher diskutierten Operatoren
Basic Graph Pattern t, Graph Patterns Pi, Dokument D
μ(t) := ersetze Variablen in t nach μ
18
Beispiel Graph Pattern Semantik
D={
(ms:Person1,rdf:type,foaf:Person), (ms:Person1,foaf:name,“Bill Gates“),
(ms:Person1,foaf:knows,lx:Person1), (ms:Person1,myns:salary,_:salary1),
(_:salary1,rdf:value,“1000000“), (_:salary1,myns:unit,“US Dollar“),
(lx:Person1,rdf:type,foaf:Person), (lx:Person1,foaf:knows,ms:Person1)
(lx:Person1,foaf:name,“Linus Torvalds“), (lx:Person1,foaf:knows,lx:Person2)
}
((?person,rdf:type,foaf:Person) AND (?person,foaf:name,?name))
OPTIONAL ((?person,myns:salary,?s1) AND (?s1,rdf:value,?s2))
Dokument
Graph Pattern
19
Ergebnis und Ergebnisdarstellung
((?person,rdf:type,foaf:Person) AND (?person,foaf:name,?name))
OPTIONAL ((?person,myns:salary,?s1) AND (?sal1,rdf:value,?s2))
Graph Pattern P
[[P]]D={{?person -> ms:Person1, ?name -> „Bill Gates“,
?s1 -> _:salary1, ?s2 -> „1000000“},
{?person -> lx:Person1, ?name -> „Linus Thorvals“}}
Ergebnis
?person ?name ?s1 ?s2ms:Person1 „Bill Gates“ _:salary1 „1000000“
lx:Person1 „Linus Thorvals“
Ergebnis in tabellarischer Form
20
Ergebniscodierung in Implementierung
Ausgabe in tabellarischer Form in CSV-Format Zeile 1: Variablennamen in beliebiger
Reihenfolge, durch Kommata getrennt Folgende Zeilen: Ergebnistupel in
beliebiger Reihenfolge
?name;?person;?s1;?s2
„Linus Thorvals“;lx:Person1;;
„Bill Gates“;ms:Person1;_:salary1;„1000000“
Mögliche Programmausgabe
21
Erfülltheit von Filter-Bedingungen
Sei R eine Filter-Bedingung. μ erfülltBedingung R (μ |= R), wennSei R eine Filter-Bedingung. μ erfülltBedingung R (μ |= R), wenn
Analog zum zweiten Fall: <, <=, >=, >
22
Semantik von Filter-Bedingungen
Erhalte Mappings, die Bedingung erfüllen
P FILTER (?person = lx:Person1)
Graph Pattern P FILTER R
[[P]]D={{?person -> ms:Person1, ?name -> „Bill Gates“,
?s1 -> _:salary1, ?s2 -> „1000000“},
{?person -> lx:Person1, ?name -> „Linus Thorvals“}}
P FILTER (?person = ms:Person1)
= {{?person -> lx:Person1, ?name -> „Linus Thorvals“}}
Ergebnis
23
Implementierung Einlesen von Graph Patterns aus Datei
GraphPattern ::= SimpleGraphPattern | ComposedGraphPattern |
FilterGraphPattern
SimpleGraphPattern ::= „(„ Subject „,“ Predicate „,“ Object „)“
ComposedGraphPattern ::= SimpleGraphPattern Operator SimpleGraphPattern
FilterGraphPattern ::= SimpleGraphPattern „FILTER“ FilterCondition
Subject ::= URI | Variable
Predicate ::= URI | Variable
Object ::= URI | Literal | Variable
FilterCondition ::= FilterSubexp FilterOperator FilterSubexp
FilterSubExp ::= URI | Literal | Variable
Operator ::= „AND“ | „UNION“ | „OPTIONAL“
FilterOperator ::= „<“ | „<=“ | „=“ | „>“ | „>=“
, wobei URI eine URI ist (möglicherweise in Prefix-Notation), Literal ein String in Anführungszeichen, und Variable eine Variable der Form ?[a-zA-Z]+ (z.B. ?name, ?x, ?abcD)24
Aufgaben
Berechne auf dem Datensatz D (Folie 19):
(a) [[(?person1,foaf:knows,?person2) AND (?person2,foaf:knows,?person1]]D
(b) [[(?person1,rdf:type,foaf:Person) OPTIONAL ((?person1,foaf:knows,?person2) AND (?person2,myns:salary,?sal1) AND (?sal1,rdf:value,?sal2))]]D
Was berechnen die Anfragen (in Worten)?
25