Login
Talks & Seminars
Title: Structural Tractability of Counting Solutions to Conjunctive Queries
Prof. Arnaud Durand, University Denis Diderot - Paris
Date & Time: November 20, 2013 15:15
Venue: CFDVS Conference Room, Basement, Department of Mathematics
Abstract:
Computing aggregates such as the sum or the counting of solutions is a natural task in databases. Conjunctive queries are a basic class of queries equivalent to select-project-join queries and strongly related to constraint satisfaction problems. Most research on conjunctive queries has focused on the so-called boolean conjunctive query problem, short CQ, which is, given a query and a database, to decide if the query has any answers with respect to the database. While CQ is hard in general, many 'islands of tractability' have been found based on the hypergraphs associated to queries. Recently, Pichler and Skritek have shown that these hypergraph based techniques are not sufficient to guarantee tractability for the associated counting problem #CQ, i.e., given a conjunctive query and a database, determine the number of answers to the query. I will give a short introduction into conjunctive queries and survey know results. I will also present an exact characterizion of the tractability frontier for #CQ for well-known classes of conjunctive queries. Joint works with Stefan Mengel (JCSS and ICDT 2013). References: 1. Arnaud Durand, Stefan Mengel: Structural tractability of counting of solutions to conjunctive queries. ICDT 2013: 81-92 2. Arnaud Durand, Stefan Mengel: The complexity of weighted counting for acyclic conjunctive queries. J. Comput. Syst. Sci. 80(1): 277-296 (2014)
Speaker Profile:
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback