Dichotomy for Axiomatising Inclusion Dependencies on K-Databases
2026-02-20 • Databases
DatabasesLogic in Computer Science
AI summaryⓘ
The authors study a type of database where each entry is tagged with values from a structure called a monoid, focusing on how certain rules called inclusion dependencies apply. They find two main cases based on the monoid's properties: if it is weakly cancellative, usual rules fully describe when dependencies hold; if not, some extra rules including a 'weak symmetry' rule are needed. They also show that if we require the total weights in the database to be equal (like probabilities), an additional 'balance' rule is necessary. Their work clarifies which axioms are sufficient to understand inclusion rules in these generalized databases.
K-relationmonoidinclusion dependenciesK-databaseweakly cancellativeweakly absorptiveaxiomatisationimplication problemweak symmetry axiombalance axiom
Authors
Miika Hannula, Teymur Ismikhanov, Jonni Virtema
Abstract
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 inclusion dependencies over K-databases, where K is a positive commutative monoid. We establish a dichotomy regarding the axiomatisation of the entailment of inclusion dependencies over K-databases, based on whether the monoid K is weakly absorptive or weakly cancellative. We establish that, if the monoid is weakly cancellative then the standard axioms of inclusion dependencies are sound and complete for the implication problem. If the monoid is not weakly cancellative, it is weakly absorptive and the standard axioms of inclusion dependencies together with the weak symmetry axiom are sound and complete for the implication problem. In addition, we establish that the so-called balance axiom is further required, if one stipulates that the joint weights of each K-relation of a K-database need to be the same; this generalises the notion of a K-relation being a distribution. In conjunction with the balance axiom, weak symmetry axiom boils down to symmetry.