Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies
We study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i.e., one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be rewritten into a linear program (i.e., having...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2016
|
| _version_ | 1797100656843030528 |
|---|---|
| author | Cuenca Grau, B Kaminski, M Nenov, Y |
| author_facet | Cuenca Grau, B Kaminski, M Nenov, Y |
| author_sort | Cuenca Grau, B |
| collection | OXFORD |
| description | We study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i.e., one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be rewritten into a linear program (i.e., having at most one IDB body atom in each rule), thus providing a novel characterisation of Datalog rewritability in terms of linearisability. Motivated by this result, we propose the class of markable programs, which extends both Datalog and linear Disjunctive Datalog and admits Datalog rewritings of polynomial size. We show that our results can be seamlessly applied to ontological reasoning and identify two classes of non-Horn ontologies that admit Datalog rewritings of polynomial and exponential size, respectively. Finally, we shift our attention to conjunctive query answering and extend our results to the problem of computing a rewriting of a Disjunctive Datalog program that yields the same answers to a given query w.r.t. arbitrary data. Our empirical results suggest that a fair number of non-Horn ontologies are Datalog rewritable and that query answering over such ontologies becomes feasible using a Datalog engine. |
| first_indexed | 2024-03-07T05:40:41Z |
| format | Journal article |
| id | oxford-uuid:e5753c32-30e2-44cd-8444-01ee9e2f53df |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:40:41Z |
| publishDate | 2016 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:e5753c32-30e2-44cd-8444-01ee9e2f53df2022-03-27T10:24:06ZDatalog rewritability of Disjunctive Datalog programs and non-Horn ontologiesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e5753c32-30e2-44cd-8444-01ee9e2f53dfSymplectic Elements at OxfordElsevier2016Cuenca Grau, BKaminski, MNenov, YWe study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i.e., one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be rewritten into a linear program (i.e., having at most one IDB body atom in each rule), thus providing a novel characterisation of Datalog rewritability in terms of linearisability. Motivated by this result, we propose the class of markable programs, which extends both Datalog and linear Disjunctive Datalog and admits Datalog rewritings of polynomial size. We show that our results can be seamlessly applied to ontological reasoning and identify two classes of non-Horn ontologies that admit Datalog rewritings of polynomial and exponential size, respectively. Finally, we shift our attention to conjunctive query answering and extend our results to the problem of computing a rewriting of a Disjunctive Datalog program that yields the same answers to a given query w.r.t. arbitrary data. Our empirical results suggest that a fair number of non-Horn ontologies are Datalog rewritable and that query answering over such ontologies becomes feasible using a Datalog engine. |
| spellingShingle | Cuenca Grau, B Kaminski, M Nenov, Y Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies |
| title | Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies |
| title_full | Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies |
| title_fullStr | Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies |
| title_full_unstemmed | Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies |
| title_short | Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies |
| title_sort | datalog rewritability of disjunctive datalog programs and non horn ontologies |
| work_keys_str_mv | AT cuencagraub datalogrewritabilityofdisjunctivedatalogprogramsandnonhornontologies AT kaminskim datalogrewritabilityofdisjunctivedatalogprogramsandnonhornontologies AT nenovy datalogrewritabilityofdisjunctivedatalogprogramsandnonhornontologies |