Conjunctive queries for EL with role composition
EL++ is a rather expressive description logic (DL) that still admits polynomial time inferencing for many reasoning tasks. Conjunctive queries are an important means for expressive querying of DL knowledge bases. We address the problem of computing conjunctive query entailment for EL ++ knowledge ba...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2007
|
| _version_ | 1826281269043920896 |
|---|---|
| author | Krötzsch, M Rudolph, S |
| author_facet | Krötzsch, M Rudolph, S |
| author_sort | Krötzsch, M |
| collection | OXFORD |
| description | EL++ is a rather expressive description logic (DL) that still admits polynomial time inferencing for many reasoning tasks. Conjunctive queries are an important means for expressive querying of DL knowledge bases. We address the problem of computing conjunctive query entailment for EL ++ knowledge bases. As it turns out, querying unrestricted EL ++ is actually undecidable, but we identify restrictions under which query answering becomes decidable and even tractable.We give precise characterisations of schema, query, and combined complexity. To the best of our knowledge, the presented algorithm is the first to answer conjunctive queries in a DL that admits complex role inclusion axioms. © 2007 by Bozen-Bolzano University Press. |
| first_indexed | 2024-03-07T00:26:16Z |
| format | Journal article |
| id | oxford-uuid:7e3ed2d3-7708-45b8-a75d-f1ed98d3a427 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:26:16Z |
| publishDate | 2007 |
| record_format | dspace |
| spelling | oxford-uuid:7e3ed2d3-7708-45b8-a75d-f1ed98d3a4272022-03-26T21:08:54ZConjunctive queries for EL with role compositionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7e3ed2d3-7708-45b8-a75d-f1ed98d3a427EnglishSymplectic Elements at Oxford2007Krötzsch, MRudolph, SEL++ is a rather expressive description logic (DL) that still admits polynomial time inferencing for many reasoning tasks. Conjunctive queries are an important means for expressive querying of DL knowledge bases. We address the problem of computing conjunctive query entailment for EL ++ knowledge bases. As it turns out, querying unrestricted EL ++ is actually undecidable, but we identify restrictions under which query answering becomes decidable and even tractable.We give precise characterisations of schema, query, and combined complexity. To the best of our knowledge, the presented algorithm is the first to answer conjunctive queries in a DL that admits complex role inclusion axioms. © 2007 by Bozen-Bolzano University Press. |
| spellingShingle | Krötzsch, M Rudolph, S Conjunctive queries for EL with role composition |
| title | Conjunctive queries for EL with role composition |
| title_full | Conjunctive queries for EL with role composition |
| title_fullStr | Conjunctive queries for EL with role composition |
| title_full_unstemmed | Conjunctive queries for EL with role composition |
| title_short | Conjunctive queries for EL with role composition |
| title_sort | conjunctive queries for el with role composition |
| work_keys_str_mv | AT krotzschm conjunctivequeriesforelwithrolecomposition AT rudolphs conjunctivequeriesforelwithrolecomposition |