Finite open-world query answering with number restrictions
Open-world query answering is the problem of deciding, given a set of facts, conjunction of constraints, and query, whether the facts and constraints imply the query. This amounts to reasoning over all instances that include the facts and satisfy the constraints. We study finite open-world query ans...
| Auteurs principaux: | , |
|---|---|
| Format: | Journal article |
| Langue: | English |
| Publié: |
Association for Computing Machinery
2020
|
| _version_ | 1826305976408473600 |
|---|---|
| author | Amarilli, A Benedikt, M |
| author_facet | Amarilli, A Benedikt, M |
| author_sort | Amarilli, A |
| collection | OXFORD |
| description | Open-world query answering is the problem of deciding, given a set of facts, conjunction of constraints, and query, whether the facts and constraints imply the query. This amounts to reasoning over all instances that include the facts and satisfy the constraints. We study finite open-world query answering (FQA), which assumes that the underlying world is finite and thus only considers the finite completions of the instance. The major known decidable cases of FQA derive from the following: the guarded fragment of first-order logic, which can express referential constraints (data in one place points to data in another) but cannot express number restrictions such as functional dependencies; and the guarded fragment with number restrictions but on a signature of arity only two. In this article, we give the first decidability results for FQA that combine both referential constraints and number restrictions for arbitrary signatures: We show that, for unary inclusion dependencies and functional dependencies, the finiteness assumption of FQA can be lifted up to taking the finite implication closure of the dependencies. Our result relies on new techniques to construct finite universal models of such constraints for any bound on the maximal query size. |
| first_indexed | 2024-03-07T06:40:57Z |
| format | Journal article |
| id | oxford-uuid:f93f7c82-779d-4f8b-92f5-c1fa7c956cf7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:40:57Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:f93f7c82-779d-4f8b-92f5-c1fa7c956cf72022-03-27T12:56:39ZFinite open-world query answering with number restrictionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f93f7c82-779d-4f8b-92f5-c1fa7c956cf7EnglishSymplectic Elements at OxfordAssociation for Computing Machinery2020Amarilli, ABenedikt, MOpen-world query answering is the problem of deciding, given a set of facts, conjunction of constraints, and query, whether the facts and constraints imply the query. This amounts to reasoning over all instances that include the facts and satisfy the constraints. We study finite open-world query answering (FQA), which assumes that the underlying world is finite and thus only considers the finite completions of the instance. The major known decidable cases of FQA derive from the following: the guarded fragment of first-order logic, which can express referential constraints (data in one place points to data in another) but cannot express number restrictions such as functional dependencies; and the guarded fragment with number restrictions but on a signature of arity only two. In this article, we give the first decidability results for FQA that combine both referential constraints and number restrictions for arbitrary signatures: We show that, for unary inclusion dependencies and functional dependencies, the finiteness assumption of FQA can be lifted up to taking the finite implication closure of the dependencies. Our result relies on new techniques to construct finite universal models of such constraints for any bound on the maximal query size. |
| spellingShingle | Amarilli, A Benedikt, M Finite open-world query answering with number restrictions |
| title | Finite open-world query answering with number restrictions |
| title_full | Finite open-world query answering with number restrictions |
| title_fullStr | Finite open-world query answering with number restrictions |
| title_full_unstemmed | Finite open-world query answering with number restrictions |
| title_short | Finite open-world query answering with number restrictions |
| title_sort | finite open world query answering with number restrictions |
| work_keys_str_mv | AT amarillia finiteopenworldqueryansweringwithnumberrestrictions AT benediktm finiteopenworldqueryansweringwithnumberrestrictions |