Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning
We study the problem of rewriting a disjunctive datalog program into plain datalog. We show that a disjunctive program is rewritable if and only if it is equivalent to a linear disjunctive program, thus providing a novel characterisation of datalog rewritability. Motivated by this result, we propose...
| Main Authors: | , , |
|---|---|
| פורמט: | Conference item |
| יצא לאור: |
Association for Computing Machinery
2014
|
| _version_ | 1826299313907564544 |
|---|---|
| author | Kaminski, M Nenov, Y Cuenca Grau, B |
| author_facet | Kaminski, M Nenov, Y Cuenca Grau, B |
| author_sort | Kaminski, M |
| collection | OXFORD |
| description | We study the problem of rewriting a disjunctive datalog program into plain datalog. We show that a disjunctive program is rewritable if and only if it is equivalent to a linear disjunctive program, thus providing a novel characterisation of datalog rewritability. Motivated by this result, we propose weakly linear disjunctive datalog—a novel rule-based KR language that extends both datalog and linear disjunctive datalog and for which reasoning is tractable in data complexity. We then explore applications of weakly linear programs to ontology reasoning and propose a tractable extension of OWL 2 RL with disjunctive axioms. Our empirical results suggest that many non-Horn ontologies can be reduced to weakly linear programs and that query answering over such ontologies using a datalog engine is feasible in practice. |
| first_indexed | 2024-03-07T05:00:02Z |
| format | Conference item |
| id | oxford-uuid:d7f67d5b-8ca7-4f75-b970-4a303e3f36a1 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:00:02Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:d7f67d5b-8ca7-4f75-b970-4a303e3f36a12022-03-27T08:44:49ZDatalog rewritability of disjunctive datalog programs and its applications to ontology reasoningConference itemhttp://purl.org/coar/resource_type/c_5794uuid:d7f67d5b-8ca7-4f75-b970-4a303e3f36a1Symplectic Elements at OxfordAssociation for Computing Machinery2014Kaminski, MNenov, YCuenca Grau, BWe study the problem of rewriting a disjunctive datalog program into plain datalog. We show that a disjunctive program is rewritable if and only if it is equivalent to a linear disjunctive program, thus providing a novel characterisation of datalog rewritability. Motivated by this result, we propose weakly linear disjunctive datalog—a novel rule-based KR language that extends both datalog and linear disjunctive datalog and for which reasoning is tractable in data complexity. We then explore applications of weakly linear programs to ontology reasoning and propose a tractable extension of OWL 2 RL with disjunctive axioms. Our empirical results suggest that many non-Horn ontologies can be reduced to weakly linear programs and that query answering over such ontologies using a datalog engine is feasible in practice. |
| spellingShingle | Kaminski, M Nenov, Y Cuenca Grau, B Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning |
| title | Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning |
| title_full | Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning |
| title_fullStr | Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning |
| title_full_unstemmed | Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning |
| title_short | Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning |
| title_sort | datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning |
| work_keys_str_mv | AT kaminskim datalogrewritabilityofdisjunctivedatalogprogramsanditsapplicationstoontologyreasoning AT nenovy datalogrewritabilityofdisjunctivedatalogprogramsanditsapplicationstoontologyreasoning AT cuencagraub datalogrewritabilityofdisjunctivedatalogprogramsanditsapplicationstoontologyreasoning |