Datalog rewriting for Guarded TGDs
We deal with the problem of fact entailment with respect to a database and a set of integrity constraints, focusing on the case of Guarded tuple-generating dependencies (GTGDs). The original approach to the problem in the literature is via forward reasoning or "chasing", where one complete...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
CEUR Workshop Proceedings
2022
|
| _version_ | 1826310145443889152 |
|---|---|
| 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 | We deal with the problem of fact entailment with respect to a database and a set of integrity constraints, focusing on the case of Guarded tuple-generating dependencies (GTGDs). The original approach to the problem in the literature is via forward reasoning or "chasing", where one completes the input database by adding fresh elements and facts. This completion process may be infinite, but in the case of GTGDs it is known that one can compute a point where the chase can be cut off without missing any base facts. Another approach is by forming an automaton and checking it for emptiness. Neither of these approaches scales to large input datasets. An alternative approach is to <i>rewrite the constraints into Datalog</i>: the Datalog rewriting can be generated in advance of any dataset and will produce the same base facts as the original constraints. It is known that Datalog rewritings always exist. But to our knowledge the approach has never been implemented. In this work we overview effective algorithms to Datalog rewriting of GTGDs. This presents work that will appear in VLDB 2022. |
| first_indexed | 2024-03-07T07:47:45Z |
| format | Conference item |
| id | oxford-uuid:f6b724d6-bb1c-4c35-a9ea-b71e541c0641 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:47:45Z |
| publishDate | 2022 |
| publisher | CEUR Workshop Proceedings |
| record_format | dspace |
| spelling | oxford-uuid:f6b724d6-bb1c-4c35-a9ea-b71e541c06412023-06-09T11:03:34ZDatalog rewriting for Guarded TGDsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:f6b724d6-bb1c-4c35-a9ea-b71e541c0641EnglishSymplectic ElementsCEUR Workshop Proceedings2022Benedikt, MBuron, MGermano, SKappelmann, KMotik, BWe deal with the problem of fact entailment with respect to a database and a set of integrity constraints, focusing on the case of Guarded tuple-generating dependencies (GTGDs). The original approach to the problem in the literature is via forward reasoning or "chasing", where one completes the input database by adding fresh elements and facts. This completion process may be infinite, but in the case of GTGDs it is known that one can compute a point where the chase can be cut off without missing any base facts. Another approach is by forming an automaton and checking it for emptiness. Neither of these approaches scales to large input datasets. An alternative approach is to <i>rewrite the constraints into Datalog</i>: the Datalog rewriting can be generated in advance of any dataset and will produce the same base facts as the original constraints. It is known that Datalog rewritings always exist. But to our knowledge the approach has never been implemented. In this work we overview effective algorithms to Datalog rewriting of GTGDs. This presents work that will appear in VLDB 2022. |
| spellingShingle | Benedikt, M Buron, M Germano, S Kappelmann, K Motik, B Datalog rewriting for Guarded TGDs |
| title | Datalog rewriting for Guarded TGDs |
| title_full | Datalog rewriting for Guarded TGDs |
| title_fullStr | Datalog rewriting for Guarded TGDs |
| title_full_unstemmed | Datalog rewriting for Guarded TGDs |
| title_short | Datalog rewriting for Guarded TGDs |
| title_sort | datalog rewriting for guarded tgds |
| work_keys_str_mv | AT benediktm datalogrewritingforguardedtgds AT buronm datalogrewritingforguardedtgds AT germanos datalogrewritingforguardedtgds AT kappelmannk datalogrewritingforguardedtgds AT motikb datalogrewritingforguardedtgds |