Direct Access for Conjunctive Queries with Negations

Capelli, Florent; Irwin, Oliver

Document type :

Communication dans un congrès avec actes

DOI :

10.4230/LIPIcs.ICDT.2024.13

Title :

Direct Access for Conjunctive Queries with Negations

Author(s) :

Capelli, Florent [Auteur]

Centre de Recherche en Informatique de Lens [CRIL]
Irwin, Oliver [Auteur]
Linking Dynamic Data [LINKS]

Conference title :

International Conference on Database Theory

City :

Paestum

Country :

Italie

Start date of the conference :

2024-03-24

Publisher :

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Publication date :

2024

English keyword(s) :

Conjunctive queries
factorized databases
direct access
hypertree decomposition

HAL domain(s) :

Informatique [cs]/Base de données [cs.DB]

English abstract : [en]

Given a conjunctive query $Q$ and a database $\mathbf{D}$, a direct access to the answers of $Q$ over $\mathbf{D}$ is the operation of returning, given an index $j$, the $j^{\mathsf{th}}$ answer for some order on its ...
Show more >Given a conjunctive query $Q$ and a database $\mathbf{D}$, a direct access to the answers of $Q$ over $\mathbf{D}$ is the operation of returning, given an index $j$, the $j^{\mathsf{th}}$ answer for some order on its answers. While this problem is $\#\mathsf{P}$-hard in general with respect to combined complexity, many conjunctive queries have an underlying structure that allows for a direct access to their answers for some lexicographical ordering that takes polylogarithmic time in the size of the database after a polynomial time precomputation. Previous work has precisely characterised the tractable classes and given fine-grained lower bounds on the precomputation time needed depending on the structure of the query. In this paper, we generalise these tractability results to the case of signed conjunctive queries, that is, conjunctive queries that may contain negative atoms. Our technique is based on a class of circuits that can represent relational data. We first show that this class supports tractable direct access after a polynomial time preprocessing. We then give bounds on the size of the circuit needed to represent the answer set of signed conjunctive queries depending on their structure. Both results combined together allow us to prove the tractability of direct access for a large class of conjunctive queries. On the one hand, we recover the known tractable classes from the literature in the case of positive conjunctive queries. On the other hand, we generalise and unify known tractability results about negative conjunctive queries -- that is, queries having only negated atoms. In particular, we show that the class of $\beta$-acyclic negative conjunctive queries and the class of bounded nest set width negative conjunctive queries admit tractable direct access.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Compilation de connaissances pour l'analyse de données

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

document
Open access
Access the document

capelli_irwin_2024_direct_access_for_conjunctive_queries_with_negation.pdf
Open access
Access the document

document
Open access
Access the document

capelli_irwin_2024_direct_access_for_conjunctive_queries_with_negation.pdf
Open access
Access the document

Direct Access for Conjunctive Queries with ... BibTeX CSV Excel RIS

Files

Direct Access for Conjunctive Queries with ...

BibTeX

CSV

Excel

RIS