# Acquiring Ontology Axioms through Mappings to Data Sources +
## 5 Query Answering
### Query Rewriting
Given an IHUCQ \(Q\) and a TBox \(\mathcal{T}\), we denote by \(\mathit{PerfectRef}(Q,\mathcal{T})\) the EUCQ returned by the query rewriting algorithm for \(\mathit{DL-Lite}_{\mathcal{R}}\) presented in [23] (Actually, we consider a slight generalization of that algorithm, allowing for the presence of a ternary relation (\(\mathit{Inst}_{R}\)) in the query.). ALGORITHM _RewritelHUCQ_\((Q,\mathcal{T},\mathcal{M})\)  
INPUT: IHUCQ \(Q\), \(\mathit{DL-Lite}_{\mathcal{R}}\) TBox \(\mathcal{T}\), instance-mapping \(\mathcal{M}\)  
OUTPUT: IHUCQ \(Q^{\prime}\)  
**begin**  
\(Q_{0}=\mathit{PMG}(Q,\mathcal{T})\);  
\(Q_{1}=\mathit{Normalize}(Q_{0})\);  
\(Q_{2}=\tau(Q_{1},\mathcal{T})\);  
\(Q_{3}=\mathit{PerfectRef}(Q_{2},\mathcal{T})\);  
\(Q_{4}=\tau^{-}(Q_{3},\mathcal{T})\);  
\(Q^{\prime}=\mathit{Denormalize}(Q_{4},\mathcal{M})\);  
**return**\(Q^{\prime}\);  
**end**  
**Example 8**: _To provide an example of a complete execution of the algorithm \(\mathit{RewritelHUCQ}(Q,\mathcal{T},\mathcal{M})\), let us now continue the rewriting described in Example 6 and in Example 7. Let us focus on the PerfectRef function, and apply it to the query (2) (which is contained in the set \(Q_{2}\) of CQs). PerfectRef transforms the atoms of the query using TBox inclusions as rewriting rules, from right to left. For example, according to the inclusion \(\mathtt{FALCON}\sqsubseteq\mathit{Ford}\), it rewrites the atom \(\mathit{Ford}(x)\) in query (2) into the atom \(\mathtt{FALCON}(x)\) (intuitively, the PerfectRef encodes in the rewriting the knowledge expressed by the ontology saying that to obtain instances of \(\mathit{Ford}\) one has to look also for instances of \(\mathtt{FALCON}\)). In this way PerfectRef produces the following query and adds it to the set \(Q_{3}\) (notice that the atom \(\mathtt{FALCON}(x)\) was already present in the query, thus the effect of the rewriting in this case is simply dropping the first atom of the query):_  
\[q(x)\,\leftarrow\,\mathtt{FALCON}(x),\mathit{Coupe}(\mathtt{FALCON}),\, \mathit{produced\_in}(x,\mathtt{Australia}). \tag{3}\]  
_A similar reformulation is performed for all atoms whose predicate occurs in the right-hand side of a positive inclusion (provided that its arguments are not bound, as described in [23]). Among the queries returned by PerfectRef we consider in the following only query (3), which, as we will see later, will allow us to obtain the answer to the original query (the other queries returned by \(\mathit{RewritelHUCQ}(Q,\mathcal{T},\mathcal{M})\) do not really contribute to the final answer in our example). Finally, \(\mathit{RewritelHUCQ}(Q,\mathcal{T},\mathcal{M})\) applies \(\tau^{-}\) and \(\mathit{Denormalize}\) (which in this case is immaterial) to query (3), thus returning the query_  
\[q(x)\,\leftarrow\,\mathit{Inst}_{\mathbb{C}}(x,\mathtt{FALCON}),\mathit{Inst}_{ \mathbb{C}}(\mathtt{FALCON},\mathit{Coupe}),\mathit{Inst}_{R}(x,\mathtt{Australia}, \mathrm{produced\_in}). \tag{4}\]  
The IHUCQ returned by \(\mathit{RewritelHUCQ}(Q,\mathcal{T},\mathcal{M})\) constitutes a perfect rewriting of the query \(Q\) with respect to the TBox \(\mathcal{T}\) and the mapping \(\mathcal{M}\), as formally stated by the following theorem. **Theorem 1**: _Let \(\mathcal{T}\) be a TBox, let \(\mathcal{M}\) be an instance-mapping and let \(Q\) be an IHUCQ. Then, for every ABox \(\mathcal{A}\) that is a retrievable through \(\mathcal{M}\), \(\mathit{cert}(Q,\mathcal{T}\cup\mathcal{A})=\mathit{cert}(\mathit{RewritelHUCQ }(Q,\mathcal{T},\mathcal{M}),\mathcal{A})\)._  
The proof follows from Definition 4, from Lemma 1, from the correctness of the algorithm _PerfectRef_[23], and from the fact that the functions _Normalize_, \(\tau\), \(\tau^{-}\) and _Denormalize_ just perform equivalent transformations of the query.