$$%% 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: $$

Query Answering Methods in RDF Integration Systems

An RDF integration system is of the form \(S=\langle \onto, \rules, \mappings, \extensions \rangle\), where \(\onto\) is a first order RDFS ontology (without blank nodes), \(\rules\) is the set of RDFS entailment rules composed of two disjoint rule sets \(\rules_{a}\) and \(\rules_{c}\), finally \(\mappings\) and \(\extensions\) are RIS mappings with their extensions.

The certain answer set of a BGP query \(q\) on \(S\) is: \[\cert(q, S) = \{\phi(\bar x) \mid (\rdfGraph \cup \onto) \models_{\rules}^{\phi} q(\bar x)\}\] where \(\phi(\bar x)\) is made of values from \(\extensions\).

Classifying Query Answering Methods by Kind of Reasoning

Two Kinds of Reasoning

Since \(\rules = \rules_{a} \cup \rules_{c}\), we can split the reasoning w.r.t. \(\rules\) in two:

  • reasoning w.r.t. \(\rules_{a}\), to entail new assertion triples,
  • reasoning w.r.t. \(\rules_{c}\), to entail new constraint (ontological) triples.

Moreover, we have proven that the saturation w.r.t. \(\rules\) of RDF graph can be obtained by saturating w.r.t. \(\rules_{a}\) then \(\rules_{c}\) or in the inverse order:

For \(\graph\) an RDF graph whose ontology is FO RDFS ontology, it holds: \[\graph^{\rules} = \left (\graph^{\rules_{a}} \right )^{\rules_{c}} = \left (\graph^{\rules_{c}} \right )^{\rules_{a}}\]

Methods for reasoning w.r.t. \(\rules_{a}\)

We define methods to handle the reasoning w.r.t. \(\rules_{a}\) in \(S\) during the computation of the certain answer of a BGPQ \(q\):

  • saturate w.r.t. \(\rules_{a}\). This method is only applicable when the graph has been saturated, i.e., in a materialization

context. It consists of saturating the materialization of the induced graph \(\rdfGraph\) with the ontology \(\onto\) w.r.t. \(\rules_{a}\) before evaluating the query. This can be done in pre-processing (prior to any query being answered).

  • reformulate w.r.t. \(\rules_{a}\). This methods consists of reformulating the query \(q\) w.r.t. \(\rules_{a}\) and \(\onto\)

as \(\mathcal{Q_{a}} = \mathrm{Ref}_{a}(q, \onto)\).

  • saturate mappings. This method consists of replacing the mappings \(\mappings\) with the saturated mappings

\(\mappings^{\rules_{a}, \onto}\). This can be done in pre-processing.

Methods for reasoning w.r.t. \(\rules_{c}\)

We define methods to handle the reasoning w.r.t. \(\rules_{c}\) in \(S\) during the computation of certain answer of a BGPQ \(q\):

  • saturate w.r.t. \(\rules_{c}\). This method is only applicable in materialization scenarios. It consists of

saturating the materialization of the ontology \(\onto\) w.r.t. \(\rules_{c}\) before evaluating the query. This can be done in pre-processing.

  • reformulate w.r.t. \(\rules_{c}\). This method consists of reformulating the query \(q\) w.r.t. \(\rules_{c}\)

and \(\onto\) as \(\mathcal{Q_{c}} = \mathrm{Ref}_{c}(q, \onto)\).

  • mappings for \(\onto^{\rules_{c}}\). This method consists of adding the mappings \(\mappings_{\onto^{\rules_{c}}}\)

and their extensions \(\extensions_{\onto^{\rules_{c}}}\) to \(S\) in order to populate \(\onto^{\rules_{c}}\) (the saturated ontology) in the induced graph. This method can be applied in pre-processing.

Combinations of methods for reasoning w.r.t. \(\rules\)

We can combine one method for reasoning w.r.t. \(\rules_{a}\) with one other w.r.t. \(\rules_{c}\) in order to compute \(\cert(q, S)\) certain answers of \(q\) on \(S\). The following table contains an expression of \(\cert(q, S)\) for each combination. Each of this expression will lead to a computation according we choose a materialization or mediator approach.

When we use a materialization approach all combinations in the following table are available. And we compute \(\cert(q, S)\) by evaluating a UBGPQ on a materialized graph as follow:

  • expressions in first line or first column have the form \(Q(\graph^{\rules})\). Its computation is done by (i) materializing the graph \(\graph\), (ii) saturating it using \(\rules\) and (iii) evaluating \(Q\) in the saturation. (i) and (ii) can be done in pre-processing.
  • other expressions have the form \(\cert(Q, \langle \emptyset, \emptyset, \mappings, \extensions \rangle)\). Its computation is done by (i) materializing the induced graph \(\graph^{\mappings}_{\extensions}\), (ii) evaluating \(Q\) on the materialization. (i) can be done in pre-processing.

When we use a mediator approach, combinations of the first line and first column are not available. So, all expressions have the form \(\cert(Q, \langle \emptyset, \emptyset, \mappings, \extensions \rangle)\). We compute the certain answers by (i) getting a rewriting of \(Q\) using \(\mappings\) (ii) evaluating the rewriting on \(\extensions\) using the mediator.

Finally, we have 13 methods for query answering in RIS, 9 methods by materialization and 4 methods by mediation.

  saturate w.r.t. \(\rules_{a}\) reformulate w.r.t. \(\rules_{a}\) saturate mappings
saturate w.r.t. \(\rules_{c}\) \(q((\rdfGraph \cup \onto)^{\rules_{a} \cup \rules_{c}})\) \(\mathcal{Q_{a}}(\rdfGraph \cup \onto^{\rules_{c}})\) \(q(\graph^{\mappings^{\rules_{a}, \onto}}_{\extensions} \cup \onto^{\rules_{c}})\)
reformulate w.r.t. \(\rules_{c}\) \(\mathcal{Q_{c}}((\rdfGraph \cup \onto)^{\rules_{a}})\) \(\cert(\mathcal{Q_{c,a}}, \langle \emptyset, \emptyset, \mappings, \extensions \rangle)\) \(\cert(\mathcal{Q_{c}}, \langle \emptyset, \emptyset, \mappings^{\rules_{a}, \onto}, \extensions \rangle)\)
mappings for \(\onto_{\rules_{c}}\) \(q((\rdfGraph \cup \graph^{\mappings_{\onto^{\rules_{c}}}}_{\extensions_{\onto^{\rules_{c}}}})^{\rules_{a}})\) \(\cert(\mathcal{Q_{a}}, \langle \emptyset, \emptyset, \mappings \cup \mappings_{\onto^{\rules_{c}}}, \extensions \cup \extensions_{\onto^{\rules_{c}}} \rangle)\) \(\cert(q, \langle \emptyset, \emptyset, \mappings^{\rules_{a}, \onto} \cup \mappings_{\onto^{\rules_{c}}}, \extensions \cup \extensions_{\onto^{\rules_{c}}} \rangle)\)