Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909020637364224 |
|---|---|
| author | Tsamoura, Efthymia Motik, Boris |
| author_facet | Tsamoura, Efthymia Motik, Boris |
| contents | In this paper we present the first goal-driven query answering technique for first- and second-order dependencies with equality. Our technique transforms the input dependencies so that applying the chase to the output avoids many inferences that are irrelevant to the query. The transformation proceeds in several steps, which comprise the following three novel techniques. First, we present a variant of the singularisation technique by Marnette [59] that can handle function variables and that corrects an incompleteness of a related formulation by ten Cate et al. [73]. Second, we present a relevance analysis technique that can eliminate dependencies that provably do not contribute to query answers. Third, we present a variant of the magic sets algorithm [19] that can handle second-order dependencies with equality. We also present the results of an extensive empirical evaluation, which show that goal-driven query answering can be orders of magnitude faster than computing the full universal model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09125 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality Tsamoura, Efthymia Motik, Boris Artificial Intelligence Databases Logic in Computer Science F.4.1; I.2.4 In this paper we present the first goal-driven query answering technique for first- and second-order dependencies with equality. Our technique transforms the input dependencies so that applying the chase to the output avoids many inferences that are irrelevant to the query. The transformation proceeds in several steps, which comprise the following three novel techniques. First, we present a variant of the singularisation technique by Marnette [59] that can handle function variables and that corrects an incompleteness of a related formulation by ten Cate et al. [73]. Second, we present a relevance analysis technique that can eliminate dependencies that provably do not contribute to query answers. Third, we present a variant of the magic sets algorithm [19] that can handle second-order dependencies with equality. We also present the results of an extensive empirical evaluation, which show that goal-driven query answering can be orders of magnitude faster than computing the full universal model. |
| title | Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality |
| topic | Artificial Intelligence Databases Logic in Computer Science F.4.1; I.2.4 |
| url | https://arxiv.org/abs/2412.09125 |