BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260917T123629Z
UID:Seminar-dept-350@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20140515T110000
DTEND:20140515T120000
SUMMARY:School Seminar Series
DESCRIPTION:Dr Hubie Chen: The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity\n\nConjunctive queries are the most basic and heavily studied database queries. The complexity of evaluating a conjunctive query on a relational database has been, since the landmark work of Chandra and Merlin (1977), a research subject of persistent and enduring interest. This evaluation problem is equivalent to a number of well-known problems, including conjunctive query containment, the homomorphism problem on relational structures, and the constraint satisfaction problem. Correspondingly, studies of this problem have come from a wide variety of perspectives and motivations.\n\n\n\nIn this work, we perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity.  We classify sets of conjunctive queries according to the complexity of this problem.  Previous work showed that a set of conjunctive queries is fixed-parameter tractable precisely when the set is equivalent to a set of queries having bounded treewidth. We present a fine classification of query sets up to parameterized logarithmic space reduction.  We show that, in the bounded treewidth regime, there are three complexity degrees and that the properties that determine the degree of a query set are bounded pathwidth and bounded tree depth.\n\n\n\nAfter presenting this classification theorem, we engage in a study of the two higher degrees via logarithmic space machine characterizations and complete problems.  Our work yields a significantly richer perspective on the complexity of conjunctive queries and, at the same time, suggests new avenues of research in parameterized complexity.\n\n\n\nWe will end by discussing recent work that obtains a broad, unifying perspective on and generalization of the discussed classifications. This work makes use of a novel variant of the well-known notion of tree decomposition which we call graph deconstruction.\n\n\n\nThis talk is based on PODS '13 and LICS '14 articles.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=350
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR