# Acquiring Ontology Axioms through Mappings to Data Sources +
## 5 Query Answering
### Query Answering
By unfolding it through \(\mathsf{UnfoldDB}(Q^{\prime},\mathcal{M}_{A})\), we obtain (among other queries) the FOL query_  
\[\{x\quad|\quad\texttt{T-Cars}(x,\texttt{c1},a,b)\wedge\texttt{T-CarTypes}( \texttt{c1},\mathit{FALCON},d,e)\wedge\texttt{T-CarTypes}(a^{\prime}, \mathit{FALCON},b^{\prime},\mathit{cuppe})\wedge\]  
\[\quad\texttt{T-Cars}(x,a^{\prime\prime},b^{\prime\prime},\texttt{Australia})\}\]  
_More in detail, we have unfolded the atom \(\mathit{Inst}_{C}(x,\mathit{FALCON})\) using mapping M13, atom \(\mathit{Inst}_{C}(\mathit{FALCON},\mathit{cuppe})\) using mapping M12, and the atom \(\mathit{Inst}_{R}(x,\texttt{Australia},\mathit{produced\_in})\) using mapping M10. Notice also that other queries are produced by the function \(\mathsf{UnfoldDB}\) applied to the query (4) and the \(\mathcal{M}_{A}\) (e.g., by unfolding \(\mathit{Inst}_{C}(\mathit{FALCON},\mathit{cuppe})\) through M12). However, the one we showed is sufficient to obtain the answers to the original query. It is indeed easy to see that by evaluating the above query over \(\mathit{DB}_{\mathcal{M}_{A}}\) (see Figure 3), we obtain the answer \(\mathtt{INTERCEPTOR}\), and this is the only answer to the query (i) given in Example 5 evaluated over the MKD system \(\mathcal{K}\)._To prove correctness of the above algorithm, we first state the following property, whose proof immediately follows from the definition of \(\mathit{Retrieve}(\mathcal{M},DB)\) and the definition of model of a \(\mathit{Hi}(\mathit{DL}\mathit{-Lite}_{\mathcal{R}})\) MKB. **Lemma 2**: _Let \(\mathcal{K}=\langle DB,\mathcal{M}\rangle\) be a \(\mathit{Hi}(\mathit{DL}\mathit{-Lite}_{\mathcal{R}})\) MKB and let \(\mathcal{H}=\mathit{Retrieve}(\mathcal{M},DB)\). The set of models of \(\mathcal{K}\) and \(\mathcal{H}\) coincide._  
We also need the following additional property. **Lemma 3**: _Let \(\mathcal{M}\) be an instance-mapping, and let \(Q\) be an IHUCQ. Then, for every database \(DB\),_  
\[\mathit{cert}(Q,\langle\mathcal{M},DB\rangle)=\mathit{IntEval}(\mathsf{UnfoldDB }(Q,\mathcal{M}),DB).\]  
Proof. : The proof follows from Definition 4 and by a natural, slight extension (which we leave to the reader) of the proof of correctness of the algorithm \(\mathsf{UnfoldDB}\) shown in [20]. We are now ready to show the correctness of the algorithm _Answer_. **Theorem 2**: _Let \(\mathcal{K}\)=\(\langle DB,\mathcal{M}\rangle\) be a \(\mathit{Hi}(\mathit{DL}\mathit{-Lite}_{\mathcal{R}})\) MKB, let \(Q\) be an IHUCQ, and let \(U\) be the set of tuples returned by \(\mathit{Answer}(Q,\mathcal{K})\). Then, \(\mathit{cert}(Q,\mathcal{K})=U\)._  
Proof. : The proof immediately follows from Theorem 1 and Lemmas 2 and 3. Finally, from the algorithm _Answer_ we are able to derive the following complexity results for query answering over \(\mathit{Hi}(\mathit{DL}\mathit{-Lite}_{\mathcal{R}})\) MKBs. **Theorem 3**: _Let \(\mathcal{K}\)=\(\langle DB,\mathcal{M}\rangle\) be a \(\mathit{Hi}(\mathit{DL}\mathit{-Lite}_{\mathcal{R}})\) MKB, let \(Q\) be an IHUCQ and let \(\vec{t}\) be a tuple of expressions. Deciding whether \(\mathcal{K}\models Q(\vec{t})\) is in \(AC^{0}\) with respect to the size of \(DB_{\mathcal{M}_{A}}\), is in PSPACE with respect to the size of \(\mathcal{K}\), and is NP-complete with respect to the size of \(Q(\vec{t})\)._  
Proof. : To decide whether \(\mathcal{K}\models Q(\vec{t})\) we can execute \(\mathit{Answer}(Q(\vec{t}),\mathcal{K})\). Then, membership in \(AC^{0}\) with respect to the size of \(DB_{\mathcal{M}_{A}}\) follows from the fact that the only step of the algorithm _Answer_ that depends on \(DB_{\mathcal{M}_{A}}\) is \(\mathit{IntEval}(Q^{\prime\prime},DB_{\mathcal{M}_{A}})\), where \(Q^{\prime\prime}\) is a FOL query and the fact that evaluating an FOL query over a database is in \(AC^{0}\) in data complexity.