Rewriting Conjunctive Queries over Description Logic Knowledge Bases.
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 que...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2008
|
| _version_ | 1797079848332558336 |
|---|---|
| author | Pérez-Urbina, H Motik, B Horrocks, I |
| author2 | Schewe, K |
| author_facet | Schewe, K Pérez-Urbina, H Motik, B Horrocks, I |
| author_sort | Pérez-Urbina, H |
| collection | OXFORD |
| description | 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 is NLogSpace-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 from LogSpace to PTime-complete. © 2008 Springer Berlin Heidelberg. |
| first_indexed | 2024-03-07T00:51:41Z |
| format | Journal article |
| id | oxford-uuid:869db2f5-5fd3-499a-a4da-de9efede3359 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:51:41Z |
| publishDate | 2008 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:869db2f5-5fd3-499a-a4da-de9efede33592022-03-26T22:05:05ZRewriting Conjunctive Queries over Description Logic Knowledge Bases.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:869db2f5-5fd3-499a-a4da-de9efede3359EnglishSymplectic Elements at OxfordSpringer2008Pérez-Urbina, HMotik, BHorrocks, ISchewe, KThalheim, BWe 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 is NLogSpace-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 from LogSpace to PTime-complete. © 2008 Springer Berlin Heidelberg. |
| spellingShingle | Pérez-Urbina, H Motik, B Horrocks, I Rewriting Conjunctive Queries over Description Logic Knowledge Bases. |
| title | Rewriting Conjunctive Queries over Description Logic Knowledge Bases. |
| title_full | Rewriting Conjunctive Queries over Description Logic Knowledge Bases. |
| title_fullStr | Rewriting Conjunctive Queries over Description Logic Knowledge Bases. |
| title_full_unstemmed | Rewriting Conjunctive Queries over Description Logic Knowledge Bases. |
| title_short | Rewriting Conjunctive Queries over Description Logic Knowledge Bases. |
| title_sort | rewriting conjunctive queries over description logic knowledge bases |
| work_keys_str_mv | AT perezurbinah rewritingconjunctivequeriesoverdescriptionlogicknowledgebases AT motikb rewritingconjunctivequeriesoverdescriptionlogicknowledgebases AT horrocksi rewritingconjunctivequeriesoverdescriptionlogicknowledgebases |