We consider the problems of conjunctive query answering and rewriting for information integration systems in which a Description Logic ontology is used to provide a global view of the data. We present a resolution-based query rewriting algorithm for DL-Lite+ontologies, and use it to show that query answering in this setting isNLogSpace-complete with respect to data complexity. We also show that our algorithm produces an optimal rewriting when the input ontology is expressed in the language DL-Lite. Finally, we sketch an extended version of the algorithm that would, we are confident, be optimal for several DL languages with data complexity of query answering ranging fromLogSpacetoPTime-complete.
%0 Conference Paper
%1 Perez-Urbina2008
%A Perez-Urbina, Hector
%A Motik, Boris
%A Horrocks, Ian
%B Semantics in Data and Knowledge Bases
%D 2008
%I Springer Berlin / Heidelberg
%K InformationIntegration query rewriting
%P 199--214
%R 10.1007/978-3-540-88594-8_11
%T Rewriting Conjunctive Queries over Description Logic Knowledge Bases
%U http://www.springerlink.com/content/1vru315158284613/
%V 4925
%X We consider the problems of conjunctive query answering and rewriting for information integration systems in which a Description Logic ontology is used to provide a global view of the data. We present a resolution-based query rewriting algorithm for DL-Lite+ontologies, and use it to show that query answering in this setting isNLogSpace-complete with respect to data complexity. We also show that our algorithm produces an optimal rewriting when the input ontology is expressed in the language DL-Lite. Finally, we sketch an extended version of the algorithm that would, we are confident, be optimal for several DL languages with data complexity of query answering ranging fromLogSpacetoPTime-complete.
%@ 978-3-540-88593-1
@inproceedings{Perez-Urbina2008,
abstract = {We consider the problems of conjunctive query answering and rewriting for information integration systems in which a Description Logic ontology is used to provide a global view of the data. We present a resolution-based query rewriting algorithm for DL-Lite+ontologies, and use it to show that query answering in this setting isNLogSpace-complete with respect to data complexity. We also show that our algorithm produces an optimal rewriting when the input ontology is expressed in the language DL-Lite. Finally, we sketch an extended version of the algorithm that would, we are confident, be optimal for several DL languages with data complexity of query answering ranging fromLogSpacetoPTime-complete.},
added-at = {2009-11-25T16:02:33.000+0100},
author = {Perez-Urbina, Hector and Motik, Boris and Horrocks, Ian},
bdsk-url-1 = {http://www.springerlink.com/content/1vru315158284613/},
bdsk-url-2 = {http://dx.doi.org/10.1007/978-3-540-88594-8_11},
biburl = {https://www.bibsonomy.org/bibtex/200a192a6227c9c81761a03c068671706/alexjdl},
booktitle = {Semantics in Data and Knowledge Bases},
date-added = {2009-11-25 13:54:13 +0100},
date-modified = {2009-11-25 14:23:07 +0100},
description = {Information Integration bibliography},
doi = {10.1007/978-3-540-88594-8_11},
interhash = {45107ce47e1729bd596fb716d9e20a32},
intrahash = {00a192a6227c9c81761a03c068671706},
isbn = {978-3-540-88593-1},
issn = {0302-9743 (Print) 1611-3349 (Online)},
keywords = {InformationIntegration query rewriting},
pages = {199--214},
publisher = {Springer Berlin / Heidelberg},
series = {Lecture Notes in Computer Science},
subject_collection = {Computer Science},
timestamp = {2009-11-25T16:13:05.000+0100},
title = {Rewriting Conjunctive Queries over Description Logic Knowledge Bases},
url = {http://www.springerlink.com/content/1vru315158284613/},
volume = 4925,
year = 2008
}