The Logic of theSemantic WebEnrico FranconiFree University of Bozen-Bolzano, ItalyThe Logic of the Semantic Web - Enrico FranconiWhat is this talk about2The Logic of the Semantic Web - Enrico FranconiWhat is this talk aboutA sort of tutorial of RDF, the core semantic web knowledge representation language (data model)Emphasises the logical aspect......necessary to introduce in this context constraints, e.g., (conceptual) schemas, ontologies, etcMost material taken from my PODS-06 invited talk2The Logic of the Semantic Web - Enrico FranconiTechnical ContentRDF as a novel KR languagewith meta-modelling capabilities with challenging theoretical problemsSPARQL as the RDF query languagea query language for incomplete informationwith interesting capabilitiesI’ll present an abstract logic-based frameworkDISCLAIMER:the field is very youngthe current main effort is about clarifying issues3The Logic of the Semantic Web - Enrico FranconiSummary4The Logic of the Semantic Web - Enrico FranconiSummaryRDF as a KR language4The Logic of the Semantic Web - Enrico FranconiSummaryRDF as a KR languageThe semantics of RDF4The Logic of the Semantic Web - Enrico FranconiSummaryRDF as a KR languageThe semantics of RDFRDF as a representation system for incomplete information: naive tables and conjunctive queries4The Logic of the Semantic Web - Enrico FranconiSummaryRDF as a KR languageThe semantics of RDFRDF as a representation system for incomplete information: naive tables and conjunctive queriesRDF with constraints: RDFS4The Logic of the Semantic Web - Enrico FranconiSummaryRDF as a KR languageThe semantics of RDFRDF as a representation system for incomplete information: naive tables and conjunctive queriesRDF with constraints: RDFSQuerying RDF incomplete databases4The Logic of the Semantic Web - Enrico FranconiSummaryRDF as a KR languageThe semantics of RDFRDF as a representation system for incomplete information: naive tables and conjunctive queriesRDF with constraints: RDFSQuerying RDF incomplete databasesSPARQL as the query language for RDF4The Logic of the Semantic Web - Enrico FranconiRDF in the real worldRDF and SPARQL are W3C standardsWidespread use for metadata representation, e.g.Apple (MCF)Adobe (XMP)Mozilla/FirefoxOracle supports RDF, and provides an extension of SQL to query RDF dataHP has a big lab (in Bristol) developing specialised data stores for RDF (Jena)...but: research is beyond practice5The Logic of the Semantic Web - Enrico FranconiA node- and edge-labelled directed graphedges are called propertiesthe left node in a directed edge is called subjectthe right node in a directed edge is called objectTypical notations are:p(s,o)Triple(s, p, o)s p o.Labels are URIs, literals, or bnodesRDF6The Logic of the Semantic Web - Enrico FranconiExample7:john29:agerdf:type:rock-band 32:average-agerdf:type:anthony:agerdf:type:age:has-max37:leads:antony :leads :john.:antony :age _:a.:antony rdf:type _:b._:b rdf:type :rock-band.:age :has-max 37....The Logic of the Semantic Web - Enrico FranconiExample7:john29:agerdf:type:rock-band 32:average-agerdf:type:anthony:agerdf:type:age:has-max37:leads:antony :leads :john.:antony :age _:a.:antony rdf:type _:b._:b rdf:type :rock-band.:age :has-max 37....The Logic of the Semantic Web - Enrico FranconiSome labels are anonymous: bnodesThe alphabets of labels for nodes and for properties are not disjoint: a coreference is possible between nodes and propertiesThere is a special pre-defined non well-founded “rdf:type” property, with the intended meaning of “is-element-of”RDF peculiarities8The Logic of the Semantic Web - Enrico FranconiWe want to provide a model-theoretic semantics to RDF graphs, in order to properly define entailment and query answeringWe consider here a simplified RDF language:no restrictions on literalsin normative RDF literals are not allowed in subject positionno restrictions on propertiesin normative RDF bnodes are not allowed in property positionno “axiomatic” knowledgeMeaning of RDF graphs9The Logic of the Semantic Web - Enrico FranconiRDF semantics (atoms)I = !∆I, ·I, ·Ip"10·I: U ∪ L "→ ∆I·Ip: ∆I"→ 2∆I×∆Iα : B "→ ∆IThe Logic of the Semantic Web - Enrico FranconiRDF semantics (atoms)I = !∆I, ·I, ·Ip"uI,α= uIlI,α= lIbI,α= α(b)10·I: U ∪ L "→ ∆I·Ip: ∆I"→ 2∆I×∆Iα : B "→ ∆IThe Logic of the Semantic Web - Enrico FranconiRDF semantics (atoms)I = !∆I, ·I, ·Ip"uI,α= uIlI,α= lIbI,α= α(b)I, α |= p(s, o) iff !sI,α, oI,α" ∈ (pI,α)Ip10·I: U ∪ L "→ ∆I·Ip: ∆I"→ 2∆I×∆Iα : B "→ ∆IThe Logic of the Semantic Web - Enrico FranconiRDF semantics (atoms)I = !∆I, ·I, ·Ip"uI,α= uIlI,α= lIbI,α= α(b)I, α |= p(s, o) iff !sI,α, oI,α" ∈ (pI,α)Ip10·I: U ∪ L "→ ∆I·Ip: ∆I"→ 2∆I×∆Iα : B "→ ∆II, α |= p(s, o) iff !sI,α, oI,α" ∈ pIp,α(FOL)The Logic of the Semantic Web - Enrico FranconiRDF semantics (atoms)I = !∆I, ·I, ·Ip"uI,α= uIlI,α= lIbI,α= α(b)I, α |= p(s, o) iff !sI,α, oI,α" ∈ (pI,α)IpI, α |= p(s, o) iff !sI,α, pI,α, oI,α" ∈ TI10·I: U ∪ L "→ ∆I·Ip: ∆I"→ 2∆I×∆Iα : B "→ ∆IThe Logic of the Semantic Web - Enrico FranconiRDF semantics and entailment is a model of an RDF graph G, written , if there exists an such thatAn RDF graph G entails an RDF graph H ( )iff for any such that then 11I, α |= {p1(s1, o1), p2(s2, o2), · · · } iffI, α |= p1(s1, o1) andI, α |= {p2(s2, o2), · · · }I, α |= GII |= GαI |= HI |= GIG |= HNon-atomic formulas:The Logic of the Semantic Web - Enrico FranconiExample12:john29:agerdf:type:rock-band 32:average-m’-agerdf:type:anthony:agerdf:type:leads|=:anthony:leads29:ageThe Logic of the Semantic Web - Enrico Franconi[_, Tessaris, 2004] The models of an RDF graphare the same as the models of the FOL formulawhere is the set of bnode names appearing in the graphI |= {p1(s1, o1), p2(s2, o2), · · · }I |=FOL∃¯b. T (s1, p1, o1) ∧ T (s2, p2, o2) ∧ · · ·¯bRDF and FOL13The Logic of the Semantic Web - Enrico FranconiExample14:john29:agerdf:type:rock-band 32:average-m’-agerdf:type:anthony:agerdf:type:leads󲰞x,y. T(:antony, :leads, :john) 󲰙 T(:antony, :age, x) 󲰙 T(:antony, rdf:type, y) 󲰙 T(y, rdf:type :rock-band) 󲰙 ...The Logic of the Semantic Web - Enrico FranconiComplexity of RDF entailmentNP-complete in the size of the graphsPolynomial in the size of the entailing graph GAlgorithm: