Rewriting the infinite chase
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...
| Huvudupphovsmän: | , , , , |
|---|---|
| Materialtyp: | Conference item |
| Språk: | English |
| Publicerad: |
Association for Computing Machinery
2022
|
| _version_ | 1826308889332678656 |
|---|---|
| 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 GTGDs
are transformed to a Datalog program that entails the same base
facts on each base instance. We show that the rewriting can be
seen as containing “shortcut” rules that circumvent certain chase
steps, we present several algorithms that compute the rewriting by
simulating specific types of chase steps, 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-03-07T07:25:58Z |
| format | Conference item |
| id | oxford-uuid:9a03b3c0-1c3e-4ddb-877c-7f830daf8cab |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:25:58Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:9a03b3c0-1c3e-4ddb-877c-7f830daf8cab2022-11-11T10:52:17ZRewriting the infinite chaseConference itemhttp://purl.org/coar/resource_type/c_5794uuid:9a03b3c0-1c3e-4ddb-877c-7f830daf8cabEnglishSymplectic ElementsAssociation for Computing Machinery2022Benedikt, 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 GTGDs are transformed to a Datalog program that entails the same base facts on each base instance. We show that the rewriting can be seen as containing “shortcut” rules that circumvent certain chase steps, we present several algorithms that compute the rewriting by simulating specific types of chase steps, 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 |
| title | Rewriting the infinite chase |
| title_full | Rewriting the infinite chase |
| title_fullStr | Rewriting the infinite chase |
| title_full_unstemmed | Rewriting the infinite chase |
| title_short | Rewriting the infinite chase |
| title_sort | rewriting the infinite chase |
| work_keys_str_mv | AT benediktm rewritingtheinfinitechase AT buronm rewritingtheinfinitechase AT germanos rewritingtheinfinitechase AT kappelmannk rewritingtheinfinitechase AT motikb rewritingtheinfinitechase |