Rewriting the infinite chase for guarded TGDs
Guarded tuple-generating dependencies (GTGDs) are a natural extension of description logics and referential constraints. It has long been known that queries over GTGDs can be answered by a variant of the chase—a quintessential technique for reasoning with dependencies. However, there has been little...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2024
|
| _version_ | 1811141157938266112 |
|---|---|
| author | Benedikt, M Buron, M Germano, S Kappelmann, K Motik, B |
| author_facet | Benedikt, M Buron, M Germano, S Kappelmann, K Motik, B |
| author_sort | Benedikt, M |
| collection | OXFORD |
| description | Guarded tuple-generating dependencies (GTGDs) are a natural extension of description logics and referential
constraints. It has long been known that queries over GTGDs can be answered by a variant of the chase—a
quintessential technique for reasoning with dependencies. However, there has been little work on concrete
algorithms and even less on implementation. To address this gap, we revisit Datalog rewriting approaches to
query answering, where a set of GTGDs is transformed to a Datalog program that entails the same base facts
on each base instance. We show that a rewriting consists of “shortcut” rules that circumvent certain chase
steps, we present several algorithms that compute a rewriting by deriving such “shortcuts” efficiently, and
we discuss important implementation issues. Finally, we show empirically that our techniques can process
complex GTGDs derived from synthetic and real benchmarks and are thus suitable for practical use. |
| first_indexed | 2024-09-25T04:33:25Z |
| format | Journal article |
| id | oxford-uuid:66051147-8cd7-4d31-9160-abe3c17772c5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:33:25Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:66051147-8cd7-4d31-9160-abe3c17772c52024-09-10T09:40:53ZRewriting the infinite chase for guarded TGDsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:66051147-8cd7-4d31-9160-abe3c17772c5EnglishSymplectic ElementsAssociation for Computing Machinery2024Benedikt, MBuron, MGermano, SKappelmann, KMotik, BGuarded tuple-generating dependencies (GTGDs) are a natural extension of description logics and referential constraints. It has long been known that queries over GTGDs can be answered by a variant of the chase—a quintessential technique for reasoning with dependencies. However, there has been little work on concrete algorithms and even less on implementation. To address this gap, we revisit Datalog rewriting approaches to query answering, where a set of GTGDs is transformed to a Datalog program that entails the same base facts on each base instance. We show that a rewriting consists of “shortcut” rules that circumvent certain chase steps, we present several algorithms that compute a rewriting by deriving such “shortcuts” efficiently, and we discuss important implementation issues. Finally, we show empirically that our techniques can process complex GTGDs derived from synthetic and real benchmarks and are thus suitable for practical use. |
| spellingShingle | Benedikt, M Buron, M Germano, S Kappelmann, K Motik, B Rewriting the infinite chase for guarded TGDs |
| title | Rewriting the infinite chase for guarded TGDs |
| title_full | Rewriting the infinite chase for guarded TGDs |
| title_fullStr | Rewriting the infinite chase for guarded TGDs |
| title_full_unstemmed | Rewriting the infinite chase for guarded TGDs |
| title_short | Rewriting the infinite chase for guarded TGDs |
| title_sort | rewriting the infinite chase for guarded tgds |
| work_keys_str_mv | AT benediktm rewritingtheinfinitechaseforguardedtgds AT buronm rewritingtheinfinitechaseforguardedtgds AT germanos rewritingtheinfinitechaseforguardedtgds AT kappelmannk rewritingtheinfinitechaseforguardedtgds AT motikb rewritingtheinfinitechaseforguardedtgds |