A.1SintassiSPARQL AppendiceA

(1)

Appendice A

A.1 Sintassi SPARQL

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 .

(2)

APPENDICE A. SINTASSI E SEMANTICA DI SPARQL 68 ValueC ::= Var Op VarOrGTerm | isIRI(Var) | isLiteral(Var)

Op ::= > | < | ≥ | ≤

GraphTerm ::= IriRef | RDFLiteral | BNode Var ::= ’?’Varname | ’$’Varname VarOrGTerm ::= Var | GraphTerm

VarOrIri ::= Var | IriRef

A.2 Semantica SPARQL

Env : IriRefSet → Graph

Record : VarOrBNode → GraphTerm Rel= Set(Record) t[g]=        g1 se t= [. . . , g = g1, . . .] g altrimenti

dove t è un record e g un termine del grafo.

~_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}

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

(3)

APPENDICE A. SINTASSI E SEMANTICA DI SPARQL 69

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

g3 = GraphTerm}

~_Vgt : VarOrGTerm → (Record → GraphTerm)

~gVgtt = t[g]

~_Vc : ValueC → (Record → Bool)

~σ1OPσ2Vct = ~σ1 Vgt t OP ~σ2 Vgt t ~isIRI(σ)Vct = datatype(~σ Vgt t )= IriRef ~isLiteral(σ)Vct = datatype(~σ Vgt t )= RDFLiteral ~langMatches(σ1, σ2)Vc_t = langMatches(~σ1Vgtt , ~σ2 Vgt t ) ~bound(σ)Vct = ~σ Vgt t , NULL ~sameTerm(σ1, σ2)Vc_t = ~σ1Vgtt = ~σ2 Vgt t ~isBlank(σ)Vct = datatype(~σ Vgt t )= BNode

datatype : Var → GraphTerm

langMatches : (GraphTerm × GraphTerm) → Bool

~_Gp: GP → (Env → Rel) ~TripleGpe = ~TripleTre ~GP filter VCGpe = {t | t ∈ (~GP Gp e ∧ ~VCVct )} ~GP1and GP2Gpe = ~GP1Gpe Z ~GP2Gpe ~GP1unionGP2Gpe = ~GP1Gpe ∪ ~GP2Gpe ~GP1optionalGP2Gpe = ~GP1Gpe X ~GP2Gpe ~IriRef graph GPGpe = ~GP Gp e[De f ault=e(IriRe f )] ~Var graph GPGpe =

(4)

~{}Gpe = {}

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.

~_Wc := WhereClause → (Env → Rel) ~where GPWce = ~GP

Gp e

~_Dce : DatasetClause → (Env → Env)

~Dce = []

~DatasetClause from IriRefDce = ~DatasetClauseDce +

[Default= ((~DatasetClauseDc

e (Default)) ∪ e(IriRef))]

~DatasetClause from named IriRefDce = ~DatasetClauseDce +

[IriRef= e(IriRef)]

~_Sc : SelectClause → (Rel → Rel)

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

~select ∗Scr = r

~_Sq : SelectQuery → (Env → Rel)

~SelectClause DatasetClause WhereClauseSqe =

let e1= ~DatasetClauseDc e

let r= BlankRename (~WhereClauseWc e1 )

return ~SelectClauseSc r

(5)

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.

~_Ct : Triple → (Record → (GraphTerm × GraphTerm × GraphTerm) )

~g1 g2 g3Ctt = ~g1Vgtt ~g2Vgtt ~g3Vgtt

~_Cc : ConstructClause → (Rel → Graph)

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

f : (Int × Record) → BNode

La funzione iniettiva f dato un indice e un record genera dei blank nodes diversi per ogni coppia< indice, record >.

~_Cq : ConstructQuery → (Env → Graph)

~ConstructClause DatasetClause WhereClauseCqe =

let e1= ~DatasetClauseDc e

let r= BlankRename (~WhereClauseWc e1 )

return ~ConstructClauseCc r

(6)

~_Aq : AskQuery → (Env → Bool)

~ask DatasetClause WhereClauseAqe = let e1 = ~DatasetClauseDce

let r = ~WhereClauseWc e1

(7)

Appendice B

B.1 Definizione dei tipi

