Capitolo 2 Sintassi e semantica di SPARQL

Sintassi e semantica di SPARQL

Questo capitolo presenta la sintassi e la semantica del linguaggio SPAR-QL su cui si basa il sistema di tipi oggetto di questo studio. La sintassi riprende quella ufficiale del W3C e verrà presentata nella sezione 2.1. Non essendoci nessuna semantica uffiale, quella proposta nella sezione 2.2 si basa sulla semantica proposta da Pérez, Arenas e Gutierrez in [16].

2.1

Sintassi di SPARQL

Nella descrizione del linguaggio [17], il W3C ha definito una sintassi piuttosto complessa. Non tutte le parti di esse sono rilevanti per questo studio per cui verrà presentata una sintassi più breve e concisa.

Non sono stati considerati i modificatori di soluzione, il prologo della query, la query DESCRIBE e sono stati definiti in maniera più generale i graph pattern, le triple e il template della query CONSTRUCT.

La sintassi così semplificata è mostrata nella Tabella 2.1. I simboli terminali sono scritti con un carattere italico mentre i non terminali in maiuscoletto. La notazione usata nella SelectClause e DatasetClause

term1(term2 | term3) sta per term1term2 | term1term3

La Query può essere solo di tre tipi, manca la DESCRIBE. Questa restitui-sce le informazioni che si conoscono di una o più risorse indicate. La restitui-scelta

Query ::= SelectQuery | ConstructQuery | AskQuery

SelectQuery ::= SelectClause DatasetClause WhereClause

SelectClause ::= select (Var+ | ’*’)

ConstructQuery ::= ConstructClause DatasetClause WhereClause

ConstructClause ::= construct ConstructTemplate

ConstructTemplate ::= Triple+

AskQuery ::= ask DatasetClause WhereClause

DatasetClause ::= DatasetClause from

(DefGraphClause | NamGraphClause ) |

DefGraphClause ::= IriRef

NamGraphClause ::= named IriRef

WhereClause ::= where GP

GP ::= Triple | GP filter ValueC | GP and GP

| GP union GP | GP optional GP | VarOrIri graph GP | {}

Triple ::= VarOrGTerm VarOrIri VarOrGTerm .

ValueC ::= Var Op VarOrGTerm | isIRI(Var) | isLiteral(Var)

| isBlank(Var) | langMatches(Var, Var) | bound(Var) | sameTerm(Var,Var) | ¬ValueC | ValueC ∧ ValueC | ValueC ∨ ValueC

Op ::= > | < | ≥ | ≤

GraphTerm ::= IriRef | RDFLiteral | BNode

Var ::= ’?’Varname | ’$’Varname

VarOrGTerm ::= Var | GraphTerm

VarOrIri ::= Var | IriRef

Tabella 2.1: Sintassi SPARQL

delle informazioni restituite dalla DESCRIBE è decisa dal servizio, non è predicibile. Non essendo possibile determinare staticamente il risultato e quindi tipizzarla, si è scelto di non prenderla in considerazione.

Come visto in precedenza una componente importante della query è la forma del risultato. La prima parte dell’esecuzione (scelta del grafo ed esecuzione del graph pattern ossia DatasetClause e WhereClause) è indipendente dalla forma del risultato mentre la parte finale non lo è.

Infatti la SelectQuery ha una clausola che esegue una proiezione sulle variabili indicate o su tutte, la ConstructQuery ha un template composto da un insieme di triple e la AskClause ha solo una parola chiave in quanto la tabella di binding non viene manipolata ma semplicemente testata.

La DatasetClause è la clausola che permette di cambiare il grafo di default o inserire una lista di named graph. Tale clausola può anche essere vuota nel momento in cui si sceglie di eseguire la query nel grafo di default. La WhereClause semplicemente consiste in un graph pattern (GP ) che può essere composto da una semplice tripla, da un basic graph pattern (GP andGP ) o da altri pattern complessi. GP filter ValueC è la selezione con un predicato logico ValueC che può avere un operatore binario oppure usare funzioni inserite nella Tabella 1.5.

La tripla (Triple) è il componente base di un graph pattern. Può conte-nere nella posizione di soggetto e oggetto una variabile oppure un termine del grafo, mentre nelle proprietà può contenere o una variabile oppure una IRI. Questo termine ha una valenza doppia in quanto il template della query CONSTRUCT è composto da una o più triple in questa forma.

I termini del grafo (GraphTerm), come visto precedentemente, possono essere una IRI, un literal o un blank node. Le variabili possono essere precedute da il simbolo “$” oppure “?”.

2.2

Semantica di SPARQL

