8 papers
Getting to the Root: A Combined Complexity Perspective on Consistent Query Answering
Miika Hannula
The data complexity of consistent query answering has been extensively studied over the past two decades. In this paper, we study its combined complexity, which has gained less att…
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…
Locally Consistent K-relations: Entailment and Axioms of Functional Dependence
Timon Barlag, Miika Hannula, Juha Kontinen +2
Local consistency arises in diverse areas, including Bayesian statistics, relational databases, and quantum foundations, and so does the notion of functional dependence. We adopt a…
Dichotomy for Axiomatising Inclusion Dependencies on K-Databases
Miika Hannula, Teymur Ismikhanov, Jonni Virtema
A relation consisting of tuples annotated by an element of a monoid K is called a K-relation. A K-database is a collection of K-relations. In this paper, we study entailment of inc…
Independence Under Incomplete Information
Miika Hannula, Minna Hirvonen, Juha Kontinen +1
We initiate an investigation how the fundamental concept of independence can be represented effectively in the presence of incomplete information in relational databases. The conce…
Logical Approaches to Non-deterministic Polynomial Time over Semirings
Timon Barlag, Nicolas Fröhlich, Teemu Hankala +6
We provide a logical characterization of non-deterministic polynomial time defined by BSS machines over semirings via existential second-order logic interpreted in the semiring sem…