$$%% examples \newcommand{\exGraph}{\graph_{\mathrm{ex}}} \newcommand{\exOnto}{\onto_{\mathrm{ex}}} \newcommand{\exMappings}{\mappings_{\mathrm{ex}}} \newcommand{\exExtensions}{\extensions_{\mathrm{ex}}} \newcommand{\exRule}{r_{\mathrm{ex}}} \newcommand{\RDFSrules}{\rules_{\mathrm{RDFS}}} %% RDF \newcommand{\triple}[3]{(#1, #2, #3)} \newcommand{\tuple}[1]{\langle #1 \rangle} \newcommand{\subject}{\mathtt{s}} \newcommand{\prop}{\mathtt{p}} \newcommand{\object}{\mathtt{o}} \newcommand{\blank}{\_{:}b} \newcommand{\blankn}[1]{\_{:}#1} \newcommand{\irin}[1]{{:}\mathrm{#1}} \newcommand{\class}{\mathtt{c}} \newcommand{\nsrdf}{\mathrm{rdf{:}}} \newcommand{\nsrdfs}{\mathrm{rdfs{:}}} \newcommand{\rdftype}{\mathrm{rdf{:}type}} \newcommand{\rdfLiteral}{\mathrm{rdf{:}Literal}} \newcommand{\rdfssubClassOf}{\mathrm{rdfs{:}subClassOf}} \newcommand{\rdfssubPropertyOf}{\mathrm{rdfs{:}subPropertyOf}} \newcommand{\rdfsdomain}{\mathrm{rdfs{:}domain}} \newcommand{\rdfsrange}{\mathrm{rdfs{:}range}} \newcommand{\rdfsClass}{\mathrm{rdfs{:}Class}} \newcommand{\rdfProperty}{\mathrm{rdf{:}Property}} \newcommand{\xsdint}{\mathrm{xsd{:}int}} %% \newcommand{\type}{\tau} \newcommand{\subclass}{\prec_{sc}} \newcommand{\subproperty}{\prec_{sp}} \newcommand{\domain}{\hookleftarrow_{d}} \newcommand{\range}{\hookrightarrow_{r}} \newcommand{\rdfentailment}{\vdash_{^\mathrm{RDF}}} \newcommand{\RDFS}[1]{\mathrm{RDFS}(#1)} \newcommand{\aka}{a.k.a.~} \newcommand{\etc}{etc} \newcommand{\wrt}{w.r.t.~} \newcommand{\st}{s.t.~} \newcommand{\ie}{i.e.,~} \newcommand{\eg}{e.g.,~} \newcommand{\graph}{G} \newcommand{\rules}{\mathcal{R}} \newcommand{\sources}{\mathcal{S}} \newcommand{\views}{\mathcal{V}} \newcommand{\extensions}{\mathcal{E}} \newcommand{\onto}{\mathcal{O}} \newcommand{\mappings}{\mathcal{M}} \newcommand{\modelsrdf}{\models_\rules} \newcommand{\bgp}{P} \newcommand{\Bl}[1]{\mathrm{Bl}(#1)} \newcommand{\Val}[1]{\mathrm{Val}(#1)} \newcommand{\Var}[1]{\mathrm{Var(#1)}} \newcommand{\ext}[1]{\mathrm{ext}(#1)} \newcommand{\cert}{\mathrm{cert}} \newcommand{\ans}{\mathrm{ans}} \newcommand{\query}{\leftarrow} \newcommand{\body}[1]{\textrm{body}(#1)} \newcommand{\head}[1]{\textrm{head}(#1)} \newcommand{\cs}{\mathrm{cs}} \newcommand{\lcs}{\mathrm{lcs}} \newcommand{\cl}{\mathrm{cl}} \newcommand{\lua}{\mathrm{lua}} \newcommand{\lur}{\mathrm{lur}} \newtheorem{lemma}{Lemma} \newtheorem{definition}{Definition} \newtheorem{problem}{Problem} \newtheorem{property}{Property} \newtheorem{corollary}{Corollary} \newtheorem{example}{Example} \newtheorem{theorem}{Theorem} \newcommand{\URIs}{\mathscr U} \newcommand{\IRIs}{\mathscr I} \newcommand{\BNodes}{\mathscr B} \newcommand{\Literals}{\mathscr L} \newcommand{\Variables}{\mathscr V} % DB \newcommand{\CQ}{\ensuremath{\mathtt{CQ}}\xspace} \newcommand{\UCQ}{\ensuremath{\mathtt{UCQ}}\xspace} \newcommand{\SQL}{\ensuremath{\mathtt{SQL}}\xspace} \newcommand{\rel}[1]{\mathsf{#1}} % Cost model \newcommand{\cans}[1]{|#1|_t} \newcommand{\cref}[1]{|#1|_r} \newcommand{\db}{\mathtt{db}} % DL \newcommand{\cn}{\ensuremath{N_{C}}\xspace} \newcommand{\rn}{\ensuremath{N_{R}}\xspace} \newcommand{\inds}{\ensuremath{N_{I}}\xspace} \newcommand{\ainds}{\ensuremath{\mathrm{Ind}}\xspace} \newcommand{\funct}{\mathit{funct} \ } \newcommand{\KB}{\mathcal{K}\xspace} \newcommand{\dlr}{DL-Lite$_{\mathcal{R}}$\xspace} % Logics \newcommand{\FOL}{\ensuremath{\mathtt{FOL}}\xspace} \newcommand{\datalog}{\ensuremath{\mathtt{Datalog}}\xspace} \newcommand{\dllite}{DL-Lite\xspace} \newcommand{\true}{\mathrm{true}} \newcommand{\false}{\mathrm{false}} \newcommand{\dis}{\mathtt{dis}} \newcommand{\vars}[1]{\ensuremath{\mathrm{vars}(#1)}} %\newcommand{\terms}[1]{\ensuremath{\mathrm{terms}(#1)}} %math \renewcommand{\phi}{\varphi} \newcommand\eqdef{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}} \newcommand\restr[2]{#1_{|#2}} \newcommand{\ontoBody}[1]{\mathrm{body}_\onto(#1)} %proof of the rewriting theorem \newcommand{\rdfGraph}{\graph^{\mappings}_{\extensions}} \newcommand\systemGraph{\graph^{\mappings \cup \mappings^{\text{STD}}_\onto}_{\extensions \cup \extensions_\onto}} \newcommand\viewsGraph{\graph^{\mappings^{\rules,\onto} \cup \mappings^{\text{STD}}_\onto}_{\extensions \cup \extensions_\onto}} \newcommand{\standMappings}{\mappings^{\text{STD}}_\onto} \newcommand{\reminder}[1]{[\vadjust{\vbox to0pt{\vss\hbox to0pt{\hss{\Large $\Longrightarrow$}}}}{{\textsf{\small #1}}}]} %\newcommand{\FG}[1]{\textcolor{blue}{\reminder{FG:~#1}}} \newcommand{\extVersion}{false} \newcommand{\printIfExtVersion}[2] { \ifthenelse{\equal{\extVersion}{true}}{#1}{} \ifthenelse{\equal{\extVersion}{false}}{#2}{} } \newcommand{\bda}{\true} \newcommand{\ifBDA}[2]% {% \ifthenelse{\equal{\bda}{true}}{#1}{}% \ifthenelse{\equal{\bda}{false}}{#2}{}% } %%% Local Variables: %%% TeX-master: "paper" %%% End: $$

Schema Implementation

Schema Implementation Definition

The schema implementation stores RDF triples about the schema of an RDF graph using text encoding for RDF terms:

  • a set of classes
  • a set of properties
  • a map linking c class to the set of all subclasses of c
  • a map linking each p property to the set of all subproperty of p
  • a map linking each c class to properties having the given class as domain
  • a map linking each c class to properties having the given class as range

and it implements methods allowing any request on the RDFS schema as it is stored. We don't want that the schema implements any kind of reasoning.

Information stored in a schema are equivalent to a set of RDF triples containing exactly the following triples:

  • \(\triple{c}{\type}{\rdfsClass}\) for \(c\) into the set of classes
  • \(\triple{p}{\type}{\rdfProperty}\) for \(p\) into the set of properties
  • \(\triple{c_{1}}{\subclass}{c}\) for each \(c_{1}\) subclass of \(c\)
  • \(\triple{p_{1}}{\subclass}{p}\) for each \(p_{1}\) subproperty of \(p\)
  • \(\triple{p}{\domain}{c}\) for each \(c\) domain of \(p\)
  • \(\triple{p}{\range}{c}\) for each \(c\) range of \(p\)

Defining the semantic of schema object as a set of triples allows us to talk about its saturation according to RDF entailment rules. We also expect that every methods on schema implements the evaluation of simple conjunctive query on the set of triples that it contains.

Schema Extractor

A schema extractor extracts the schema from a triples store, containing the RDF graph \(\graph\). Each extractor takes as input:

  • an access to \(G\),
  • a Boolean RDFSTriplesOnly.

The extracted schema of \(\graph\) denoted \(\mathrm{ES}(\graph)\) is build as follow:

  1. if RDFSTriplesOnly is false (default), then it contains triples of form \(\triple{\subject}{\type}{\rdfProperty}\) and \(\triple{\subject}{\type}{\rdfsClass}\) of \(\graph\).
  2. it contains all triples with an RDFS property of \(\graph\).

Saturations

In this section, we describe some RDF entailment rule set to saturated the schema of an RDF graph.

RDFS Schema Entailment Rules

The RDFS schema entailement rules are:

Rule Entailment Rule
rdfs5 \(\triple{\prop_1}{\subproperty}{\prop_2},\triple{\prop_2}{\subproperty}{\prop_3} \rightarrow \triple{\prop_1}{\subproperty}{\prop_3}\)
rdfs11 \(\triple{\subject}{\subclass}{\object},\triple{\object}{\subclass}{\object_1} \rightarrow \triple{\subject}{\subclass}{\object_1}\)
ext1 \(\triple{\prop}{\domain}{\object},\triple{\object}{\subclass}{\object_1} \rightarrow \triple{\prop}{\domain}{\object_1}\)
ext2 \(\triple{\prop}{\range}{\object},\triple{\object}{\subclass}{\object_1} \rightarrow \triple{\prop}{\range}{\object_1}\)
ext3 \(\triple{\prop}{\subproperty}{\prop_1},\triple{\prop_1}{\domain}{\object} \rightarrow \triple{\prop}{\domain}{\object}\)
ext4 \(\triple{\prop}{\subproperty}{\prop_1},\triple{\prop_1}{\range}{\object} \rightarrow \triple{\prop}{\range}{\object}\)

Class and Property Definitions Entailment Rules

The class and property definitions entailment rules are:

Entailment Rule For Class Definition
\(\triple{p}{\subclass}{q} \rightarrow \triple{p}{\type}{\rdfsClass}\)
\(\triple{p}{\subclass}{q} \rightarrow \triple{q}{\type}{\rdfsClass}\)
\(\triple{p}{\domain}{c} \rightarrow \triple{c}{\type}{\rdfsClass}\)
\(\triple{p}{\range}{c} \rightarrow \triple{c}{\type}{\rdfsClass}\)
Entailment Rule For Property Definition
\(\triple{p}{\subproperty}{q} \rightarrow \triple{p}{\type}{\rdfProperty}\)
\(\triple{p}{\subproperty}{q} \rightarrow \triple{q}{\type}{\rdfProperty}\)
\(\triple{p}{\domain}{c} \rightarrow \triple{p}{\type}{\rdfProperty}\)
\(\triple{p}{\range}{c} \rightarrow \triple{p}{\type}{\rdfProperty}\)

Reflexive Relation Schema Entailment Rules

The reflexive relation schema entailment rules are:

Rule Entailment Rule
rdfs6 \(\triple{\prop}{\type}{\rdfProperty} \rightarrow \triple{\prop}{\subproperty}{\prop}\)
rdfs10 \(\triple{\class}{\type}{\rdfsClass} \rightarrow \triple{\class}{\subclass}{\class}\)

Alternatively, Alexandra have proposed some entailment rules to handle the reflexivity of sub class and sub property relations in GoasdoueBGPQueryAnswering2012 Figure 6 and 7. Their rules don't use \(\rdfProperty\) and \(\rdfsClass\), but wrap the Class and Property definition entailment rules with two above rules. In the paper, a "schema-level of a graph" is only triples that an RDFS property. Figure 6 presents reflexivity entailment from schema-level, this entailment is also supported by the rules we previously introduce. But, we have to add some entailment rules to allow entailment from instance-level triple to schema-level triple presented in Figure 7.

I want to introduce here a new definition for specific schema. We first define reserved IRIs as: \(\subclass, \subproperty, \domain, \range, \type, \rdfProperty,\rdfsClass\).

A FO schema is a RDF graph where triples have the one of following form :

  • \(\triple{\subject}{\prop}{\object}\) where \(\prop\) is a RDFS property, and also \(\subject\) and \(\object\) are not reserved IRIs.
  • \(\triple{\subject}{\type}{\rdfProperty}\) where \(\subject\) is not a reserved IRI.
  • \(\triple{\subject}{\type}{\rdfsClass}\) where \(\subject\) is not a reserved IRI.

A property of the union of reflexive relation schema, class and property definition and RDFS schema entailment rule set is that saturation of FO schema is still an FO schema.

Generic Class and Property Definitions Entailment Rules

The two following entailment rules will be used to entail new schema triples from instance and schema triples.

Rule Entailment Rule
rdfD2 \(\triple{\subject}{\prop}{\object} \rightarrow \triple{\prop}{\type}{\rdfProperty}\)
  \(\triple{\subject}{\type}{\class} \rightarrow \triple{\class}{\type}{\rdfsClass}\)

Funny entailments will appear, since we use all introduced rules together: \(\triple{\subject}{\type}{\class}\) entails \(\triple{\type}{\type}{\rdfProperty}\) entails \(\triple{\type}{\subproperty}{\type}\) entails \(\triple{\subproperty}{\type}{\rdfProperty}\) entails \(\triple{\subproperty}{\subproperty}{\subproperty}\). But none of this entailments seem to raise a problem, because it seems not possible to use one of this no FO triple with an instance (assertions) entailment rule to generate a schema triple that is not already entailed by some of the previous schema entailment rules. In other words, the following lemma, adapted from extended version of ESWC paper, holds:

For all RDF graph \(\graph\) with a FO schema, it holds that: \[\graph^{\rules_a \cup \rules_s} = \left ( \graph^{\rules_a} \right ) ^{\rules_s}\] where \(\rules_{a}\) is the standard RDF entailment rule for assertions triples and \(\rules_{s}\) is a set of RDF entailment rules for schema triple (defined above).