Logic and Algebra for Query Evaluation 2023
2023-11-13..2023-11-21
Berkeley, United States
as the organisers put it
The workshop will discuss semantics of logic programs over general semirings: constraints over semirings, query complexity with semiring semantics, termination conditions of logic programs over semirings. The connection between semirings and logic is a relatively new development in database theory (since 2007), and this area has high potential for major innovation. Some of the problems discussed at the workshop will be inspired by systems, others will be purely theoretical in nature, such as the quest for finding appropriate extensions of Pebble Games to semiring semantics.
who it's for
database researchers, query evaluation researchers, datalog developers, programming language researchers, systems researchers, data provenance researchers, machine learning researchers, constraint solving researchers
topics
semiring provenance and semantics; optimization over semirings; semiring-based constraint solving; omega-continuous Newton method on semirings; conditional instances for queries; certain and possible answers for annotated relations; ranked enumeration via dynamic-programming DAGs; conjunctive queries with aggregation and direct access; equality saturation encoded in Datalog (egglog); neurosymbolic languages and relational algebra; ring-based incremental view maintenance; provenance-based explainability and causal data integration
| title | author | length |
|---|---|---|
| Constrained Optimization Over Semirings | Kuldeep S. Meel | 29m |
Defines OptConf: given propositional F and semiring K, compute the maximum interpretation value. Proves for Viterbi/tropical semirings the problem sits between… | ||
| Semiring-Based Soft Constraint Solving and Argumentation | Stefano Bistarelli | 29m |
Introduces algebraic semirings inside CSPs and argumentation to turn feasibility checks into optimisation over semiring values, defines constraints as… | ||
| Consistency, Acyclicity, and Positive Semirings | Phokion Kolaitis | 38m |
Shows that for positive semiring K annotated relations, every pairwise-consistent family has a global witness exactly when the schema forms an acyclic… | ||
| An Introduction to Newton’s Method on Semirings | Javier Esparza | 47m |
Claims a generalization of Newton's method to polynomial fixpoint systems over omega-continuous semirings that always converges from 0 and whose i‑th… | ||
| Understanding Queries by Conditional Instances | Sudeepa Roy | 29m |
Defines conditional instances—small representative instances with global conditions—that capture distinct ways a domain-relational-calculus query can be… | ||
| Approximating Certain and Possible Answers Beyond Sets | Boris Glavic | 35m |
Generalizes certain and possible answers from set semantics to semiring-annotated relations, proving that lattice-ordered semirings let query evaluation… | ||
| Any-k: Ranked enumeration for Dynamic Programming | Nikos Tziavelis | 32m |
Presents a concrete algorithmic framework that turns dynamic programs into DAG shortest‑path problems so ranked enumeration returns the k‑th best solution with… | ||
| Direct Access for Conjunctive Queries with Aggregation | Nofar Carmeli | 29m |
Characterizes when a lexicographically sorted answer array for conjunctive queries with grouping meets quasi-linear preprocessing and logarithmic access… | ||
| Semiring Semantics | Erich Graedel | 01h 06m |
Semiring semantics evaluates formulas in commutative semirings so truth becomes annotated values; negation is handled by translating to negation normal form… | ||
| Logic and Algebras for Distributed Computing: Applications and Open Questions | Joe Hellerstein, Conor Power | 01h 01m |
Vision and prototypes present a concrete stack: translate Daedalus programs into a Hydro/Hydroflow IR, compile with e-graph style rewrites (Egg/Egglog) into… | ||
| Datalog and Equality Saturation | Max Willsey | 01h 01m |
Claims that equality saturation can be encoded as Datalog while keeping the congruence closure algorithm work in practice lead to a concrete system and… | ||
| Deep Learning and the Relational Algebra | Zack Ives | 32m |
The work extends a standard relational model with a tensor data type and neural operators, treats autograd via a gradient semiring, and implements a prototype… | ||
| Factorized Graph Neural Networks (With Some Algebraic Cheating) | Wolfgang Gatterbauer | 29m |
Claims a method called distant compatibility estimation that recovers class compatibilities from extremely sparse labels (examples down to 1 in 10,000) by… | ||
| Scallop: A Language for Neurosymbolic Programming | Mayur Naik, Ziyang Li, Jiani Huang | 35m |
A Datalog-based language and compiler called Scallop combines a neural module for perception with a declarative logic layer and a differentiable provenance… | ||
| Algorithmic Aspects of Semiring Provenance for Stratified Datalog | Matthias Naaf | 28m |
Claim: greatest fixed points of polynomial operators over absorptive semirings with continuity can be computed in polynomial time by iterating n steps… | ||
| A (Semi)Ring-Based Query Algebra for Incremental View Maintenance and Query Compilation | Christoph Koch | 33m |
Argues that queries form a polynomial algebra over avalanche (semi)rings so deltas become algebraic derivatives and the k-th deltas depend only on the update… | ||
| A Unified Approach for Reverse Data Management Problems | Neha Makhija | 28m |
Proposes a concrete encoding of reverse data management problems as an ILP encoding whose LP relaxation matches the ILP on all known PTIME cases so solvers… | ||
| Circuits for Querying Trees: A Little Survey | Pierre Bourhis | 32m |
Claims that MSO tree queries compile to Boolean circuits (a smooth d-DNNF or a zero-suppressed semantic d-DNNF) via tree automata construction in time linear… | ||
| Logical Interfaces to Data, Beyond Views | Michael Benedikt | 35m |
Proposes replacing exported views with two interface specs: a set of utility queries users must be able to answer and an equivalence on instances that users… | ||
| Towards Interpretable Data Science | Daniel Deutch | 33m |
Argues that explanations must run across the data science cycle and gives concrete systems and numbers: uses Shapley values over provenance compiled into… | ||
| Measuring the Importance of Database Elements | Benny Kimelfeld | 31m |
Shows that tuple-importance and parameter-importance are formalized as cooperative games with database tuples or query parameters as players, and that… | ||
| Causal Data Integration | Brit Youngmann | 28m |
Proposes Causal Data Integration: an automated pipeline that mines unobserved attributes from knowledge graphs, joins hundreds of candidates to an input table… | ||
| Towards Interpretable Data Science | Daniel Deutch | 35m |
Argues that explanations must run through the whole data‑science cycle and demonstrates concrete tools: uses Shapley values with provenance and knowledge… | ||
| Achieving Understandability and Privacy With Provenance-Based Explanations | Amir Gilad | 30m |
Describes two concrete systems: a pipeline that turns value-level provenance into concise natural-language justifications by using NaLIR plus the provenance… | ||
| nothing matches | ||