13 papers
Aspects of Coherence in Dependence Logic
Timon Barlag, Nicolas Fröhlich, Miika Hannula +4
Dependence logic extends first-order logic with dependence atoms asserting that the value of a variable is determined by the values of certain other variables. The semantics of dep…
Semijoins of Annotated Relations
Phokion G. Kolaitis
The semijoin operation is a fundamental operation of relational algebra that has been extensively used in query processing. Furthermore, semijoins have been used to formulate desir…
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…
Rewriting Consistent Answers on Annotated Data
Phokion G. Kolaitis, Nina Pardal, Jonni Virtema +1
We embark on a study of the consistent answers of queries over databases annotated with values from a naturally ordered positive semiring. In this setting, the consistent answers o…
Characterizing Data Dependencies Then and Now
Phokion G. Kolaitis, Andreas Pieris
Data dependencies are integrity constraints that the data of interest must obey. During the 1980s, Janos Makowsky made a number of contributions to the study of data dependencies;…
On the Number of Quantifiers Needed to Define Boolean Functions
Marco Carmosino, Ronald Fagin, Neil Immerman +3
The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binar…
Parallel Play Saves Quantifiers
Marco Carmosino, Ronald Fagin, Neil Immerman +4
The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear o…
Consistency of Relations over Monoids
Albert Atserias, Phokion G. Kolaitis
The interplay between local consistency and global consistency has been the object of study in several different areas, including probability theory, relational databases, and quan…