21 citations · 72 across the 28 of their papers we have counts for
36 papers
Getting to the Root: A Combined Complexity Perspective on Consistent Query Answering
Miika Hannula
We study the combined complexity of consistent query answering for Boolean self-join-free conjunctive queries with unary primary keys and acyclic attack graphs. Although every fixe…
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…
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…
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…
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…
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…
Logic and Computation through the Lens of Semirings
Timon Barlag, Nicolas Fröhlich, Teemu Hankala +6
We study the expressivity and computational aspects of first-order logic and its extensions in the semiring semantics developed by Grädel and Tannen. We characterize the complexity…
Parameterised Complexity of Consistent Query Answering via Graph Representations
Teemu Hankala, Miika Hannula, Yasir Mahmood +1
We study consistent query answering via different graph representations. First, we introduce solution-conflict hypergraphs in which nodes represent facts and edges represent either…
Conditional independence on semiring relations
Miika Hannula
Conditional independence plays a foundational role in database theory, probability theory, information theory, and graphical models. In databases, conditional independence appears…
Information inequality problem over set functions
Miika Hannula
Information inequalities appear in many database applications such as query output size bounds, query containment, and implication between data dependencies. Recently Khamis et al.…
Logics with probabilistic team semantics and the Boolean negation
Miika Hannula, Minna Hirvonen, Juha Kontinen +3
We study the expressivity and the complexity of various logics in probabilistic team semantics with the Boolean negation. In particular, we study the extension of probabilistic ind…
Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions
Teemu Hankala, Miika Hannula, Juha Kontinen +1
We study the complexity of the problem of training neural networks defined via various activation functions. The training problem is known to be existsR-complete with respect to li…
Unified Foundations of Team Semantics via Semirings
Timon Barlag, Miika Hannula, Juha Kontinen +2
Semiring semantics for first-order logic provides a way to trace how facts represented by a model are used to deduce satisfaction of a formula. Team semantics is a framework for st…
A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys
Miika Hannula, Jef Wijsen
Since 2005, significant progress has been made in the problem of Consistent Query Answering (CQA) with respect to primary keys. In this problem, the input is a database instance th…
On elementary logics for quantitative dependencies
Miika Hannula, Minna Hirvonen, Juha Kontinen
We define and study logics in the framework of probabilistic team semantics and over metafinite structures. Our work is paralleled by the recent development of novel axiomatizable…
An Algorithm for the Discovery of Independence from Data
Miika Hannula, Bor-Kuan Song, Sebastian Link
For years, independence has been considered as an important concept in many disciplines. Nevertheless, we present the first research that investigates the discovery problem of inde…
Controlling Entity Integrity with Key Sets
Miika Hannula, Xinyi Li, Sebastian Link
Codd's rule of entity integrity stipulates that every table has a primary key. Hence, the attributes of the primary key carry unique and complete value combinations. In practice, d…
On the Interaction of Functional and Inclusion Dependencies with Independence Atoms
Miika Hannula, Juha Kontinen, Sebastian Link
Infamously, the finite and unrestricted implication problems for the classes of i) functional and inclusion dependencies together, and ii) embedded multivalued dependencies alone a…
Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
Miika Hannula, Jonni Virtema
Probabilistic team semantics is a framework for logical analysis of probabilistic dependencies. Our focus is on the axiomatizability, complexity, and expressivity of probabilistic…
On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic
Miika Hannula, Juha Kontinen, Martin Lück +1
Second-order Boolean logic is a generalization of QBF, whose constant alternation fragments are known to be complete for the levels of the exponential time hierarchy. We consider t…
Descriptive complexity of real computation and probabilistic independence logic
Miika Hannula, Juha Kontinen, Jan Van den Bussche +1
We introduce a novel variant of BSS machines called Separate Branching BSS machines (S-BSS in short) and develop a Fagin-type logical characterisation for languages decidable in no…
Complexity Thresholds in Inclusion Logic
Miika Hannula, Lauri Hella
Logics with team semantics provide alternative means for logical characterization of complexity classes. Both dependence and independence logic are known to capture non-determinist…
Facets of Distribution Identities in Probabilistic Team Semantics
Miika Hannula, Åsa Hirvonen, Juha Kontinen +2
We study probabilistic team semantics which is a semantical framework allowing the study of logical and probabilistic dependencies simultaneously. We examine and classify the expre…
Probabilistic team semantics
Arnaud Durand, Miika Hannula, Juha Kontinen +2
Team semantics is a semantical framework for the study of dependence and independence concepts ubiquitous in many areas such as databases and statistics. In recent works team seman…