– Titre: Enumeration and Related Problems in Query Answering:
– Résumé: When analyzing the complexity of answering queries over databases, the traditional approach asks for the total time required to compute all answers. As the number of answers may be much larger than the size of the input database, there has been a focus on analyzing this task from an enumeration point of view, i.e. bounding the delay between successive answers when they are returned one by one. The motivation here is that we can get value from seeing some of the answers before all of them are produced. A more recent shift takes this approach a step forward. Depending on the final goal of the query, we can save a significant amount of computation by solving enumeration-related problems that do not produce the entire solution set. As an example, simulating random access to a sorted list of query answers can be used to efficiently compute quantiles of the query answers. This talk will inspect enumeration-related problems in databases from a fine-grained complexity point of view and discuss their connection to enumeration.
Room 02/124.
