BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20261028T185135Z
UID:Seminar-verification-1522@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Patrick Totzke:MAILTO:totzke@liverpool.ac.uk
DTSTART:20261029T110000
DTEND:20261029T120000
SUMMARY:Verification Series
DESCRIPTION:Sam Thompson: Tight width minimisation of self-join-free quantified conjunctive queries\n\nQuery minimisation is a classical problem in database theory and the width of a formula, defined as the maximum number of free variables over all subformulae, is a central measure for query evaluation. This talk will consider width minimisation for a subclass of quantified conjunctive queries (QCQs), namely self-join-free QCQs. I'll present a result that, for this class, rewriting optimality coincides with semantic optimality: given a query φ, the minimum-width query obtainable from φ by applying natural and established rewriting rules has minimum width among all first-order formulae logically equivalent to φ. As a consequence, the width of a self-join-free QCQ can be optimised by a logical-equivalence-preserving rewriting algorithm.\n\n\n\n(This is based on joint work with Hubie Chen and Fabio Mogavero, to appear at PODS 2027.)\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1522
LOCATION:Ashton 208
END:VEVENT
END:VCALENDAR