TypeTN ::= T_IRI | T_RDFLiteral | T_BNode | T_NULL | {IriRef} | {lit}

| _nameOf(TG) | _{TN ∪ TN} | _{TN ∩ TN}

TypeTG ::= TN T_IRI TN | TN IriRef TN | | _{TG ∪ TG} Type TR ::= [Var : TN] | _{TR ∪ TR} | _{TR and TR} | _{TR opt TR} | _[] TypeNG ::= | NG, IriRef : TG

B.2 Semantica dei tipi

~_tn: TN → (Env → P{GraphTerm}) ~T_IRItne = IRIREF

~T_RDFLiteraltne = RDFLiteral

~T_BNodetne = BNode

(8)

APPENDICE B. IL SISTEMA DI TIPI 74

~T_NULLtne = {null}

~{lit}tbe = {lit}

~{IriRef}tbe = {IriRef}

~nameOf(TG)tne = {IriRef | e(IriRef) ∈ ~TG tg e } ~TN1∪ TN2tne = ~TN1tne ∪ ~TN2tne ~TN1∩ TN2tne = ~TN1tne ∩ ~TN2tne ~_tg: TG → (Env → P{Graph}) ~tge = ∅ ~TN1T_IRI TN2tge = P(G | G ⊆ ~TN1tne × IRIREF × ~TN2tne ) ~TN1IriRef TN2tge = P(G | G ⊆ ~TN1tne × {IriRef} × ~TN2tne ) ~TG1∪ TG2tge = ~TG1tge ∪ ~TG2tge ~_tr: TR → (Env → P{Rel})

~[Var : TN]tre = P([Var = nodo] | nodo ∈ ~TNtne )

~TR1∪ TR2tre = ~TR1tre ∪+~TR2tre ~TR1 andTR₂tr e = ~TR1tre Z ~TR2tre ~TR1 optTR₂tr e = ~TR1tre X ~TR2tre ~[]tre = {[]}

Date due relazioni r1e r2, definiamo:

• r1 Z r2come la classica giunzione tra tabelle

• r1 X r2il join esterno definito come: (r1 Z r2)∪(r1×{c1, . . . , cn} → null)

dove {c1, . . . , cn} sono i campi di r2 non presenti in r1

• r1∪+r2come l’unione tra due relazioni con schema diverso ottenuta

aggiungendo colonne di valori nulli nelle tabelle al fine di rendere omogenei gli schemi e quindi poter eseguire l’unione relazionale Dati due insiemi di relazioni R1e R2, definiamo:

(9)

APPENDICE B. IL SISTEMA DI TIPI 75 • R1 Z R2 = {r1 Z r2| r1 ∈ R1, r2 ∈ R2} • R1 X R2 = {r1 X r2| r1 ∈ R1, r2 ∈ R2} • R1∪+R2 = {r1∪+r2| r1 ∈ R1, r2 ∈ R2} ~_ng : NG → (Env → P{Env}) ~nge = {∅}

