Direct Access for Conjunctive Queries with Negation
summary
Direct access for conjunctive queries with negation becomes possible by compiling the query+database into an ordered decision circuit that is polynomial-size in the database for the tractable classes described, tagging decision gates with small count tables. Construction runs in linear preprocessing (in the database) and poly(query) time; answering the jth tuple uses the tables to pick variable values and runs in polylog access (domain-size) per value written. Technique recovers positive acyclic results and yields new tractable islands (beta-acyclic negatives, bounded nested-width); tree-structured circuits provably blow up for some negative queries.
AI-written summary · about
chapters (16)
- 0:00Direct access in database theory
- 2:10Problem definition
- 5:47Tractable query classes
- 8:17Acyclic queries and join trees
- 12:17Counting solutions with Yannakakis
- 14:09Direct access for α-acyclic queries
- 18:28α elimination and acyclicity
- 21:19Circuit approach for databases
- 23:27Ordered decision circuits
- 27:50Building circuits via DPLL
- 30:19Circuit construction with α elimination
- 31:02Direct access on ordered circuits
- 36:49Join tree vs circuit approaches
- 37:31Beta acyclicity and negation
- 38:58Signed conjunctive queries
- 39:45Q&A
related talks
29mDirect Access for Conjunctive Queries with Aggregation
43mA Dichotomy for Queries with Negation in Probabilistic Databases
19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II
01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
32mCircuits for Querying Trees: A Little Survey
28mThe Logic of Counting Query Answers
20mPolygon: Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search
35mApproximating Certain and Possible Answers Beyond Sets