# Acquiring Ontology Axioms through Mappings to Data Sources +
## 5 Query Answering
### Query Rewriting
As an example, consider the query  
\[q(x) \leftarrow \mathit{Inst}_{C}(x,\mathit{Ford}),\mathit{Inst}_{C}(x,\mathit{ Exists}(\mathit{produced\_in})),\mathit{Inst}_{R}(x,\textsc{ Australia},\mathit{produced\_in}).\]  
\(\mathit{Normalize}(q)\) returns the query  
\[q(x) \leftarrow \mathit{Inst}_{C}(x,\mathit{Ford}),\mathit{Inst}_{R}(x,\_, \_,\mathit{produced\_in}),\mathit{Inst}_{R}(x,\textsc{Australia},\mathit{ produced\_in}).\]  
Then, let \(q\) be an IHCQ and \(\mathcal{M}\) be an instance-mapping, \(\mathit{Denormalize}(q,\mathcal{M})\) is the IHUCQ \(Q\) defined inductively as follows:  
* \(q\in Q\);
* if \(q^{\prime}\in Q\) and \(q^{\prime}\) contains an atom \(\alpha\) of the form \(\mathit{Inst}_{R}(e_{1},\_,e_{2})\), and either \(\mathit{Exists}(e_{2})\) occurs in \(\mathcal{M}\) or \(\mathit{Exists}(x)\) (where \(x\) is a variable) occurs in \(\mathcal{M}\), then the query obtained from \(q^{\prime}\) by replacing \(\alpha\) with the atom \(\mathit{Inst}_{C}(e_{1},\mathit{Exists}(e_{2}))\) belongs to \(Q\);
* if \(q^{\prime}\in Q\) and \(q^{\prime}\) contains an atom \(\alpha\) of the form \(\mathit{Inst}_{R}(\_,e_{1},e_{2})\), and either \(\mathit{Exists}(\mathit{Inv}(e_{2}))\) occurs in \(\mathcal{M}\) or \(\mathit{Exists}(\mathit{Inv}(x))\) (where \(x\) is a variable) occurs in \(\mathcal{M}\), then the query obtained from \(q^{\prime}\) by replacing \(\alpha\) with the atom \(\mathit{Inst}_{C}(e_{1},\mathit{Exists}(\mathit{Inv}(e_{2})))\) belongs to \(Q\);
* if \(q^{\prime}\in Q\) and \(q^{\prime}\) contains an atom \(\alpha\) of the form \(\mathit{Inst}_{R}(e_{1},\mathit{Exists}(\mathit{Inv}(e_{3})))\) belongs to \(Q\);
* if \(q^{\prime}\in Q\) and \(q^{\prime}\) contains an atom \(\alpha\) of the form \(\mathit{Inst}_{R}(e_{1},e_{2},e_{3})\) and either \(\mathit{Inv}(e_{3})\) occurs in \(\mathcal{M}\) or \(\mathit{Inv}(x)\) (where \(x\) is a variable) occurs in \(\mathcal{M}\), then the query obtained from \(q^{\prime}\) by replacing \(\alpha\) with the atom \(\mathit{Inst}_{R}(e_{2},e_{1},\mathit{Inv}(e_{3}))\) belongs to \(Q\). Finally, let \(Q\) be an IHUCQ and let \(\mathcal{M}\) be a mapping, we define \(\mathit{Denormalize}(Q,\mathcal{M})\) as \(\bigcup_{q\in Q}\mathit{Denormalize}(q,\mathcal{M})\). We formally introduce below the functions \(\tau\) and \(\tau^{-}\), which transform IHUCQs into EUCQs and vice versa. Let \(q\) be an IHCQ and let \(\mathcal{T}\) be a TBox, \(\tau(q,\mathcal{T})\) is the ECQ obtained from \(q\) as follows:  
* each atom of \(q\) of the form \(\mathit{Inst}_{C}(e_{1},e_{2})\), such that \(e_{2}\in\mathit{Concepts}(\mathcal{T})\), is replaced with the atom \(e_{2}(e_{1})\);
* each atom of \(q\) of the form \(\mathit{Inst}_{R}(e_{1},e_{2},e_{3})\), such that \(e_{3}\in\mathit{Roles}(\mathcal{T})\), is replaced with the atom \(e_{3}(e_{1},e_{2})\). Let us now apply the function \(\tau\) to the query (1) (which is already normalized), and obtain the query  
\[q(x)\gets\mathit{Ford}(x),\mathit{FALCON}(x),\mathit{Coupe}(\mathit{ FALCON}),\mathit{produced\_in}(x,\textsc{Australia}). \tag{2}\]  
Then, given an IHUCQ \(Q\), we define \(\tau(Q,\mathcal{T})=\{\tau(q,\mathcal{T})\mid q\in Q\}\). Let \(q\) be an ECQ and \(\mathcal{T}\) be a TBox, then \(\tau^{-}(q,\mathcal{T})\) is the IHCQ obtained from \(q\) as follows:  
* each atom of \(q\) of the form \(e_{2}(e_{1})\) is replaced with the atom \(\mathit{Inst}_{C}(e_{1},e_{2})\);
* each atom of \(q\) of the form \(e_{3}(e_{1},e_{2})\) is replaced with the atom \(\mathit{Inst}_{R}(e_{1},e_{2},e_{3})\). Then, given an IHUCQ \(Q\), we define \(\tau^{-}(Q,\mathcal{T})=\{\tau^{-}(q,\mathcal{T})\mid q\in Q\}\). An example of application of \(\tau^{-}(Q,\mathcal{T})\) can be obtained by simply reversing the transformation shown in Example 7. We can now formally define our algorithm for query rewriting. The algorithm takes as input an IHUCQ, a TBox and an instance-mapping, and returns a new IHUCQ.