Tractable Conjunctive Queries over Static and Dynamic Relations
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_ | 1866912296928804864 |
|---|---|
| author | Kara, Ahmet Luo, Zheng Nikolic, Milos Olteanu, Dan Zhang, Haozhe |
| author_facet | Kara, Ahmet Luo, Zheng Nikolic, Milos Olteanu, Dan Zhang, Haozhe |
| contents | We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes.
We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant).
To decide whether a query is tractable, it does not suffice to analyse separately the sub-queries over the static relations and over the dynamic relations, respectively. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16224 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tractable Conjunctive Queries over Static and Dynamic Relations Kara, Ahmet Luo, Zheng Nikolic, Milos Olteanu, Dan Zhang, Haozhe Databases H.2.4 We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes. We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant). To decide whether a query is tractable, it does not suffice to analyse separately the sub-queries over the static relations and over the dynamic relations, respectively. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones. |
| title | Tractable Conjunctive Queries over Static and Dynamic Relations |
| topic | Databases H.2.4 |
| url | https://arxiv.org/abs/2404.16224 |