Evènement pour le groupe Séminaire Méthodes Formelles


Date 2021-03-02  07:00-07:00
TitreThe Complexity of Answering Unions of Conjunctive Queries 
RésuméWe discuss the fine-grained complexity of enumerating the answers to a query over a relational database. With the ideal guarantees, linear time is required before the first answer to read the input and determine its existence, and then we need to print the answers one by one. Consequently, we wish to identify the queries that can be solved with linear preprocessing time and constant or logarithmic delay between answers. A known dichotomy classifies CQs into those that admit such enumeration and those that do not. The computationally expensive component of query answering is joining tables, which can be done efficiently if and only if the join query is acyclic. However, the join query usually does not appear in a vacuum; for example, it may be part of a larger query, or it may be applied to a database with dependencies. We inspect how the complexity changes in these settings and chart the borders of tractability within. In addition, we consider the task of enumerating query answers with a uniformly random order, and we propose to do so using an efficient random-access structure for representing the set of answers. We also prove conditional lower bounds showing that our algorithms capture all tractable queries in some cases. Among our results, we show that a union of tractable conjunctive queries may be intractable w.r.t. random access; on the other hand, a union of intractable conjunctive queries may be tractable w.r.t. enumeration. Enregistrement : https://u-bordeaux-fr.zoom.us/rec/share/QOU7TB0aeSrBV5ZpIKNRc2ATR-9p_C0cLYfpjo1-pGGtK48YGrzCdJj_6S4hVTcJ.loUHSiQ8Wr5tVMgW 
LieuOnline 
OrateurNofar Carmeli 
Emailhttps://nofar.carme.li/ 
UrlENS 



Aucun document lié à cet événement.

Retour
Retour à l'index