Acyclicity notions for existential rules and their application to query answering in ontologies
Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the...
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Journal article |
| Lingua: | English |
| Pubblicazione: |
Association for the Advancement of Artificial Intelligence
2013
|
| _version_ | 1826311840250986496 |
|---|---|
| author | Grau, B Horrocks, I Krötzsch, M Kupke, C Magka, D Motik, B Wang, Z |
| author_facet | Grau, B Horrocks, I Krötzsch, M Kupke, C Magka, D Motik, B Wang, Z |
| author_sort | Grau, B |
| collection | OXFORD |
| description | Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions. |
| first_indexed | 2024-03-07T08:15:39Z |
| format | Journal article |
| id | oxford-uuid:703229aa-38cf-4e4b-8e3f-522b8cd95eed |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:15:39Z |
| publishDate | 2013 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:703229aa-38cf-4e4b-8e3f-522b8cd95eed2024-01-05T09:11:28ZAcyclicity notions for existential rules and their application to query answering in ontologiesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:703229aa-38cf-4e4b-8e3f-522b8cd95eedEnglishSymplectic Elements at OxfordAssociation for the Advancement of Artificial Intelligence2013Grau, BHorrocks, IKrötzsch, MKupke, CMagka, DMotik, BWang, ZAnswering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions. |
| spellingShingle | Grau, B Horrocks, I Krötzsch, M Kupke, C Magka, D Motik, B Wang, Z Acyclicity notions for existential rules and their application to query answering in ontologies |
| title | Acyclicity notions for existential rules and their application to query answering in ontologies |
| title_full | Acyclicity notions for existential rules and their application to query answering in ontologies |
| title_fullStr | Acyclicity notions for existential rules and their application to query answering in ontologies |
| title_full_unstemmed | Acyclicity notions for existential rules and their application to query answering in ontologies |
| title_short | Acyclicity notions for existential rules and their application to query answering in ontologies |
| title_sort | acyclicity notions for existential rules and their application to query answering in ontologies |
| work_keys_str_mv | AT graub acyclicitynotionsforexistentialrulesandtheirapplicationtoqueryansweringinontologies AT horrocksi acyclicitynotionsforexistentialrulesandtheirapplicationtoqueryansweringinontologies AT krotzschm acyclicitynotionsforexistentialrulesandtheirapplicationtoqueryansweringinontologies AT kupkec acyclicitynotionsforexistentialrulesandtheirapplicationtoqueryansweringinontologies AT magkad acyclicitynotionsforexistentialrulesandtheirapplicationtoqueryansweringinontologies AT motikb acyclicitynotionsforexistentialrulesandtheirapplicationtoqueryansweringinontologies AT wangz acyclicitynotionsforexistentialrulesandtheirapplicationtoqueryansweringinontologies |