Il W3C non ha proposto nessuna semantica per il linguaggio SPARQL. Sebbene le componenti del linguaggio siano intuitive e ben definite, la loro combinazione rende le query complesse e l’assenza di una semantica formale crea delle difficoltà nell’interpretazione di alcune query.

Per il confronto della semantica proposta in questa tesi con altri studi si rimanda al capitolo 4. Vediamo nel dettaglio quindi la semantica proposta partendo da alcune fondamentali definizioni.

Come detto in precedenza la query viene eseguita sul grafo di default di un dataset. È possibile specificare un altro grafo o nella request al ser-vizio o direttamente nella query o in entrambi (in questo caso verrebbero considerati i grafi indicati nella request). Per semplificare queste diverse combinazioni scegliamo di preprocessare la query e quindi di avere nel-la query ottenuta delle cnel-lausole che rispecchiano correttamente tutte le diverse indicazioni.

Immaginiamo quindi di avere un ambiente iniziale (Env) rappresentato dal grafo di default del dataset. Se la query contiene delle DatasetClause l’ambiente cambia o si espande. Definiamo

Env : IriRefSet → Graph

come il tipo di una funzione che associa ad un riferimento il grafo a cui riferisce. Definiamo inoltre un record come una riga della tabella risultante dall’esecuzione della query; il record è quini una funzione del seguente tipo:

Record : VarOrBNode → GraphTerm

che associa ad una variabile o ad un blank node il rispettivo termine del grafo (VarOrBNode è un termine che può essere una variabile o un blank node). Dato un record t ed un termine del grafo g definiamo il valore del termine rispetto a quel record come

t[g]=        g1 se t= [. . . , g = g1, . . .] g altrimenti

Per esempio la variabile Var1di una tabella avrà valore t[Var1] nel record

t. Tre notazioni che saranno usate di seguito sono: • [] è il record vuoto.

• [a1 = g1, . . . , an = gn] è un record che associa ogni aial corrispondente

• [t1]+ [t2] denota l’estensione del record t1 con il record t2 con

sovra-scrittura di eventuali campi in comune. Per esempio: [?x=_:a, ?y=_:b]+ [?x=_:c, ?z=_:d] =

[?x=_:c, ?y=_:b, ?z=_:d]

Definiamo inoltre il tipo Rel come il tipo delle relazioni ovvero degli insiemi di record:

Rel : Set(Record) Con Set(item) indichiamo un insieme di item.

La tripla del pattern è il componente elementare di un graph pattern di una query SPARQL. La semantica Tr applicata ad una tripla in un ambiente restituisce una relazione.

~_Tr : Triple → (Env → Rel) ~TripleTre = ~T1 T2 T3Tre

~T1 T2 T3Tre = πvar(T1,T2,T3)(~T1T1e Z ~T2T2e Z ~T3T3e )

~VarT1e = {[Var = g1; 1 = g1; 2 = g2; 3 = g3] | (g1, g2, g3) ∈ e(Default)}

~GraphTermT1e = {[1 = g1; 2 = g2; 3 = g3] | (g1, g2, g3) ∈ e(Default)∧

g1 = GraphTerm}

~VarT2e = {[Var = g2; 1 = g1; 2 = g2; 3 = g3] | (g1, g2, g3) ∈ e(Default)}

~IriRefT2e = {[1 = g1; 2= g2; 3= g3] | (g1, g2, g3) ∈ e(Default)∧

g2 = IriRef}

~VarT3e = {[Var = g3; 1 = g1; 2 = g2; 3 = g3] | (g1, g2, g3) ∈ e(Default)}

~GraphTermT3e = {[1 = g1; 2 = g2; 3 = g3] | (g1, g2, g3) ∈ e(Default)∧

g3 = GraphTerm}

I termini della tripla T1, T2 e T3 sono valutati separatamente conside-rando la loro posizione. var(T1,T2,T3) è l’insieme di quei termini che sono

delle variabili. Viene fatta la giunzione tra le tre tabelle ottenute una per ogni termine e infine la proiezione sulle variabili della tripla. La notazione [1 = g1; 2 = g2; 3 = g3] sta ad indicare un record avente in posizione n il

Per esempio considerando il grafo 2.2 vogliamo valutare la semantica Tr sulla tripla {?x dc:creator ?nome}.

PREFIX dc: <http://purl.org/dc/elements/1.1/>

_:a dc:creator “Eric Miller”

_:a dc:year “2004-02-10”

_:b dc:creator “Patrick Hayes”

_:b dc:title “RDF Semantics”

_:c dc:year “2010-01-26”

