SPARQL Sémantika. Peter Vojtáš

SPARQL Sémantika Peter Vojtáš Department of Software Engineering Faculty of Information Technology Czech Technical University in Prague ©Peter Vojtáš, Jan Dědek, Ivo Lašek

Semantic Web MI‐SWE 2011 Lecture 8 MI‐POA

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Obsah Sledujeme německou knížku

SPARQL Semantik http://semantic-web-grundlagen.de

P. Hitzler, M. Krötzsch, S. Rudolph, Y. Sure Semantic Web Grundlagen Springer 2008, ISBN: 978-3-540-33993-9

SPARQL – sémantika

10-SPARQL-Semantik-2009.pdf

MI-SWE 2011

2

Obsah 1. Úvod a motivace 2. Transformace dotazů v SPARQL do SPARQL algebry 3. Počítání v SPARQL algebře 4. Shrnutí

MI-SWE 2011


3

SPARQL Minulá přednáška: SPARQL jako dotazovací jazyk pro RDF PREFIX ex: SELECT ?buch, ?autor WHERE { ?buch ex:VerlegtBei . ?buch ex:Preis ?preis . ?buch ex:Autor ?autor FILTER (?preis < 35) } ORDER BY ?preis LIMIT 10 Charakteristika SPARQL: jednoduché, nepovinné a alternativní grafové vzory Filter Výstupní formáty (SELECT, CONSTRUCT, . . . ) Modifikátory (ORDER BY, LIMIT, . . . ) Pro tuto přednášku zbylo zodpovědět otázku: Jak je přesně definovaná sémantika SPARQL? MI-SWE 2011


4

K čemu sémantika Zatím neformální představení SPARQL (my jsme měli článek čilanů) Použivatel: „které odpovědi můžu očekávat na můj dotaz?“ Vývojář: „Jak se bude chovat moje SPARQL implementace?“ Výrobce: „Je můj produkt v souladu se SPARQL?“ Formální sémantika snad do toho vnese více světla

MI-SWE 2011


5

Sémantika dotazovacích jazyků Sémantika formální logiky: Modelově teoretická sémantika: které interpretace splňují znalostní bázi důkazově teoretická sémantika: které důkazy (odvození) z dané znalostní báze jsou přípustné? ... Sémantika programovacích jazyků: Axiomatická sémantika: která logická tvrzení jsou pravdivá pro daný program? Operační sémantika: jak vypadá běh daného programu? Denotační sémantika: jak lze daný programm reprezentovat jako funkci vstup-výstup? Co teď s dotazovacím jazykem? MI-SWE 2011


6

Sémantika dotazovacích jazyků Sémantika dotazovacích jazyků: Dotaz jako splňování (query entailment) dotaz jako popis přípustných výsledků databáze jako množina logických předpokladů (teorie) odpověď na dotaz jako logické odvození Např.: OWL DL a RDF(S) jako dotazovací jazyky, konjunktivní dotazy Dotazovací algebra dotaz jako popis výpočtu výsledků databáze jako vstup odpověď jako výstup Např.: relační algebra pro SQL, SPARQL-algebra MI-SWE 2011


7

Transformace dotazů do SPARQL algebry { ?kniha ex:Cena ?cena . FILTER (?cena < 15) OPTIONAL { ?kniha ex:Nazev ?nazev . } { ?kniha ex:Autor ex:Shakespeare . } UNION { ?kniha ex:Autor ex:Marlowe . } } Sémantika SPARQL-ovského dotazu: 1. Transformace dotazu do algebraického výrazu 2. Spočítání výsledku tohoto výrazu MI-SWE 2011


8

Transformace dotazů do SPARQL algebry: BGP { ?kniha ex:Cena ?cena . FILTER (?cena < 15) OPTIONAL { ?kniha ex:Nazev ?nazev . } { ?kniha ex:Autor ex:Shakespeare . } UNION { ?kniha ex:Autor ex:Marlowe . } } První krok: transformace jednoduchých grafových vzorů Operátor BGP Basic Graph Pattern Současně rozepsaní zkráceného URI

MI-SWE 2011


9

Transformace dotazů do SPARQL algebry: BGP { BGP(?kniha ?cena .) FILTER (?cena < 15) OPTIONAL { BGP(?kniha .) } UNION { BGP(?kniha .) } } První krok: transformace jednoduchých grafových vzorů Operátor BGP Basic Graph Pattern Současně rozepsaní zkráceného URI MI-SWE 2011


10

Transformace do SPARQL algebry: Union { BGP(?kniha ?cena .) FILTER (?cena < 15) OPTIONAL { BGP(?kniha .) } UNION { BGP(?kniha .) } } Druhý krok: skládání alternativních grafových vzorů Operátor Union vztahuje se na UNION {} ohraničené grafové vzory UNION ( váže silněji než konjunkce) Uzávorkování vícero alternativ jako v minulé přednášce (zleva asociativní)

MI-SWE 2011


11

Transformace do SPARQL algebry: Union { BGP(?kniha ?cena .) FILTER (?cena < 15) OPTIONAL { BGP(?kniha .) } , { BGP(?kniha .) }) } Druhý krok: skládání alternativních grafových vzorů Operátor Union vztahuje se na UNION {} ohraničené grafové vzory UNION ( váže silněji než konjunkce) Uzávorkování vícero alternativ jako v minulé přednášce (zleva asociativní)

MI-SWE 2011


12

Transformace do SPARQL algebry Join(M1, M2)

konjunktivní spojení M1 a M2

LeftJoin(M1, M2, F)

Nepovinné spojení M1 s M2 pod podmínkou F

Filter (F, M)

Použití diltrovací podmínky F na M

Z

Konstanta pro prázdný výraz

MI-SWE 2011


13

Transformace do SPARQL algebry Join(M1, M2)

konjunktivní spojení M1 a M2

LeftJoin(M1, M2, F)

Nepovinné spojení M1 s M2 pod podmínkou F

Filter (F, M)

Použití filtrovací podmínky F na M

Z

Konstanta pro prázdný výraz

Trasformace se vykonává postupně zevnitř ven: 1. Zvol nejaký „nejvnitřnější“ grafový vzor M; 2. Odstraň filtrovací podmínky z M; GF := konjunkce filtrovacích podmínek 3. Inicializuj G := Z, a zpracuj všechny podvýrazy UA následovně: a. pokud UA = OPTIONAL Filter(F, A): G := LeftJoin(G, A, F) b. jinak, pokud UA = OPTIONAL A: G := LeftJoin(G, A, true) c. jinak: G := Join(G,UA) 4. pokud GF je neprázdné: G := Filter(GF,G)

MI-SWE 2011


14

Transformace SPARQL algebry:(Left)Join, Filter { BGP(?kniha ?cena .) FILTER (?cena < 15) OPTIONAL { BGP(?kniha .) } , { BGP(?kniha .) }) }

MI-SWE 2011


15

Transformace SPARQL algebry:(Left)Join, Filter { BGP(?kniha ?cena .) FILTER (?cena < 15) OPTIONAL Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) }

MI-SWE 2011


16

Transformace SPARQL algebry:(Left)Join, Filter { BGP(?kniha ?cena .) FILTER (?cena < 15) OPTIONAL Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) }

MI-SWE 2011


17

Transformace SPARQL algebry:(Left)Join, Filter FILTER ((?cena < 15) Join( LeftJoin( Join(Z, BGP(?kniha ?cena .)), Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) ) ) MI-SWE 2011


18

Transformace SPARQL algebry Modifikátory G := OrderBy(G, zadaní uspořádání) G := Slice(G, o, l) ořeže výsledkovou listinu na interval délky l od pozice o, pokud bylo použito „OFFSET o“ a „LIMIT l“ G := Project(G, seznam proměnných) pokud to bylo v SELECT G:=Distinct(G) …

MI-SWE 2011


19

Definice operací SPARQL algebry Jak jsou definovány operace SPARQL-algebry? Výstup: „tabulka výsledků“ (formátování nehraje roli) vstup: dotazovaná RDF-Databáze Částečné výsledky podvýrazů Rozličné parametry podle operace Prázdný výraz Z? Výsledek právě jeden (funkce s prázdným oborem hodnot) „tabulka s jedním řádkem ale žádnými sloupci“ Více předminulá přednáška MI-SWE 2011


20

Příklad @prefix ex: . @prefix xsd: . ex:Hamlet ex:Autor ex:Shakespeare ; ex:Preis "10.50"^^xsd:decimal . ex:Macbeth ex:Autor ex:Shakespeare . ex:Tamburlaine ex:Autor ex:Marlowe ; ex:Preis "17"^^xsd:integer . ex:DoctorFaustus ex:Autor ex:Marlowe ; ex:Preis "12"^^xsd:integer ; ex:Titel "The Tragical History of Doctor Faustus" . ex:RomeoJulia ex:Autor ex:Brooke ; ex:Preis "9"^^xsd:integer . { ?kniha ex:Cena ?cena . FILTER (?cena < 15) OPTIONAL { ?kniha ex:Nazev ?nazev . } { ?kniha ex:Autor ex:Shakespeare . } UNION { ?kniha ex:Autor ex:Marlowe . } MI-SWE 2011


} 21

Příklad FILTER ((?cena < 15) Join( LeftJoin( Join(Z, BGP(?kniha ?cena .)), Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) ))

kniha ex:Tamburlaine ex:DoctorFaustu s MI-SWE 2011 SPARQL – sémantika

22

Příklad FILTER ((?cena < 15) Join( LeftJoin( Join(Z, BGP(?kniha ?cena .)), Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) ))

kniha ex:Macbeth ex:Hamlet MI-SWE 2011


23

Příklad FILTER ((?cena < 15) Join( LeftJoin( Join(Z, BGP(?kniha ?cena .)), Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) )) kniha ex:Hamlet ex:Macbeth ex:Tamburlaine ex:DoctorFaustu s MI-SWE 2011


24

Příklad FILTER ((?cena < 15) Join( LeftJoin( Join(Z, BGP(?kniha ?cena .)), Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) )) kniha

cena

ex:Hamlet

"10.50"ˆˆxsd:decimal

ex:Tamburlaine

"17"ˆˆxsd:integer

ex:DoctorFaustus

"12"ˆˆxsd:integer

ex:RomeoJulia

"9"ˆˆxsd:integer

MI-SWE 2011


25

Příklad FILTER ((?cena < 15) Join( LeftJoin( Join(Z, BGP(?kniha ?cena .)), Join(Z, BGP(?kniha .) ) , Join(Z, BGP(?kniha .) )) )) kniha ex:DoctorFaustus

MI-SWE 2011

nazev "The Tragical History of Doctor Faustus" SPARQL – sémantika

26


cena

ex:Hamlet


ex:Tamburlaine

"17"ˆˆxsd:integer

ex:DoctorFaustus

"12"ˆˆxsd:integer

ex:RomeoJulia

"9"ˆˆxsd:integer

MI-SWE 2011


nazev

"The Tragical History..."

27


cena

ex:Hamlet


ex:Tamburlaine

"17"ˆˆxsd:integer

ex:DoctorFaustus

"12"ˆˆxsd:integer

ex:RomeoJulia

"9"ˆˆxsd:integer

MI-SWE 2011


nazev


28


cena

ex:Hamlet


ex:Tamburlaine

"17"ˆˆxsd:integer

ex:DoctorFaustus

"12"ˆˆxsd:integer

ex:RomeoJulia

"9"ˆˆxsd:integer

MI-SWE 2011


nazev


29

SPARQL Sémantika. Peter Vojtáš

Recommend Documents