7 papers
Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions
Albert Atserias, Phokion G. Kolaitis
During the early days of relational database theory it was realized that "acyclic" database schemas possess a number of desirable semantic properties. In fact, three different noti…
Disjunctions of Two Dependence Atoms
Nicolas Fröhlich, Phokion G. Kolaitis, Arne Meier
Dependence logic is a formalism that augments the syntax of first-order logic with dependence atoms asserting that the value of a variable is determined by the values of some other…
Who Wins the Multi-Structural Game?
Ronald Fagin, Neil Immerman, Phokion Kolaitis +2
Combinatorial games played between two players, called Spoiler and Duplicator, have often been used to capture syntactic properties of formal logical languages. For instance, the w…
Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
Balder ten Cate, Phokion G. Kolaitis, Arnar Á. Kristjánsson
A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query a…
Query Repairs
Balder ten Cate, Phokion Kolaitis, Carsten Lutz
We formalize and study the problem of repairing database queries based on user feedback in the form of a collection of labeled examples. We propose a framework based on the notion…
Codd's Theorem for Databases over Semirings
Guillermo Badia, Phokion G. Kolaitis, Carles Noguera
Codd's Theorem, a fundamental result of database theory, asserts that relational algebra and relational calculus have the same expressive power on relational databases. We explore…