Tabella 2.2: Un grafo RDF (3) ~?x dc:creator ?nomeTre =

πvar(?x, dc:creator, ?nome)(~?xT1e Z ~dc:creatorT2e Z ~?nomeT3e )

?x 1 2 3

_:a _:a dc:creator “Eric Miller”

_:a _:a dc:year “2004-02-10”

_:b _:b dc:creator “Patrick Hayes”

_:b _:b dc:title “RDF Semantics”

_:c _:c dc:year “2010-01-26”

Tabella 2.3: Valutazione della semantica T1 su ?x

1 2 3

_:a dc:creator “Eric Miller”

_:b dc:creator “Patrick Hayes”

Tabella 2.4: Valutazione della semantica T2 su dc:creator

Le tabelle 2.3-2.5 mostrano le tabelle risultanti dalla valutazione dei termini in base alla loro posizione all’interno della tripla. La Tabella 2.6 mostra il join tra queste tabelle su cui viene fatta la proiezione sulle variabili ?xe nome per ottenere la tabella finale.

Considerando invece un record della tabella di binding, la semantica Vgt applicata ad un termine che può essere una variabile o un GraphTerm e ad un record mappa il termine sul record rendendo il rispettivo valore.

?nome 1 2 3

“Eric Miller” _:a dc:creator “Eric Miller”

“2004-02-10” _:a dc:year “2004-02-10”

“Patrick Hayes” _:b dc:creator “Patrick Hayes”

“RDF Semantics” _:b dc:title “RDF Semantics”

“2010-01-26” _:c dc:year “2010-01-26”

Tabella 2.5: Valutazione della semantica T3 su ?nome

?x ?nome 1 2 3

_:a “Eric Miller” _:a dc:creator “Eric Miller”

_:b “Patrick Hayes” _:b dc:creator “Patrick Hayes”

Tabella 2.6: Join tra le tre tabelle precedenti

~_Vgt: VarOrGTerm → (Record → GraphTerm) ~gVgtt = t[g]

Per esempio considerando la tabella

?x ?nick

. . . .

alice “ali”

. . . .

se volessimo avere il valore della variabile ?nick nel record t (l’unico indicato) avremo

~?nickVgtt = “ali”

La Vgt applicata ad un termine del grafo rende il termine stesso: ~24Vgtt = 24

Per comprendere l’utilità di questo comportamento si rimanda alla semantica di un ValueC.

La semantica Vc applicata ad un ValueC ed un record, rende un booleano che indica se il record soddisfa la condizione ValueC.

~_Vc : ValueC → (Record → Bool) ~σ1OPσ2Vc_t = ~σ1Vgt_t OP ~σ2Vgt_t ~isIRI(σ)Vc_t = datatype(~σVgt_t )= IriRef

~isLiteral(σ)Vc_t = datatype(~σVgt_t )= RDFLiteral

~langMatches(σ1, σ2)Vc_t = langMatches(~σ1Vgt_t , ~σ2Vgt_t ) ~bound(σ)Vc_t = ~σVgt_t , NULL

~sameTerm(σ1, σ2)Vc_t = ~σ1Vgt_t = ~σ2Vgt_t ~isBlank(σ)Vc_t = datatype(~σVgt_t )= BNode

Gli operandi della condizione vengono valutati con la semantica Vgt. Per esempio se la condizione fosse (?age OP 24) la valutazione si tradur-rebbe in

~?ageVgtt OP ~24 Vgt t

la valutazione di ?age si tradurrebbe nel valore della variabile nel record t mentre la valutazione di 24 renderebbe il numero stesso.

Datatype è una funzione che data una variabile o un termine del grafo, rende il GraphTerm che rappresenta il tipo del suo valore. LangMatches è una funzione che dati due GraphTerm, rende true se essi sono due RDFLiteral con i tag di lingua, e tali tag sono uguali, false altrimenti.

datatype : Var → GraphTerm

langMatches : (GraphTerm × GraphTerm) → Bool

La Gp applicata ad un graph pattern GP e un ambiente rende una relazione.

~_Gp: GP → (Env → Rel) ~TripleGpe = ~TripleTre ~GP filter VCGpe = {t | t ∈ (~GP Gp e ∧ ~VCVct )} ~GP1and GP2Gpe = ~GP1Gpe Z ~GP2Gpe ~GP1unionGP_2Gp e = ~GP1Gpe ∪ ~GP2Gpe ~GP1optionalGP_2Gp e = ~GP1Gpe X ~GP2Gpe ~IriRef graph GPGpe = ~GP Gp

e(De f ault=e(IriRe f )]

~Var graph GPGpe = {[Var = IriRef] × ~GP Gp

e(De f ault=e(IriRe f )) | IriRef ∈ Dom(e)}

~{}Gpe = {}

La clausola FILTER in un graph pattern restinge la relazione ai record per cui la VC è vera.

La produzione GP1and GP2denota il basic graph pattern. La relazione

finale è data dalla giunzione delle relazioni ottenute valutando i singoli graph pattern.

Se nel graph pattern è presente la clausola OPTIONAL la relazione otte-nuta si tradurrà nella giunzione esterna delle due relazioni così definita: R1 X R2= (R1 Z R2) ∪ [(R1\πa1,...,an(R1 Z R2)) × {[b1= NULL, . . . , bm = NULL]}]

dove a1, . . . , an è lo schema della tabella R1 e b1, . . . , bm sono i campi di R2

che non fanno parte della giunzione.

La valutazione di un graph pattern su un grafo indicato da un rife-rimento (IriRef graph GP ) si traduce nell’esecuzione del graph pattern sull’ambiente in cui il grafo di default è il grafo riferito. Se invece un graph pattern viene valutato su un insieme di grafi, si valuta il graph pattern su tutti i grafi possibili e si fa una selezione per quelli che fanno parte dell’insieme. La funzione

Dom : Env → Graph permette di ottenere i nomi dei grafi dell’ambiente.

Un graph pattern vuoto rende una relazione vuota. ~_Wc: WhereClause → (Env → Rel) ~where GPWce = ~GP

Gp e

La Wc applicata ad una WhereClause e un ambiente rende una rela-zione ottenuta dalla valutarela-zione del GP sullo stesso ambiente.

Come detto la query ha sempre un grafo iniziale su cui viene eseguita (il grafo di default appunto) se non ci fosse nessuna clausola FROM o FROM NAMED. Una DatasetClause non vuota va a modificare questo ambiente: se contiene la clausola FROM esende il grafo di default, se invece contiene la FROM NAMEDestende l’ambiente aggiungendo i grafi con nome.

La Dc riceve quindi una DatasetClause e un ambiente e rende un altro ambiente.

~_Dce : DatasetClause → (Env → Env)

~Dce = []

~DatasetClause from IriRefDce = ~DatasetClauseDce +

[Default= ((~DatasetClauseDce (Default)) ∪ e(IriRef))]

~DatasetClause from named IriRefDce = ~DatasetClauseDce +

[IriRef= e(IriRef)]

Una DatasetClause vuota rende un insieme vuoto, non va quindi a modificare l’ambiente. Quando nella DatasetClause si incontra la clausola FROMseguita da un IriRef, il grafo Default viene cambiato. Una sequenza di DatasetClause con clausole FROM comporta l’unione di tutti i grafi riferiti.

La clausola FROM NAMED invece comporta la concatenazione tra il grafo con nome riferito e l’ambiente attuale.

La semantica di Sc applicata ad una SelectClause ed una relazione rende un’altra relazione.

~_Sc: SelectClause → (Rel → Rel)

~select Var1, . . . , VarnScr = {[t[Var1], . . . , t[Varn]] | t ∈ r}

~select ∗Scr = r

Se la SELECT è seguita da una lista delle variabili viene fatta la proie-zione su quelle variabili. Se invece è seguita dal simbolo “*” viene resa la relazione così com’è.

La semantica di Sq applicata ad una SelectQuery in un ambiente restituisce come risultato una tabella.

~_Sq : SelectQuery → (Env → Rel)

~SelectClause DatasetClause WhereClauseSqe =

let e1= ~DatasetClauseDce

let r= BlankRename (~WhereClauseWc_e1 ) return ~SelectClauseScr

Il let è il classico binder che assegna un valore ad una variabile. La Se-lectQuery è composta da tre clausole. La prima ad essere eseguita è la Da-tasetClause che rende l’ambiente in cui la query sarà eseguita. La Where-Clause restituisce la relazione r (tabella di binding) valutata sull’ambiente reso dalla DatasetClause. Infine su r viene valutata la SelectClause.

Definiamo con

BlankRename : Rel → Rel

la funzione biettiva che data una relazione r’ crea una nuova relazione r avente le stesse righe di r’ ma con dei blank nodes cosidetti “freschi”. Cioè per ogni blank node b ’ in r’ si genera un nuovo blank node b in r che viene sostituito ad ogni occorrenza di b ’ nelle righe di r. Applicata quindi alla tabella resa dalla WhereClause si elimina l’associazione tra i blank nodes che appaiono nel risultato e quelli presenti nel grafo.

La semantica di una singola tripla del template Ct applicata ad una tripla e un record rende un nuovo record senza variabili che apparterrà al grafo risultato.

~_Ct: Triple → (Record → (GraphTerm × GraphTerm × GraphTerm)) ~g1 g2 g3Ctt = ~g1Vgtt ~g2Vgtt ~g3Vgtt

Ogni termine della tripla viene valutato usando la semantica preceden-temente descritta Vgt e passandogli come parametro il record t.

La semantica Cc applicata ad una ConstructClause e una relazione rende un nuovo grafo.

~_Cc: ConstructClause → (Rel → Graph)

~construct Triple+Ccr = ( S t∈r S tp∈Triple+ ~tpCt t+[b1= f₁(t),...,bn= fn(t)] !)

dove b1, . . . , bn sono i blank nodes di Triple+ e f₁(t), . . . , fn(t) sono funzioni

iniettive (vedi sotto).

La ConstructClause viene eseguita valutando Triple+ una volta per ogni record t della relazione r. Per ogni tale record t si valutano tutte le triple tp del template. Se abbiamo k record in r, la tripla del template viene valutata k volte e nel caso in cui contenga dei blank nodes b1, . . . , bn tali

blank nodes devono essere sostituiti con k istanze separate per rispettare la semantica di SPARQL. A questo scopo il record t viene esteso con la sostituzione b1 = f₁(t), . . . , bn = fn(t) la quale ridenomina i nodi blank di tp

con i nodi blank f₁(t), . . . , fn(t) diversi per ogni record t. Formalmente le

funzioni f₁(t), . . . , fn(t)sono funzioni iniettive da blank nodes a blank nodes

che hanno range differenti e generano nodi blank “freschi” ovvero che non appaiano in altre parti del grafo o del risultato della query. Quindi f_i(t), dato un indice i (che indica il numero progressivo di un blank node nel template) e un record t, genera dei blank nodes diversi per ogni coppia < indice, record >:

f : (Int × Record) → BNode

Per esempio consideriamo la relazione r e il template mostrati di seguito:

?nome ?knows

“Alice” “Bob”

“Alice” “Maria”

“Maria” “Bob”

{ _:a foaf:name ?nome .

_:b foaf:name ?knows .

_:c rdf:type foaf:Group .

_:b foaf:member _:c }

I blank nodes presenti nel template sono tre. Un possibile grafo della funzione f è mostrata in Tabella 2.7.

XX XX XX XX XX XX t i _:a _:b _:c

“Alice” “Bob” _:d _:e _:f

“Alice” “Maria” _:g _:h _:i

“Maria” “Bob” _:l _:m _:n

Tabella 2.7: Applicazione della funzione f

Di seguito è mostrata la valutazione delle triple del template sul primo dei tre record.

~construct { _:a foaf:name ?nome . _:b foaf:name ?knows .

_:c rdf:type foaf:Group . _{_:b foaf:member _:c }}Cc_r =

~_:a foaf:name ?nomeCt_{[“Alice” “Bob”]}

+[_:a=_:d, _:b=_:e, _:c=_:f] S

~_:b foaf:name ?knowsCt_{[“Alice” “Bob”]}

+[_:a=_:d, _:b=_:e, _:c=_:f] S

~_:c rdf:type foaf:GroupCt

[“Alice” “Bob”]+[_:a=_:d,_:b=_:e,_:c=_:f]

~_:b foaf:member _:cCt_{[“Alice” “Bob”]}

+[_:a=_:d, _:b=_:e, _:c=_:f],

S

. . . } =

[_:d foaf:nome “Alice” . _:e foaf:nome “Bob” . _:f rdf:type foaf:Group . _:e foaf:member _:w

. . . ]

E così via per tutti gli altri record della relazione. Si noti che:

• ogni diversa valutazione del template produce nodi blank diversi • la seconda e la quarta tripla del risultato hanno lo stesso soggetto

(_:d in questo caso) proprio come la seconda e la quarta tripla del template

La semantica di Cq applicata ad una ConstructQuery ed un ambiente rende un grafo.

~_Cq: ConstructQuery → (Env → Graph)

~ConstructClause DatasetClause WhereClauseCqe =

let e1= ~DatasetClauseDc e

let r= BlankRename (~WhereClauseWc e1 )

return ~ConstructClauseCc r

Infine la semantica di Aq applicata ad una AskQuery e un ambiente rende un booleano che indica se il risultato è vuoto oppure no.

~_Aq : AskQuery → (Env → Bool)

~ask DatasetClause WhereClauseAqe = let e1 = ~DatasetClauseDce

let r= ~WhereClauseWc_e1 return r , ∅