Direct Access for Conjunctive Queries with Negation

Explore a comprehensive lecture on direct access for conjunctive queries with negation, presented by Florent Capelli from Université d'Artois, CNRS, CRIL. Delve into the concept of Direct Access, which involves retrieving the jth answer of a conjunctive query on a database for a given order. Discover how certain conjunctive queries can be structured to allow polylogarithmic time direct access after polynomial time precomputation, despite the general #P-hardness of the problem. Examine the generalization of tractability results to signed conjunctive queries, including those with negative atoms. Learn about the technique of solving ranked access for circuits representing relational data, and how this approach recovers known tractable classes for positive conjunctive queries while uncovering new areas of tractability for signed conjunctive queries. Gain insights into how this work extends the Ranked Access Problem to include known tractabilities of counting answers to beta-acyclic negative queries and deciding the existence of answers for negative queries with bounded nested-width. Understand the collaborative nature of this research, conducted jointly with Oliver Irwin, and its implications for the field of probabilistic circuits and logic.

Direct Access for Conjunctive Queries with Negation