Research Article pre-print submitted to the PriMera Scientific Engineering Journal on 5/20/2026 Extending the (Elementary) Mathematical Data Model and MatBase with two new constraint types: inexistence and anti-existence Christian Mancas* Mathematics and Computer Science Department, Ovidius University at Constanta, Romania *Corresponding Author: Christian Mancas, Ovidius University, Bd. Mamaia 124, Constanta, CT, Romania, Email: [email protected] Abstract This research paper introduces two new constraint types and four subtypes of database constraints added to our (Elementary) Mathematical Data Model, which are the duals of the existence and non-existence ones. They are formally defined, characterized, and exemplified with real-life instances. The well-formededness, satisfiability, coherence, and minimality of sets of all 7 subtypes of existence constraints is studied. Corresponding SQL-embedded pseudocode algorithms for managing such sets are provided and proved to be of constant complexity, sound, complete, and optimal. Also provided are algorithms for enforcing these new types of constraints, called inexistence and anti-existence. Their characterization proves that they have linear complexity in the sum of the arities of the function (Cartesian product)s involved, and are sound, complete, and optimal as well. All these algorithms were implemented in both versions of our intelligent data and knowledge base management system prototype MatBase, which automatically generates code for enforcing all the 7 subtypes of existence constraints.
Keywords: (Elementary) Mathematical Data Model; MatBase; anti-existence constraint; inexistence constraint; existence constraint; non-existence constraint; conceptual data modeling; database design; non-relational constraints enforcement; null values management
1. Introduction In [1] we introduced the non-existence constraints, in the framework of our (Elementary) Mathematical Data Model ((E)MDM) [2]. Recent conceptual data modeling projects brought to our attention examples of business rules whose formalization are duals to the existence and non-existence ones. As all business rules governing subuniverses of interest must be formalized as constraints and enforced either by the underlying database (db) management systems (DBMSes) or/and by the software applications built ontop of them to guarantee data plausibility [1], the highest possible quality standard in dbs, we decided to incorporate these new constraint types into (E)MDM, under the names of inexistence and anti-existence constraints, respectively. As, just like for the non-existence ones, each of them has two subtypes, namely single and consolidated ones, this extension brings the constraint types total number of the (E)MDM to 80. Of course, we added them too to both versions of MatBase (the MS Access one for small and medium dbs and the C# and SQL Server one for large dbs), our intelligent data and knowledge base management system prototype [3] based on both (E)MDM, Entity-Relationship Data Model (RDM) [4-6], and Relational Data Model [6-8]. The next Section mentions related work. The third one is dedicated to the materials and methods used. The fourth one presents and discusses the results obtained. The paper ends with conclusions and a list of references.
1
2. Related Work Among the famous 12 rules of E.F. Codd, the father of the RDM, the third one refers to null values [9]: “Null values (distinct from the empty character string or a string of blank characters and distinct from zero or any other number) are supported in fully relational DBMS for representing missing information and inapplicable information in a systematic way, independent of data type.” Codd also introduced the null substitution principle [10]. Dozens of papers were dedicated to the theoretical and practical treatment of null values in RDM and relational DBMSes were published (see, e.g., [11]). Existence constraints were introduced in [12]. We extended them to composite functions and function products [1,2]. A first algorithm on enforcing coherence and minimality of (E)MDM constraint sets was published in [13].
3. Materials and Methods Recall that a function (mapping) is a binary relation between two sets, not necessarily distinct, that satisfies two conditions: functionality, i.e., each element of one set (called the domain) is mapped to only one element of the other set (called the codomain), and totality, i.e., any element of the domain is mapped to one element of the codomain; obviously, they can be combined into only on condition: each element from the domain is mapped to exactly one element from the codomain. Using the standard math notation, e.g., Country : CITIES → COUNTRIES is a function (between the domain CITIES and the codomain COUNTRIES) as it maps any world city to the country to which it belongs (where territories which are not countries, like Gaza, are assimilated in COUNTRIES as well). For example, Country(New York) = U.S.A., Country(Montreal) = Canada, Country(Sydney) = Australia, Country(Sibiu) = Romania, etc. Often, not only in dbs, we either temporarily do not know or do not care what are the values of a function for some elements of its domain, or they even do not exist. For example, Capital : COUNTRIES → CITIES do not have values not only for some territories but even for the island country of Nauru; moreover, in relational dbs (rdbs), due to the circular nature of these two functions, you have to first add to the table COUNTRIES a new entry (say, for France) and only then add to the table CITIES entries for its cities (say, Paris, its capital, Marseille, Strasbourg, etc.). This means that Capital must not be totally defined, or accept null values, or be partially defined, which, theoretically, means that its codomain is extended to CITIES NULLS, where NULLS is a distinguished countable set of null values (where distinguished means that none of its elements also belong to another set and countable means that is discretely infinite, just like the set of naturals). Consequently, in general, by default, all rdbs table columns (i.e., functions defined on the sets of rows making the instances of the corresponding tables and taking values either from such instances, if they are foreign keys, or from data types, i.e., subsets of naturals, rationals, reals, string sets over the ASCII or UNICODE alphabets, etc.) are not totally defined (i.e., they accept null values) and totality is an explicit constraint (called NOT NULL) associated with some of them. Mathematically, the schema of a rdb table is a function (Cartesian) product, e.g., COUNTRIES is a function product x • CountryName • Capital • Currency • Population • Area : COUNTRIES → NAT(3) ASCII(255) CITIES CURRENCIES [450, 10000000000] [0.4, 20000000], where NAT(3) = {0, 1, …, 999}, ASCII(255) is the subset of strings made of ASCII characters and having maximum length 255, x is a surrogate autonumber primary key, CountryName is NOT NULL and unique (i.e., one-to-one, as there may not be two countries or territories having same name), Capital is unique as well (as no city may simultaneously be the capital of two countries), and Capital and Currency are foreign keys referencing
2
CITIES and CURRENCIES, respectively (hopefully, pointing to their corresponding primary keys x). Generally, given functions f : D → Cf and g : D → Cg, their function (Cartesian) product is the function denoted f • g : D → Cf Cg, with (f • g)(x) = <f(x), g(x)>, for any element x of D, where is the symbol denoting the Cartesian product set operator: e.g., if Cf = {1,2} and Cg = {a,b}, then Cf Cg = {<1,a>, <1,b>, <2,a>, <2,b>}. f and g are called single. Mathematically, SQL JOIN operators perform function compositions; e.g., to obtain the set of pairs <country name, capital name> you need to run the query SELECT CountryName, CityName FROM COUNTRIES JOIN CITIES ON COUNTRIES.Capital = CITIES.x, which computes the function product CountryName • Capital CityName, where Capital CityName : COUNTRIES → ASCII(255) is the composition of Capital with CityName : CITIES → ASCII(255). Generally, given functions f : D → C and g : C → E, the composite function f g : D → E computes (f g)(x) = f(g(x)), for any element x of D. For composite functions, f and g are called atomic. In conceptual data modeling, only products including composite functions are of interest, while their dual, i.e., compositions including function products, are not. Conceptual data modeling, db design, and software engineering must always rigorously treat null values, as, otherwise, either implausible data is stored in dbs, or incorrect results are computed by queries, or both. Consequently, (E)MDM included for many years already the existence and non-existence constraint types. Recall that an existence constraint is written f |⎯ g and is a shorthand for (xD)(f(x)NULLS g(x)NULLS), i.e., anytime when f is defined, g must be defined as well, e.g., email |⎯ FirstName • LastName, for the business rule “Whenever the email address of somebody is known, the corresponding first and last names must also be known.” Generally, to the left of the implication operator |⎯ there may also be a function product: f1 • … • fn |⎯ g1 • … • gm, n, m > 0, naturals, with both f1 • … • fn and g1 • … • gm being defined over the same set D, is a shorthand for (xD)(i, 1 i n)(fi(x)NULLS gj(x)NULLS, j, 1 j m), i.e., whenever at least one fi ‘s value is known, all gj ‘s values must also be known, e.g., streetAddress • email |⎯ FirstName • LastName is formalizing the business rule “Whenever either the street or email addresses of somebody is/are known, the corresponding first and last names must also be known.” Right-dually, we introduced the concept of non-existence constraints, written f |⎯ g, which is a shorthand for (xD)(f(x)NULLS g(x)NULLS), i.e., anytime when f is defined, g must not be defined, e.g., SSN |⎯ ITIN, for the business rule “Whenever a U.S. resident has a SSN, then he/she may not also have an ITIN” (where SSN = Social Security Number and ITIN = Individual Taxpayer Identification Number) [1]. As in the majority of cases these constraints are symmetric, e.g., ITIN |⎯ SSN also holds, we also introduced the simpler, coalescing syntax |⎯ f1 • … • fn, which stands for (xD)(i, 1 i n)(fi(x)NULLS fj(x)NULLS, j, 1 j n, j i), i.e., whenever one fi ‘s value is known, all other fj ‘s values must be unknown (alternatively, at most one fi ‘s value may be known for any element of D), e.g., |⎯ SSN • ITIN is formalizing the business rule “U.S. citizens may have assigned either a SSN or an ITIN but not both.” The first new existence-type constraint we are adding to (E)MDM in this paper is the dual of the non-existence: an inexistence constraint is written as f |⎯ g, which abbreviates (xD)(f(x)NULLS g(x)NULLS), i.e., anytime when f is unknown, g must be known, e.g., email |⎯ PhoneNo, for the business rule “Whenever the email address of a contact is unknown, the corresponding phone number must be known as well.” As in the majority of cases these constraints are symmetric too, e.g., PhoneNo |⎯ email also holds, we also introduced the simpler, coalescing syntax |⎯ f1 • … • fn, which stands for (xD)(i, 1 i n)(fi(x)NULLS), i.e., at least one fi ‘s value must be known for any element of D, e.g., |⎯ email • PhoneNo is formalizing the business rule “For every contact, either the email address or the phone number must be known.” Please do not confuse this (E)MDM notation with the similar RDM one, which means “all fi ‘s are NOT NULL”: recall that f NOT NULL from RDM is written f total in (E)MDM. Finally, the second new existence-type constraint we are adding to (E)MDM in this paper is the dual of the existence
3
one: an anti-existence constraint is written as f |⎯ g, which abbreviates (xD)(f(x)NULLS g(x)NULLS), i.e., anytime when f is unknown, g must also be unknown, e.g., PassedAwayYear |⎯ KilledBy, for the “business” rule “Whenever the passed away year of a person is unknown, that person was not killed” (famously put it as "There's no living with a killing" in the iconic Shane Western). We also introduced the simpler, coalescing syntax |⎯ f1 • … • fn, which stands for (xD)(i, 1 i n)(fi(x)NULLS fj(x)NULLS, j, 1 j n), i.e., all fi ‘s values are either known or unknown, for any element of D, e.g., |⎯ MultipleOf • MultiplicityFactor is formalizing the business rule “Any measurement unit is either a multiple of another one, case in which the corresponding multiplicity factor must also be known, or it is not, case in which the multiplicity factor does not make sense, hence it must also be unknown.” Indeed, e.g., the MB is a multiple of the KB with factor 1024 but the bit is not multiple of anything, hence it would be senseless to associate a multiplicity factor with it. Proposition 7 proves that |⎯ f • g is equivalent to {f |⎯ g, f |⎯ g}.
MatBase implementation To accommodate storing anti-existence and inexistence constraints together with the existence and non-existence ones, we simply added to MatBase’s metacatalog table EXIST_CNSTRS [1] another Boolean column called Inexist?. Figure 1 shows its augmented schema and a fragment of its instance.
Figure 1: MatBase form EXIST_CNSTRS built over its homonym metacatalog table #C is the primary key of this table and a foreign key referencing the primary key of the metacatalog table CONSTRAINTSET, which is storing for all constraints known to MatBase their names, dbs, type, logic formula, semantics (with database • formula, database • name, and database • semantics unique keys), etc. Mathematically, #C is the canonical inclusion injection associated to the set inclusion EXIST_CNSTRS CONSTRAINTSET (i.e., existence constraints are constraints). MatBase shows constraint names instead of their automatically generated integer identification values. ECLeftSide and ECRightSide show the functions that make the left- and right-side, respectively, of these constraints (hence, you can imagine that the implication operator |⎯ is stored between Negation? and ECRightSide). Inexist? stores the negation () operator (if any) before ECLeftSide, while Negation? stores the one before the implication operator |⎯. Finally, the computed column *Set stores the common domain set of ECLeftSide and ECRightSide; e.g., for the inexistence constraint IEC0: LastName |⎯ FirstName (see second, selected line of data from Figure 1), formalizing the “business” rule “Whenever the last name of somebody is not known, the corresponding first name must be known” (which must be enforced not only for companies, which generally have names of only one word,
4
but also for humans: e.g., ancient Greeks did not use last names, see Homer, Sophocles, Aristotle, etc.), the common domain set is Contacts from the db Stocks.mdb (stored in the Stocuri folder of the virtual logic drive V:). The values of Inexist? and Negation?, as well as the presence or absence of ECLeftSide determine the subtype of existence constraints, as shown in Figure 2 (where 0 = False and 1 = True).
Figure 2: The seven existence constraint subtypes Please note that existence and inexistence are left-duals, just like non-existence and anti-existence, while existence and non-existence are right-duals, just like inexistence and anti-existence.
Well-formed existence constraints The existence constraints of no matter what subtype are well-formed iff they have the syntaxes shown in Figure 2 and, moreover, obey the following Propositions 0 to 5: Proposition 0. Let ec be any existence constraint of no matter what subtype; (i) Both ECLeftSide and ECRightSide must be defined over the same domain set. (ii) ECRightSide : EXIST_CNSTRS → FUNCTIONS must be totally defined. Proof: Trivial, as: (i) otherwise, they may not be members of the same function product; (ii) no well-formed ec exists in Figure 2 without an ECRightSide (see column Syntax).
Q.E.D.
Corollary 0. MatBase must reject any (anti/non/in/)existence constraint without right-hand side or with sides that are not defined over a same set. Proposition 1. All single functions from both ECLeftSide and ECRightSide must be partially defined. Proof: Trivial, as otherwise they would not take null values.
Q.E.D.
Corollary 1. Let ec be any existence constraint of no matter what subtype; (i) Any composite function taking part in ec must contain at least one partially defined atomic function. (ii) The only totally defined functions that may appear in ec must be atomic. (iii) MatBase must reject any (anti/non/in/)existence constraint involving a totally defined function, except when that function is a member of a partially defined composite one. Proof: Trivial, left to the reader (hint, e.g., Capital CityName above is not total, although CityName is total but Capital is not).
Q.E.D.
5
(E)MDM and MatBase consider both a composite and a (Cartesian) product function to be partially defined whenever at least one of their member functions is not totally defined (see [2] and [1], respectively). Proposition 2. No atomic function may appear more than once in an existence constraint of no matter what subtype. Proof: Obviously, as on the same side it would be superfluous and on both sides it would be either superfluous or incoherent.
Q.E.D.
Please note that (E)MDM and MatBase do not accept duplicates in function products (e.g., see the constraint uniq_ FUNCT_PRODUCTS_F from VIII.D of [14]). Corollary 2. In any existence constraint of no matter what subtype, (i) MatBase must enforce {f1, …, fn} {g1, …, gm} = (ii) ECLeftSide ECRightSide. Proof: Trivial, left to the reader.
Coherence and minimality of the sets of (anti/non/in/)existence constraints Proposition 3. To guarantee that EXIST_CNSTRS is a set and that any set of existence constraints is minimal, ECSTS = ECRightSide • ECLeftSide • Inexist? • Negation? : EXIST_CNSTRS FUNCTIONS (FUNCTIONS NULLS) BOOLE BOOLE must be minimally injective (one-to-one). Proof: Let us denote f = 1, g = 2, f • g = 3, absence of f and False with 0, and True = 1; column Values from Figure 3 shows the corresponding values for all 7 existence constraint subtypes from Figure 2, obtained by concatenating the values of these 4 columns (presented in the order in which they are stored in both the table and the form from Figure 1): {13, 102, 112, 1002, 1013, 1102, 1112}. As expected, there are no duplicates, so ECSTS is injective. Column MinValues shows the corresponding values when eliminating ECLeftSide: {2, 12, 13, 102, 103, 112, 113}; the fact that there are no duplicates either, means that, syntactically, you can uniquely identify existence constraint subtypes even without considering ECLeftSide. However, to also eliminate duplicates from any existence constraint set, ECLeftSide must be part of this key; otherwise, e.g., users might store in a same db, under distinct names, two constraints of the types f |⎯ g or f |⎯ g having the same body. Moreover, if Inexist? is eliminated from ECSTS, 2 and 12 are duplicated; if Negation? is eliminated, 2 and 12 are duplicated; finally, if ECRightSide is eliminated, 1, 10, and 11 are duplicated. Consequently, ECSTS is minimally injective.
Q.E.D.
Corollary 3. To avoid storing duplicates in the EXIST_CNSTRS table, MatBase must enforce the unique semantic key ECRightSide • ECLeftSide • Inexist? • Negation?
Figure 3: The seven existence constraint subtypes syntax abbreviated, with and w/o ECLeftSide
6
Proposition 4. In any ec, whenever ECLeftSide is not specified, then ECRightSide must be a function product (i.e., *arity(ECLeftSide) = 0 *arity(ECRightSide) > 1). Proof: trivial, from inspecting the table from Figure 3: ECLeftSide is missing only for subtypes 3, 5, and 7, for which ECRightSide is always f • g.
Q.E.D.
Corollary 4. MatBase must enforce *arity(ECLeftSide) = 0 *arity(ECRightSide) > 1, for any compacted anti- or inexistence constraint. Proposition 5. Considering False equivalent to a null value (as, usually in dbs, whenever a Boolean column is left null, that null is considered False): (i) (Inexist? • Negation?) |⎯ ECLeftSide (any not negated not inexistence constraint is an existence one, hence ECLeftSide is compulsory) (ii) (Inexist? • ECLeftSide) |⎯ Negation? (any not inexistence constraint without left side is a non-existence one, hence Negation? must be True). Proof: (i) Trivially, if we assume by reductio ad absurdum that ECLeftSide may be null in such circumstances, it follows that existence constraints having syntax |⎯ g with Inexist? = False are valid, which is absurd. (ii) Similarly, if we assume by reductio ad absurdum that Negation? may be null in such circumstances, it follows that existence constraints having syntax |⎯ g with Inexist? = False are valid, which is absurd.
Q.E.D.
Corollary 5. MatBase must reject any existence constraint without left-hand side, as well as any non-existence one without Negation? = True. The seven existence constraint subtypes also interact between them, not only with other (E)MDM constraint types. To simplify proofs of the following results, please note the following: -
As f and g are interchangeable, (xD)(f(x)NULLS g(x)NULLS) is equivalent to (xD)(f(x)NULLS g(x)NULLS g(x)NULLS f(x)NULLS) and (xD)(f(x)NULLS g(x)NULLS) is equivalent to (xD)(f(x)NULLS g(x)NULLS g(x)NULLS f(x)NULLS). Moreover, as a b is equivalent to a b, these formulas are equivalent to (xD)(f(x)NULLS g(x)NULLS g(x)NULLS f(x)NULLS), i.e., (xD)(f(x)NULLS g(x)NULLS), and (xD)(f(x)NULLS g(x)NULLS g(x)NULLS f(x)NULLS), i.e., (xD)(f(x)NULLS g(x)NULLS), respectively.
-
Although all formulas from column Formula of the table from Figure 2 are first-order predicate logic ones, they can be computed as their propositional (zero-order) logic equivalent one, easily obtainable, e.g., by denoting f(x)NULLS =f and g(x)NULLS = g; e.g., the two above ones become (f g) (g f), which is, indeed, equivalent to f g, and (f g) (g f), which is equivalent to f g, respectively. Figure 4 provides the propositional logic formulas for all existence constraint subtypes from Figure 2.
According to Figure 4, in fact, only 5 subtypes are independent of each other: being trivial, we leave proof of Proposition 6 to the reader. Proposition 6. (i) f |⎯ g |⎯ f • g (ii) f |⎯ g |⎯ f • g
7
Figure 4: The seven existence constraint subtypes and their corresponding logic propositions Corollary 6. According to Proposition 6 and Figure 4, MatBase must always replace: (i) f |⎯ g by |⎯ f • g (as it is explicitly richer, also including f(x)NULLS g(x)NULLS) (ii) f |⎯ g by |⎯ f • g (as it is explicitly richer, also including f(x)NULLS g(x)NULLS) Analyzing the interactions between the C(5, 2) = 10 pairs of the remaining independent subtypes, we get the following results: Proposition 7. (i) f |⎯ g f |⎯ g |⎯ f • g (ii) f |⎯ g |⎯ f • g |⎯ f • g (iii) f |⎯ g |⎯ f • g |⎯ f • g Proof: (i) f |⎯ g f |⎯ g can be computed as (f g) (f g), which is equal to f g. (ii) f |⎯ g |⎯ f • g can be computed as (f g) f g, which is equal to f g. (iii) f |⎯ g |⎯ f • g can be computed as (f g) f g, which is equal to f g.
Q.E.D.
Corollary 7. MatBase must always replace f |⎯ g f |⎯ g, f |⎯ g |⎯ f • g, and f |⎯ g |⎯ f • g by |⎯ f • g. Proposition 8. The following 6 existence constraint subtype pairs are mutually exclusive (i.e., orthogonal to each other): <f |⎯ g, f |⎯ g>, <f |⎯ g, f |⎯ g>, < f |⎯ g, f |⎯ g >, < f |⎯ g, |⎯ f • g>, <f |⎯ g, f |⎯ g>, <f |⎯ g, |⎯ f • g> Proof: Let us consider any f : D → Cf NULLS and g : D → Cg NULLS; (i). (both f |⎯ g and f |⎯ g) Suppose by reductio ad absurdum that f |⎯ g f |⎯ g, i.e., (xD)(f(x)NULLS g(x)NULLS f(x)NULLS g(x)NULLS); trivially (by tertium non datur), g(x) may not be both null and not null, for no x. Check through propositional calculus: f |⎯ g f |⎯ g can be computed as (f g) (f g), which is equal to f, i.e., (xD)(f(x)NULLS), which is absurd. (ii). (both f |⎯ g and f |⎯ g)
8
Suppose by reductio ad absurdum that f |⎯ g f |⎯ g, i.e., (xD)(f(x)NULLS g(x)NULLS f(x)NULLS g(x)NULLS); trivially, this would mean that g(x) may never take null values, i.e., it is totally defined, which contradicts (g total). Check through propositional calculus: f |⎯ g f |⎯ g can be computed as (f g) (f g), which is equal to g, i.e., (xD)(g(x)NULLS), which is absurd. (iii). (both f |⎯ g and f |⎯ g) Suppose by reductio ad absurdum that f |⎯ g f |⎯ g, i.e., (xD)(f(x)NULLS g(x)NULLS f(x)NULLS g(x)NULLS), for any f and g; trivially, this is incoherent, as it would mean that g takes only null values. Check through propositional calculus: f |⎯ g f |⎯ g can be computed as (f g) (f g), which is equal to g, i.e., (xD)(g(x)NULLS ), which is absurd. (iv). (both f |⎯ g and |⎯ f • g) Suppose by reductio ad absurdum that f |⎯ g |⎯ f • g, i.e., (xD)(f(x)NULLS g(x)NULLS (f(x)NULLS g(x)NULLS f(x)NULLS g(x)NULLS)), which reduces to (xD)(f(x)NULLS g(x)NULLS), for any f and g; trivially, this is incoherent, as it would mean that both f and g take only null values. Check through propositional calculus: f |⎯ g |⎯ f • g can be computed as (f g) (f XNOR g), which is equal to f g, i.e., (xD)(f(x)NULLS g(x)NULLS ), which is absurd. (v). (both f |⎯ g and f |⎯ g) Suppose by reductio ad absurdum that f |⎯ g f |⎯ g, i.e., (xD)(f(x)NULLS g(x)NULLS f(x)NULLS g(x)NULLS), for any f and g; trivially, this is incoherent, as g(x) may not simultaneously take both null and not null values. Check through propositional calculus: f |⎯ g f |⎯ g can be computed as (f g) (f g), which is equal to f, i.e., (xD)(f(x)NULLS), which is absurd (as f is not totally defined). (vi). (both f |⎯ g and |⎯ f • g) Suppose by reductio ad absurdum that f |⎯ g |⎯ f • g, i.e., (xD)(f(x)NULLS g(x)NULLS (f(x)NULLS g(x)NULLS f(x)NULLS g(x)NULLS)), for any f and g; trivially, this is incoherent, as it reduces to (xD) (f(x)NULLS g(x)NULLS). Check through propositional calculus: f |⎯ g |⎯ f • g can be computed as (f g) (f XNOR g), which is equal to f g, i.e., (xD)(f(x)NULLS g(x)NULLS), which is absurd (neither f, nor g are totally defined).
Q.E.D.
Corollary 8: MatBase must always reject any of the 6 pairs from Proposition 8. Please note that the pair <f |⎯ g, f |⎯ g> can be computed as (f g) (f g), which is equal to f XOR g (f g), i.e., (xD)(f(x)NULLS g(x)NULLS ), i.e., for any x in D, either f(x)NULLS or g(x)NULLS but never both, which is theoretically legitimate, but not for any f and g: e.g., if we consider f = SSN and g = ITIN, as shown above, SSN |⎯ ITIN; however, SSN |⎯ ITIN does not hold, as there are U.S. residents who do not have either SSN or ITIN (e.g., recently arrived / undocumented, dependents who do not file taxes, persons without tax filling obligations, and exempt religious groups). Let us now analyze all the C(5, 3) = 10 triples made of the independent 5 existence constraint subtypes. Proposition 9. No triple made of the independent 5 existence constraint subtypes over same two functions (f and g) may exist in any coherent and minimal set of existence constraint subtypes.
9
Proof: (i) <f |⎯ g, f |⎯ g, f |⎯ g> is incoherent, according to Proposition 8 (i) and (ii). (ii) <f |⎯ g, f |⎯ g, f |⎯ g> is incoherent, according to Proposition 8 (i) and (v). (iii) <f |⎯ g, f |⎯ g, |⎯ f • g> is incoherent, according to Proposition 8 (i) and (iv). (iv) <f |⎯ g, f |⎯ g, f |⎯ g> is incoherent, according to Proposition 8 (ii) and (v). (v) <f |⎯ g, f |⎯ g, |⎯ f • g> is incoherent, according to Proposition 8 (ii) and (vi). (vi) According to Proposition 7 (i), <f |⎯ g, f|⎯ g, |⎯ f • g> = <|⎯ f • g, |⎯ f • g>, pair not minimal, as it contains duplicates, which is rejected according to Proposition 3. (vii) <f |⎯ g, f |⎯ g, f |⎯ g> is incoherent, according to Proposition 8 (v). (viii) <f |⎯ g, f |⎯ g, |⎯ f • g> is incoherent, according to Proposition 8 (vi). (ix) <f |⎯ g, f |⎯ g, |⎯ f • g> is incoherent, according to Proposition 8 (iii). (x) <f |⎯ g, f |⎯ g, |⎯ f • g> is incoherent, according to Proposition 8 (v).
Q.E.D.
Corollary 9. (i) No quadruple or quintuple made of the independent 5 existence constraint subtypes over same two functions (f and g) may exist in any coherent and minimal set of existence constraints. (ii) MatBase must not accept any triple discussed in Proposition 9. Proof: trivial, left to the reader (hint: no triples are coherent, according to Proposition 8).
The (E)MDM meta-model for the (E)MDM existence constraint subtypes Figure 5 shows the sets and functions from the (E)MDM meta-model of (E)MDM (which is also the (E)MDM model of the corresponding fragment of MatBase’s metacatalog) that are referenced in the meta-model for the (E)MDM existence constraint subtypes shown in Figure 6 (in (E)MDM, Boolean functions need not be declared as totally defined, as null values are treated as False).
Figure 5: The sets and functions referenced in the set, function, and constraint definitions from Figure 6
10
Figure 6: The (E)MDM meta-model for the (E)MDM existence constraint subtypes
MatBase pseudocode algorithms for enforcing the (E)MDM existence constraints Figures 7 to 12 show the MatBase SQL-embedded pseudocode algorithms for enforcing satisfiability, coherence, and minimality of (E)MDM existence constraint subtype sets. Enforcing in- and anti-existence constraints in MatBase Enforcement of existence and non-existence constraints in MatBase was described in [1] (see Figures 2 to 4). Obviously, just like in their case, deleting an element from the domain set D underlying an anti-existence or inexistence constraint may never violate it, while, dually, inserting a new one or updating an existing one may. Consequently, to enforce such constraints, the class D of the software app that manages the corresponding db must contain an event-driven method BeforeUpdate like the one shown in Figure 2 from [1]. This method must be automatically launched whenever users ask (implicitly or explicitly) for saving either a new added line or the updates to f and/or g values on an existing line from table D (uniquely identified by the value of D’s surrogate primary key x). MatBase automatically generates it the first time that a constraint involving D is added to the db scheme.
11
Figure 7: MatBase ECEA Algorithm for enforcing satisfiability, coherence, and minimality of existence constraint sets
Figure 7 (Continued) Similar to the case of existence and non-existence ones, whenever MatBase accepts a single inexistence constraint iec: f |⎯ g over D or a consolidated (compacted) one |⎯ f • g, it adds to this method a line that reads “if not Cancel then Cancel = enforce_inexist_cnstr(iec, f(x), g(x));”; whenever it accepts a single anti-existence constraint aec: f |⎯ g over D or a consolidated one |⎯ f • g, it adds a line that reads “if not Cancel then Cancel = enforce_antiexist_cnstr(aec, f(x), g(x));”. These lines implement the C = C {cn} statement of the Algorithm ECEA from Figure 7.
12
Figure 8: Function checkExistTotality of MatBase ECEA Algorithm Dually, whenever MatBase deletes an inexistence constraint named iec over D, it removes from this method the line that starts with “if not Cancel then Cancel = enforce_inexist_cnstr(iec,”; whenever it deletes an anti-existence constraint named aec over D, it removes the line that starts with “if not Cancel then Cancel = enforce_anti-exist_cnstr(aec,”: this is how MatBase implements the C = C ⎯ {cn} statement of the Algorithm ECEA from Figure 7. Figures 13 and 14 present the pseudocode of methods enforce_inexist_cnstr and enforce_anti-exist_cnstr, respectively, that MatBase is storing in its library Constraints [3], alongside the enforce_existence_cnstr and enforce_nonexistence_cnstr shown in Figures 3 and 4 from [1].
4. Results and Discussion Proposition 10. (Characterization of Algorithm ECEA from Figures 7 to 12) Algorithm ECEA from Figures 7 to 12 has the following properties: (i) It never loops infinitely. (ii) It is extremely fast, having complexity O(k), k natural. (iii) It enforces all 10 above Corollaries 0 to 9. (iv) It warrants the satisfiability, coherence, and minimality of the sets of all 7 subtypes from Figure 4. (v) It is sound. (vi) It is complete. (vii) It is optimal. Proof: (i) Trivial, as it has no loops. (ii) Obvious, as in the worst case (i.e., when a new constraint is added to the existing set) the algorithm from Figure 7 performs kmax = 15 steps; similarly, the function checkExistTotality from Figure 8 performs at most 7 steps,
13
Figure 9: Function checkExistDisjoint of MatBase ECEA Algorithm
Figure 10: Function checkExistCoherence of MatBase ECEA Algorithm
14
Figure 11: Function checkExistSatisf of MatBase ECEA Algorithm checkExistDisjoint from Figure 9 at most other 7, checkExistCoherence from Figure 10 another 2, checkExistSatisf from Figure 11 another 5, and checkExistRedundancies from Figure 12 another 6; in total, kmax = 15 + 27 = 42. (iii) checkExistTotality from Figure 8 enforces Corollary 1, checkExistDisjoint from Figure 9 enforces Corollary 2, checkExistCoherence from Figure 10 Corollaries 8 and 9, and checkExistRedundancies from Figure 12 Corollaries 6 and 7, while ECEA from Figure 7 enforces Corollaries 0, 3, 4, 5. (iv) Function checkExistSatisf from Figure 11 guarantees satisfiability; function checkExistCoherence from Figure 10 coherence, and function checkExistRedundancies from Figure 12, as well as ECEA, which is enforcing Corollary 3, minimality. (v) Soundness is guaranteed by Corollaries 0, 1, 2, 4, and 5, all of them enforced by ECEA and its functions checkExistTotality and checkExistDisjoint: as it accepts only well-formed constraints, its output will always contain only valid sets of constraints of all 7 subtypes from Figure 4. (vi) Completeness is also guaranteed by Corollaries 0 to 2 and 4 to 5: any well-formed constraint of all 7 subtypes from Figure 4 are accepted. (vii) Optimality is obvious from inspecting the algorithms from Figures 7 to 12: all of them are performing their tasks with the minimum number possible of instructions and disk accesses, be it to the MatBase metacatalog tables or to the underlying db instance.
Q.E.D.
Proposition 11. (Characterization of method enforce_inexist_cnstr from Figure 13) Method enforce_inexist_cnstr from Figure 13 has the following properties: (i) It never loops infinitely. (ii) It is fast, having complexity O(n + m), n, m naturals being the arities of the left- and right-side of the corresponding constraint, respectively. (iii) It correctly enforces any stored inexistent constraint, be it simple or consolidated. (iv) It is sound. (v) It is complete.
15
Figure 12: Function checkExistRedundancies of MatBase ECEA Algorithm (vi) It is optimal. Proof: (i) Trivial, as it has 3 loops, out of which 2 are executing at most m times and one at most n times. (ii) Obvious, as in the worst case (i.e., when the constraint is a single one and the new values for f(x) and g(x) are valid) the algorithm performs kmax = 7 + n + m steps. (iii) For consolidated ones, in its first loop it checks whether at least one (f • g)’s function member (in this case consolidated as the third method parameter) has a not null value for the current element x of the underlying domain; for single ones, it first checks in the second loop whether there is at least one f ’s function member for which the corresponding current x desired value is null and then, in the third loop, whether all g’s function members have not null values for the current x element. For both subtypes of inexistent constraints, whenever the corresponding conditions are not met, the method rejects saving the new values for f(x) and g(x) with appropriate error messages. (iv) Soundness is guaranteed by (iii) above, as this method rejects any attempt to violate any inexistence constraint, keeping the db instances clean of invalid data. (v) Completeness is guaranteed by the fact that it accepts any inexistence constraint and possible values for its functions f and g (accepting only those that satisfy the constraint and rejecting those that would violate it).
16
Figure 13: MatBase method enforce_inexist_cnstr (vi) Optimality is obvious from inspecting the algorithm from Figure 13: this method is performing its tasks with the minimum number possible of instructions and disk accesses, be it to the MatBase metacatalog tables or to the underlying db instance, for both single and consolidated inexistence constraints.
Q.E.D.
Proposition 12. (Characterization of method enforce_anti-exist_cnstr from Figure 14) Method enforce_anti-exist_cnstr from Figure 14 has the following properties: (i) It never loops infinitely. (ii) It is fast, having complexity O(n + m), n, m naturals being the arities of the left- and right-side of the corresponding constraint, respectively. (iii) It correctly enforces any stored anti-existent constraint, be it simple or consolidated. (iv) It is sound. (v) It is complete. (vi) It is optimal.
17
Figure 14: MatBase method enforce_anti-exist_cnstr Proof: (i) Trivial, as it has 3 loops, out of which 2 are executing at most m times and one at most n times. (ii) Obvious, as in the worst case (i.e., when the constraint is a single one and the new values for f(x) and g(x) are valid) the algorithm performs kmax = 7 + n + m steps. (iii) For consolidated ones, in its first loop it checks whether all (f • g)’s function members (in this case consolidated as the third method parameter) have either null or not null values for the current element x of the underlying domain; for single ones, it first checks in the second loop whether there is at least one f ’s function member for which the corresponding current x desired value is not null and then, in the third loop, whether all g’s function members have null values for the current x element. For both subtypes of anti-existent constraints, whenever the corresponding conditions are not met, the method rejects saving the new values for f(x) and g(x) with appropriate error messages. (iv) Soundness is guaranteed by (iii) above, as this method rejects any attempt to violate any anti-existence constraint, keeping the db instances clean of invalid data. (v) Completeness is guaranteed by the fact that it accepts any anti-existence constraint and possible values for its functions f and g (accepting only those that satisfy the constraint and rejecting those that would violate it).
18
(vi) Optimality is obvious from inspecting the algorithm from Figure 14: this method is performing its tasks with the minimum number possible of instructions and disk accesses, be it to the MatBase metacatalog tables or to the underlying db instance, for both single and consolidated anti-existence constraints.
Q.E.D.
For example, let us consider D = PERSONS, C = {iec: |⎯ email • PhoneNo, aec: PassedAwayYear |⎯ KilledBy}, iec’: |⎯ email • Name, with Name totally defined, iec”: email |⎯ email • PhoneNo, aec’: |⎯ PassedAwayYear • KilledBy, and aec’’: PassedAwayYear |⎯ KilledBy; 1.
Obviously, both iec and aec are accepted by Algorithm ECEA, so that the BeforeUpdate method of class PERSONS would look as in Figure 15.
2.
Any attempt to save to the db a line containing {(email • PhoneNo)(x) = <,>} is rejected with the error message “Saving these values is rejected: according to inexistence constraint iec, at least a column of email • PhoneNo must have a not null value!”.
3.
Any attempt to save to the db a line containing {(PassedAwayYear(x), KilledBy(x) = < , 123>} is rejected with the error message “Saving these values is rejected: according to anti-existence constraint aec, all columns of KilledBy must have a null value!”.
4.
Requests to save to the db lines containing {(email • PhoneNo)(x) = <”[email protected]”,>}, or {(email • PhoneNo)(x) = <”[email protected]”, 12345678>}, or {(email • PhoneNo)(x) = <, 12345678>} are accepted.
5.
Requests to save to the db lines containing {(PassedAwayYear(x), KilledBy(x)) = <1610, 123>} or {(PassedAwayYear(x), KilledBy(x)) = < , >} are accepted.
6.
Request to add iec’ to C is rejected with the error message “Request rejected: member function(s) Name is/are totally defined!”.
7.
Request to add iec” to C is rejected with the error message “Request rejected: email is member function Name of both email and email • PhoneNo!”.
8.
Request to add aec’ to C is granted but with the info message “Enforced constraint aec: PassedAwayYear |⎯ KilledBy is replaced by aec’ for minimality reasons!”. Automatically, MatBase replaces in the method BeforeUpdate from Figure 15 the line reading “if not Cancel then Cancel = enforce_anti-exist_cnstr(aec, PassedAwayYear(x), KilledBy(x));” with the following one: “if not Cancel then Cancel = enforce_antiexist_cnstr(aec, , (PassedAwayYear • KilledBy)(x))”.
9.
Request to add aec” to C is rejected with the error message “Request rejected: constraint set would become incoherent!”.
10. Request to delete iec from C would trigger MatBase to display the message “Are you sure you want to delete constraint iec: |⎯ email • PhoneNo? Cancel OK”; if user chooses Cancel, nothing happens; if he/she chooses OK, then MatBase deletes from the method BeforeUpdate from Figure 15 the line reading “if not Cancel then Cancel = enforce_inexist_cnstr(iec, , (email • PhoneNo)(x));”. In the C# and SQL Server version of MatBase, the method BeforeUpdate from Figure 15 is implemented as a similar one attached to the event type Validating. Moreover, MatBase is also enforcing all non-relational constraints in T-SQL, thus securing the data integrity at the db level as well, protecting its instance from direct user db access. For example, Figure 16 shows a fragment of the MatBase generated T-SQL trigger associated to table PERSONS for enforcing constraint iec.
19
Figure 15. The event-driven method BeforeUpdate of class PERSONS associated to table PERSONS.
Figure 16. Fragment of the MatBase generated T-SQL trigger associated to table PERSONS for enforcing constraint iec
5. Conclusions Pushed by examples encountered in conceptual data modeling of several subuniverses of interest, we added to our (Elementary) Mathematical Data Model four new constraint types, dual to the existence and non-existence ones: the single and consolidated inexistence and anti-existence ones. We defined them formally, established their well-forming rules, and fully axiomatized the set of all 7 subtypes of existence constraints, by establishing and proving the propositions and corollaries that govern the satisfiability, coherence, and minimality of such constraint type sets. Based on them, we updated the MatBase algorithm managing the existence and non-existence constraints to also deal with inexistence and anti-existence ones. We proved that this algorithm has constant complexity, being extremely fast, and is guaranteeing the satisfiability, coherence, and minimality of existence constraint sets containing all their 7 subtypes, while being sound, complete, and optimal. We also designed and implemented in MatBase two SQL-embedded pseudocode algorithms for enforcing inexistence and anti-existence constraints, respectively, for both single and consolidated ones. We proved that they have linear complexity in the sum of the arities of their involved functions and that they are sound, complete, and optimal, while correctly enforcing any such constraint. We provided real-life examples of constraints of all four new subtypes introduced and shown that they are correctly handled by the enforcement algorithms.
20
While the new mathematical concepts and results added by this research are not outstanding, their applicability to the conceptual data modeling theory and database software applications design and development is noteworthy: currently, to enforce the business rules in the provided examples, as well as in any other similar ones, developers must design, develop, and test dedicated code for each of them, having no clue whatsoever that they belong to a certain constraint subtype, having certain properties. Consequently, they are not only prone to design and programming errors, but they also risk blocking users from storing valid data (whenever the corresponding constraint set becomes incoherent) or to slow down db and app response time (whenever the corresponding constraint set becomes not minimal, i.e., includes redundant constraints). Obviously, even if developers do not have access at a MatBase copy, they can still use the algorithms described and characterized in this paper. Consequently, we consider that this paper contributes significantly to the database constraint theory and practice, in one of the subdomains that is difficult to deal with: correctly managing the null values.
Conflict of interest The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.
Acknowledgements This research was not sponsored by anybody and nobody other than its author contributed to it. The author is grateful to Diana Christina Mancas, who implemented in MatBase and tested the algorithms presented in this paper, and to Mihaela Virginia Mancas, who is always carefully checking all our manuscripts.
References Mancas C. “On Enforcing Existence and Non-Existence Constraints in MatBase”. PriMera Scientific Engineering 4.6 (2024): 04-12. DOI: 10.56831/PSEN-04-130 2. Mancas C. “The (Elementary) Mathematical Data Model revisited”. PriMera Scientific Engineering 5.4 (2024): 78–91. DOI: 10.56831/PSEN-05-157 3. Mancas C. “MatBase Metadata Catalog Management”. Acta Scientific Computer Sciences 2.4 (2020): 25–29. DOI: 10.48550/arXiv.2504.07243 4. Chen P.P. “The entity-relationship model. Toward a unified view of data”. ACM TODS 1.1 (1976): 9–36. 5. Thalheim B. “Entity-Relationship Modeling: Foundations of Database Technology”. Springer-Verlag, Berlin, Germany (2000). 6. Mancas C. “Conceptual Data Modeling and Database Design: A Completely Algorithmic Approach. Volume 1: The Shortest Advis able Path.” Apple Academic Press, Waretown, NJ (2015). 7. Codd E.F. “A relational model for large shared data banks”. CACM 13.6 (1970): 377–387. 8. Abiteboul S., Hull R., and Vianu V. “Foundations of Databases.” Addison-Wesley, Reading, MA (1995). 9. Codd E.F. “The 12 rules.” (1985) https://reldb.org/c/index.php/twelve-rules/ 10. Codd E.F. “Extending the database relational model to capture more meaning.” ACM TODS 4(4)(1979): 397– 434. 11. Thalheim B. and Schewe K.D. “NULL ‘Value’ Algebra and Logic.” In: Heimbrrger A. et al. (Eds.). Information Modelling and Knowledge Bases XXII (2011), pp. 354–367. IOS Press, Amsterdam, The Netherlands. 12. Maier D. “Theory of Relational Databases.” Computer Science Press, U.S.A. (1983). 13. Mancas C. “MatBase Constraint Sets Coherence and Minimality Enforcement Algorithms.” In: Benczur A., Thalheim B., Horvath T. (Eds). Advances in DB and Information Systems, LNCS 11019 (2018), pp. 263–277. Springer, Cham, Switzerland. 14. Mancas C. “Teaching Enforcement of Satisfiable, Coherent, and Minimal Database Constraint Sets Associated with Function Products to Computer Science M.Sc. Students.” Chapter 10 from Daimi K. (ed.). “Emerging Trends in Computer Science and Computer Engineering Education.” Springer Nature, Cham, Switzerland (2026). DOI: 10.1007/978-3-032-23499-5 1.
21