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

Source Target Rewriting Optimizations

During source target rewriting, many optimizations can be done using source constraints and Skolem functions

Skolem Function Encoding

We will assume that Skolem functions have disjoint range and are bijective.

Example

Assume the following mappings where \(f\) and \(g\) are Skolem functions:

  1. \(\textrm{Product}(id, l, c) \rightarrow \triple{f(id)}{\textrm{ex:label}}{l}, \triple{f(id)}{\textrm{ex:comment}}{c}\).
  2. \(\textrm{Vendor}(id, l) \rightarrow \triple{g(id)}{\textrm{ex:label}}{l}\).

Consider the following query: \[q(x, y, z) \leftarrow \triple{x}{\textrm{ex:label}}{y}, \triple{x}{\textrm{ex:comment}}{z}\]

Current Rewriting

We have encoded functions in a two layers integration:

  1. \(\textrm{Product}(id, l, c) \rightarrow \textrm{V}_{1}(f(id),l,c)\)
  2. \(V_{1}(p, l, c) \rightarrow \triple{p}{\textrm{ex:label}}{l}, \triple{p}{\textrm{ex:comment}}{c}\)
  3. \(\textrm{Vendor}(id, l) \rightarrow \textrm{V}_{2}(g(id), l)\)
  4. \(\textrm{V}_{2}(v, l) \rightarrow \triple{v}{\textrm{ex:label}}{l}\)

Currently, we will rewrite \(q\) in terms of queries using view \(V_{1}\) and \(V_{2}\) only and we find:

  1. \(Q_{1}(x, y, z) \leftarrow \textrm{V}_{1}(x, y, c), \textrm{V}_{1}(x,l,z)\)
  2. \(Q_{2}(x, y, z) \leftarrow \textrm{V}_{2}(x, y), \textrm{V}_{1}(x,l,z)\)

We can see that the rewriting \(Q_{2}\) have no answers, because the join on the first position of \(V_{1}\) and \(V_{2}\) will be translated as \(f(id_{1}) = g(id_{2})\) using the definitions of the views. But Skolem functions have disjoint ranges.

Skolem Predicates

We can translate the two layers mappings in an one layer mappings as follow:

  1. \(\textrm{Product}(id, l, c), F(id, p) \rightarrow \triple{p}{\textrm{ex:label}}{l}, \triple{p}{\textrm{ex:comment}}{c}\).
  2. \(\textrm{Vendor}(id, l), G(id, v) \rightarrow \triple{v}{\textrm{ex:label}}{l}\).

where \(F\) and \(G\) Skolem predicates represent respectively Skolem functions \(f\) and \(g\). The first arguments of predicate are the functions inputs and the second arguments are the outputs. Because this new predicate represent Skolem function, we can define the following constraints on it (here for \(F\), the same is true for \(G\)):

  • function predicate: \(\forall x,y_{1},y_{2}~ F(x, y_{1}), F(x, y_{2}) \rightarrow y_{1} = y_{2}\),
  • injective function: \(\forall x_{1}, x_{2},y~ F(x_{1}, y), F(x_{2}, y) \rightarrow x_{1} = x_{2}\),
  • disjoint ranges: for two distinct Skolem predicate \(F\) and \(G\), \(\forall x_{1}, x_{2}, y~ F(x_{1}, y), G(x_{2}, y) \rightarrow \perp\).

If we consider the rewritings of \(q\) according to the mappings including Skolem predicates:

  1. \(Q_{1}(x, y, z) \leftarrow \textrm{Product}(id_{1}, y, c), F(id_{1}, x), \textrm{Product}(id_{2}, l, z), F(id_{2}, x)\)
  2. \(Q_{2}(x, y, z) \leftarrow \textrm{Vendor}(id_{1}, y), G(id_{1}, x), \textrm{Product}(id_{2}, l, z), F(id_{2}, x)\)

According to the disjoint range property of Skolem predicate, we can deduce that \(Q_{2}\) have no answer. And we can apply the injective function property of \(F\) to obtain the following rewriting of \(q\):

\[Q_{r}(x, y, z) \leftarrow \textrm{Product}(id, y, c), \textrm{Product}(id, l, z), F(id, x)\]

Primary Key

If we add the fact that the first column of \(\textrm{Product}\) is a primary key, we have the following constraint: \[\forall x, y_{1}, y_{2}, z_{1}, z_{2} ~ \textrm{Product}(x, y_{1}, z_{1}), \textrm{Product}(x, y_{2}, z_{2}) \rightarrow y_{1} = y_{2}, z_{1} = z_{2}\]

Then the rewriting of \(q\) becomes: \[Q_{r}(x, y, z) \leftarrow \textrm{Product}(id, y, z), F(id, x)\]

Applying a Primary Key Constraint on a CQ

A primary key constraint is a pair \((P, I)\) where:

  • \(P\) a predicate
  • \(I\) a set of indexes in \(P\).

Let \(F\) be a conjunction of atoms, a primary key constraint \((P, I)\) is applicable on \(F\), if there exists two distinct atoms \(P(\bar t)\) and \(P(\bar u)\) such that \(\forall i \in I~ \bar t_{i} = \bar u_{i}\). We say that \((P,I)\) is applicable on \(F\) by the atoms \(P(\bar t)\) and \(P(\bar u)\).

We define the result of the application of this primary key constraint on \(F\) using this two atoms as \(h(F)\), where \(h\) is homomorphism: \[\{\bar u_{k} \mapsto \bar t_{k} \mid 1 \leq k \leq \mathrm{arity}(P)\}.\] The homomorphism \(h\) is not well defined, when there exists \(k\) such that \(\bar t_{k}\) and \(\bar u_{k}\) are distinct constants, we say that there is a clash during the application.

Since conjunction of atoms are represented as set of atoms, the application of a primary key constraint on a conjunction of atoms using two atoms without clash correspond to:

  • remove one of the two atoms
  • replace each variable of the removed atom by the corresponding term of the remained one.

A clash during the application of a primary key constraint means that \(F\) the conjunction of atoms violates the primary key constraint. In the case where \(F\) is a conjunctive query, we can deduce that \(F\) have no answer under the primary key constraint.

Translate SQL View as Conjunctive Query on Tables

When it is possible, it is worth to translate SQL view definition into conjunctive view on table. It will enables constraints and query core computation.