Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Direct Access for Conjunctive Queries with Negation

Simons Institute via YouTube

Overview

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.

Syllabus

Direct Access for Conjunctive Queries with Negation

Taught by

Simons Institute

Reviews

Start your review of Direct Access for Conjunctive Queries with Negation

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.