~IriRef : nameOf(TG), NGnge = {[IriRef = G | G ∈ ~TG tg e } × ~NG ng e ~NG,TGngtge = ~NG ng e × {[Default= G] | G ∈ ~TG tg e }

Dove ∪+ è l’unione esterna in cui si fa l’unione di due relazioni con stesso schema oppure con schema differente (si rendono gli schemi uguali aggiungendo colonne con valori nulli nelle tabelle).

B.3 Giudizi

NG,TG `Sq _{SelectQuery : TR} NG,TG `Cq_{ConstructQuery : TG} NG,TG `Aq _{AskQuery : Bool} NG,TG `Dc _{DatasetClause : NG’,TG’} NG,TG `Wc WhereClause : TR NG,TG `Gp GP : TR TR `Sc _{SelectClause : TR} 1 TR `Ct _{ConstructTemplate : TG’} TR `Vgt _{VarOrGTerm : TN} TR `Vc _{ValueC : Bool}

(10)

APPENDICE B. IL SISTEMA DI TIPI 76

B.4 Regole

(TypeSelectQuery) NG,TG `Dc DatasetClause : NG’,TG’ NG’,TG’ `WcWhereClause : TR TR `ScSelectClause : TR’

NG,TG `Sq _{SelectClause DatasetClause WhereClause : TR’}

(TypeSelectClause)

TR ` Var1 : TN1, . . . , Varn : TNn

TR `ScselectVar

1, . . . , Varn: [Var1: TN1, . . . , Varn : TNn]

(TypeSelectClauseAll) TR `Sc_select_{* : TR} (TypeConstructQuery) NG,TG `Dc _{DatasetClause : NG’,TG’} NG’,TG’ `Wc_{WhereClause : TR} TR `Ct _{ConstructTemplate : TG’}

NG,TG `Cq _{ConstructTemplate DatasetClause WhereClause : TG’}

(TypeConstructTemplate) TR `Ct_{Triple : TG} 1 TR `Ct Triple+ : TG2 TR `Ct _Triple_{. Triple+ : TG} 1∪ TG2 (TypeConstructTemplateBase) TR `Vgt g1 : TN1 TR `Vgt g2: TN2

TR `VgtVarOrIri : {IriRef1} ∪. . . ∪ {IriRefn}

TR `Ct _g

(11)

APPENDICE B. IL SISTEMA DI TIPI 77 (TypeAskQuery)

NG,TG `Dc DatasetClause : NG’,TG’ NG’,TG’ `Wc WhereClause : TR

NG,TG `Aq _ask_{DatasetClause WhereClause : Bool}

(TypeFrom)

NG,TG ∪ TG1`Dc DatasetClause : NG’,TG’

NG,TG `Dc _{DatasetClause from (IriRef : nameOf(TG}

1)) : NG’,TG’

(TypeFromNamed)

(NG,IriRef:nameOf(TG1)),TG `Dc DatasetClause : NG’,TG’

NG,TG `Dc _{DatasetClause from named (IriRef : nameOf(TG}

1)) : NG’,TG’ (TypeFromEmpty) NG,TG `Dc : NG,TG (TypeWhere) NG,TG `Gp GP : TR NG,TG `Dc _where_{GP : TR} (TypeTriple1) S= {TN1 | (TN1p TN2) ∈ TG ∧ (TN ∩∗TN2)} S , ∅ o : TN NG,TG `Tr _{Var p o : [Var : ∪} {_TN₁∈_S}TN₁] (TypeTriple2) W= {TN2 | (TN1p TN2) ∈ TG ∧ (TN ∩ ∗ TN1)} W , ∅ s : TN NG,TG `Tr _{s p Var : [Var : ∪} {_TN₂∈_W}TN₂]

(12)

APPENDICE B. IL SISTEMA DI TIPI 78 (TypeGpAnd) NG,TG `Gp GP1 : TR1 NG,TG `GpGP2 : TR2 NG,TG `Gp_GP 1and GP2 : TR1 and TR2 (TypeGpOpt) NG,TG `Gp _GP 1 : TR1 NG,TG `GpGP2 : TR2 NG,TG `Gp _GP 1optGP₂: TR₁opt TR₂ (TypeGpUnion) NG,TG `Gp _GP 1 : TR1 NG,TG `GpGP2 : TR2 NG,TG `Gp GP1unionGP2 : TR1∪ TR2 (TypeGpFilter) NG,TG `Gp _{GP : TR} _{TR `}Gp _{VC : Bool} NG,TG `GpGP filter VC : TR (TypeGpGraph)

NG, ∪{_{IriRe f ∈Dom(NG)}} NG[IriRef] ` GP : TR

NG,TG `Gp Var graph_{GP : [Var : Dom(NG)] and TR}

(TypeGpIriGraph ) IriRef : nameOf(TG1) ∈ NG NG, TG1`GpGP : TR NG,TG `Gp_{IriRef graph GP : TR} (TypeGpEmpty) NG,TG `Gp _{{} : {}} (TypeVC) TR `Vgt_{Var : TN} 1 TR `VgtVarOrGTerm : TN2

(13)

APPENDICE B. IL SISTEMA DI TIPI 79 (TypeVCisIri) TR `VgtVar : TN TR `Vc_{isIRI(Var) : Bool} (TypeVCisLiteral) TR `Vgt_{Var : TN} TR `Vc_{isLiteral(Var) : Bool} (TypeVCisBlank) TR `Vgt_{Var : TN} TR `VcisBlank(Var) : Bool (TypeVClangMatches) TR `Vgt_Var 1 : TN TR `VgtVar2 : TN

TR `VclangMatches(Var₁,Var2) : Bool

(TypeVCbound) TR `Vgt_{Var : TN} TR `Vcbound(Var) : Bool (TypeVCsameTerm) TR `Vgt_Var 1 : TN TR `VgtVar2: TN TR `Vc _sameTerm(Var 1,Var)2 : Bool (TypeNotVC) TR `Vc_{VC : Bool} TR `Vc_{¬VC : Bool} (TypeVCand) TR `Vc_VC 1 : Bool TR `Vc VC2: Bool TR `Vc_VC 1∧ VC2: Bool

(14)

APPENDICE B. IL SISTEMA DI TIPI 80 (TypeVCor) TR `VcVC1 : Bool TR `Vc VC2: Bool TR `Vc_VC 1∨ VC2: Bool (VarOrGTermVar) TR `Tr Var : TN TR `Vgt_{Var : TN} (VarOrGTermIri) TR `VgtIriRef : {IriRef} (VarOrGTermBnode) TR `Vgtbn : T_BNode (VarOrGTermLiteral) TR `Vgtlit : T_RDFLiteral[lit] (TypeAnd) TR1` Var : TN1 TR2` Var : TN2 TR1and TR2 ` Var : TN1∩ TN2 (TypeAnd1)

TR1` Var : TN1 Var < VarSet(TN2)

TR1and TR2 ` Var : TN1

(TypeAnd2)

TR2` Var : TN2 Var < VarSet(TN1)

(15)

APPENDICE B. IL SISTEMA DI TIPI 81 (TypeOpt)

TR1` Var : TN1 TR2` Var : TN2

TR1 opt TR2 ` Var : TN1

(TypeOpt1)

TR1` Var : TN1 Var < VarSet(TR2)

TR1opt TR2` Var : TN1

(TypeOpt2)

TR1opt TR2 ` Var : TN2∪ T_NULL

(TypeUnion)

TR1` Var : TN1 TR2` Var : TN2

TR1∪ TR2` Var : TN1∪ TN2

(TypeUnion1)

TR1∪ TR2 ` Var : TN1∪ T_NULL

(TypeUnion2)

TR1∪ TR2 ` Var : TN2∪ T_NULL

B.5 Proprietà

NG,TG `Sq SelectQuery : TR ⇒ ∀_{e ∀e1 ∈ ~NG,TG}ngtg e . ~SelectQuery Sq e1 ∈ ~TR tr e1 TR `Sq SelectClause : TR1 ⇒ ∀_{e ∀r ∈ ~TR}tr e . ~SelectClauseScr ∈ ~TR1tre

(16)

APPENDICE B. IL SISTEMA DI TIPI 82 NG,TG `Cq_{ConstructQuery : TG ⇒} ∀_{e ∀e1 ∈ ~NG,TG}ngtg e . ~ConstructQuery Cq e1 ∈ ~TG tg e1 TR `Ct _{ConstructTemplate : TG ⇒} ∀_{e ∀t ∈ ~TR}tr e . ~ConstructTemplateCtt ∈ ~TG tg e TR `Vgt_{VarOrGTerm : TN ⇒} ∀_{e ∀t ∈ ~TR}tr e . ~VarOrGTerm Vgt t ∈ ~TNtne NG,TG `Aq _{AskQuery : Bool ⇒} ∀_{e ∀e1 ∈ ~NG,TG}ngtg e . ~AskQuery Aq e1 ∈ ~Boole NG,TG `Dc _{DatasetClause : NG’,TG’ ⇒} ∀_{e ∀e1 ∈ ~NG,TG}ngtg e . ~DatasetClauseDc_e1 ∈ ~NG’,TG’ ngtg e1 NG,TG `Wc_{WhereClause : TR ⇒} ∀_{e ∀e1 ∈ ~NG,TG}ngtg e . ~WhereClauseWc_e1 ∈ ~TRtr_e1 NG,TG `Gp_{GP : TR ⇒} ∀_{e ∀e1 ∈ ~NG,TG}ngtg e . ~GP Gp e1 ∈ ~TR tr e1 TR `Vc _{ValueC : Bool ⇒} ∀_{e ∀t ∈ ~TR}tr e . ~ValueCVct ∈ ~Boole