7 papers
Approximate Functional Dependencies---Implication Problem Revisited
Nicolas Fröhlich, Matilda Häggblom, Åsa Hirvonen +1
Functional dependencies are an important and well-studied class of database constraints that correspond to a notion expressed by dependence atoms in team logic. In practice, data o…
Expressibility and inexpressibility in propositional team logics
Matilda Häggblom, Minna Hirvonen, Jouko Väänänen
We develop dimension theoretic methods for propositional team based logics. Such quantitative methods were defined for team based first-order logic in a recent paper by Hella, Luos…
Implication Problems over Positive Semirings
Minna Hirvonen
We study various notions of dependency in semiring team semantics. Semiring teams are essentially database relations, where each tuple is annotated with some element from a positiv…
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…
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 complexit…