Enumerazione e "direct access": la complessità temporale di ottenere informazioni rilevanti da un database

Collecting and processing data are among the main purposes of computing. Data is usually stored in databases, that we can imagine as collections of big tables containing constant values. Obtaining information from a database becomes more difficult and time consuming as its size grows. Employing the tools of mathematical logic, we can formalize the notions of database and of conjunctive query. The class of conjunctive queries is a notable fragment of first-order logic consisting of questions we can formulate about the data. A remarkable work in this field is J. Brault-Baron's doctorate thesis, where a representation of conjunctive queries as hypergraphs is used to classify the time complexity of enumerating their answers. These answers are computed in a certain order, which suggests a further question: how can we access a relevant part of the answers to a database query more efficiently than by computing all answers? This question was tackled by N. Carmeli et al. in a seminal paper, where the problem of direct access and the related tasks of selection and inverted access are analysed. Although the main results that appear in this thesis have already been addressed in literature, here they are reorganized in a uniform discourse and some arguments are clarified through original proofs.

La raccolta e l'elaborazione di dati sono tra gli scopi principali dell'informatica. Solitamente i dati si archiviano in database, che possiamo immaginare come raccolte di grandi tabelle contenenti valori costanti. Ottenere informazioni da un database diventa più complesso e richiede più tempo man mano che le sue dimensioni aumentano. Utilizzando gli strumenti della logica matematica, possiamo formalizzare le nozioni di database e di "conjunctive query". La classe delle "conjunctive queries" è un frammento notevole della logica del prim'ordine, costituito da domande che possiamo formulare sui dati. Un lavoro notevole in questo campo è la tesi di dottorato di J. Brault-Baron, in cui una rappresentazione delle "conjunctive queries" come ipergrafi è utilizzata per classificare la complessità temporale dell'enumerazione delle loro risposte. Queste risposte vengono trovate in un certo ordine e questo suggerisce un'ulteriore domanda: come possiamo accedere a una parte rilevante delle risposte a una "database query" in modo più efficiente che calcolando tutte le risposte? Questa domanda è stata affrontata da N. Carmeli et al. in un articolo seminale, in cui vengono analizzati il ​​problema del "direct access" e i problemi correlati della selezione e dell'"inverted access". Sebbene i principali risultati che compaiono in questa tesi siano già stati affrontati in letteratura, qui sono riorganizzati in un discorso uniforme e alcuni argomenti sono chiariti attraverso dimostrazioni originali.