Extending the (Elementary) Mathematical Data Model and MatBase with two new constraint types: inexistence and anti-existence

Formal definitions, complexity analysis, and MatBase implementation of dual existence constraints

Christian Mancas· 2026· DOI 10.48550/arXiv.2605.24021

The core problem

The (Elementary) Mathematical Data Model (EMDM) provides a rigorous foundation for database constraints. Existing work defines existence and non-existence constraints, which ensure that certain tuples must or must not exist in a relation. This paper introduces two new constraint types—inexistence and anti-existence—that are the duals of existence and non-existence. These constraints expand the expressive power of EMDM by allowing the specification of negative requirements: for example, stating that a particular combination of values must not exist, or that if one tuple exists, another must not. The paper formally defines these constraints, characterizes their properties, and studies the well-formedness, satisfiability, coherence, and minimality of sets containing all seven subtypes of existence constraints. It also presents SQL-embedded pseudocode algorithms for managing these sets, proving them to be of constant complexity, sound, complete, and optimal. Furthermore, algorithms for enforcing inexistence and anti-existence constraints are provided, with linear complexity in the sum of arities of the involved function (Cartesian product)s. All algorithms are implemented in both versi

The paper formally defines two new constraint types: inexistence and anti-existence, each with two subtypes, resulting in four new subtypes. Together with the existing three subtypes of existence constraints, this yields a total of seven subtypes. The formal definitions are accompanied by real-life examples, such as a university database where a student cannot be enrolled in two courses that are scheduled at the same time (an anti-existence constraint). The study of well-formedness, satisfiability, coherence, and minimality reveals that sets of these constraints can be checked efficiently. The management algorithms are proven to be of constant complexity, meaning that adding, removing, or checking a constraint takes time independent of the database size. The enforcement algorithms are proven to have linear complexity in the sum of the arities of the involved function (Cartesian product)s. For example, if a constraint involves two relations with arities 3 and 4, the enforcement time is O (7) . The algorithms are also proven to be sound (they never reject a valid database), complete (they always reject an invalid database), and optimal (no algorithm can do better in the worst case).

The (Elementary) Mathematical Data Model (EMDM) provides a rigorous foundation for database constraints. Existing work defines existence and non-existence constraints, which ensure that certain tuples must or must not exist in a relation. This paper introduces two new constraint types—inexistence and anti-existence—that are the duals of existence and non-existence. These constraints expand the expressive power of EMDM by allowing the specification of negative requirements: for example, stating that a particular combination of values must not exist, or that if one tuple exists, another must not. The paper formally defines these constraints, characterizes their properties, and studies the well-formedness, satisfiability, coherence, and minimality of sets containing all seven subtypes of existence constraints. It also presents SQL-embedded pseudocode algorithms for managing these sets, proving them to be of constant complexity, sound, complete, and optimal. Furthermore, algorithms for enforcing inexistence and anti-existence constraints are provided, with linear complexity in the sum of arities of the involved function (Cartesian product)s. All algorithms are implemented in both versions of MatBase, an intelligent data and knowledge base management system prototype that automatically generates code for enforcing all seven subtypes of existence constraints.

The research methodology follows a formal approach. First, the authors extend the EMDM by defining inexistence and anti-existence constraints and their four subtypes. These are formally specified using set theory and first-order logic. For a given relation schema R and a constraint C, the satisfaction condition is expressed as:

The introduction of inexistence and anti-existence constraints completes the duality of existence constraints in EMDM. The constant complexity of management algorithms ensures that constraint sets can be maintained efficiently even for large schemas. The linear complexity of enforcement algorithms is optimal because any algorithm must at least examine the tuples involved in the Cartesian product. The soundness, completeness, and optimality proofs provide strong guarantees for the correctness and efficiency of the implementation. The integration into MatBase demonstrates practical applicability: the system can automatically generate SQL code to enforce these constraints, reducing the burden on database developers. The paper also discusses the implications for database design, noting that these constraints allow for more precise modeling of real-world requirements, such as preventing conflicting assignments or ensuring that certain combinations of values never occur. Future work includes extending the model to support temporal constraints and distributed databases. Overall, this research enhances the expressive power of EMDM and provides a solid theoretical and practical foundation for advanced constraint management.

CS practitioners and researchers

Opening member content…