MatBase E-RD Cycles Associated Non -Relational [621912]

MatBase E-RD Cycles Associated Non -Relational
Constraints Discovery Assistance Algorithm
Christian Mancas
Mathematics and Computer Science Department, Ovidius University, Constanta, Romania
christian.mancas@ gmail.com
Abstract. MatBase is a prototype data and knowledge base management system
based on the Relational, Entity -Relationship, and (Elementary) Mathematical
Data Models. Entity -Relationship structural diagrams are lattice -type oriented
graphs that may have cycles, with object sets as nodes and structural functions as
edges. Most of these cycles are generally uninteresting, some of them should be
broken by eliminating computable functions, but some of them have associated
non-relational constraints that must be added to corresponding database schemes
and enforced (generally with extended SQL triggers or embedding SQL high
level programming languages trigger -type methods) to guarantee database in-
stances plausibility. This paper presents and discusses all four types of such cy-
cles, an algorithm that assists database designers in discovering all non -relational
constraints associated to them, a test case of applying this algorithm to a geo-
graphical database, as well as hints on enforcing such non -relational c onstraints.
This algorithm, designed in the framework of the (Elementary) Mathematical
Data Model and implemented in MatBase , is taught to our M.Sc. students within
the Advanced Databases lectures and labs, both at the Ovidius University and at
the Departm ent of Engineering in Foreign Languages, Computer Science Taught
in English Stream of the Bucharest Polytechnic University , as well as success-
fully used by two Romanian software companies .
Keywords: data modeling, Entity -Relationship models, database const raints
theory, relational constraints, non-relational constraints, integrity checking, data
structures and algorithms for data management, triggers and rules, commutative
function diagram s, (Elementary) Mathematical Data Model, MatBase
1 Introduction
The Entity -Relation ship Data Model (E -RDM) [3 , 9, 14 ] has a major contribution: the
extremely powerful (if properly used) associated Entity -Relationship Diagrams (E –
RDs), most probably the only data modeling formalism understandable by both cus-
tomers, business analysts, data base (db) designers, and software developers, as it uses
labeled graphs made from only a few graphical symbol types: rectangles, diamonds,
ellipses, lines, and arrows.

Any db scheme is a triple < S, M, C>, where S is a non -void finite collection of sets,
M a finite non -void set of mappings defined on and taking values from sets in S, and
C a similar one of constraints (i.e. closed first -order predicate calculus with equality
formulas) over the sets in S and mappings in M. The sets and mappings constitute the
structure (“skeleton”) of any db, while the constraints, which are formalizing business
rules, are meant to only allow storing plausible data (“flesh”) into dbs.
In the Relational Data Model (RDM) [ 1, 4, 9 ], sets of S are tables and views, map-
pings of M are their columns, and constraints of C are incorporated in the table
schemes.
Unfortunately, both RDM and E -RDM have only a handful of constraint types,
which are not at all enough to guarantee data plausibility. The (Elementary) Mathemat-
ical Data Model (( E)MDM) [ 5, 6, 9 , 11], which started with a rigorous formalization of
the E -RDM, developed then into a model providing 60 types of constraints, including
the relational ones, but the most of them being non -relational. MatBase [6, 9, 11, 12,
13] is a prototy pe data and knowledge base management system providing both
(E)MDM, E -RDM, RDM, and Datalog  [1, 9] graphic user interfaces, intensively used
in our labs and projects of undergraduate Databases and M.Sc. Advanced Database
Systems.
Just like for object sets and mappings between them, constraints can be discovered
only by humans. However, computer science and math can assist in this process: e.g.
the keys discovery assistance algorithms presented in [10]. This paper introduces and
discusses an algorithm for a ssisting discovery of non -relational constraints associated
to E-RD cycles.
This first section presents our E -RD variant notation (see [ 9] for more details and
examples), recalls the difference between relational and non -relational constraints [12],
and sy ntactically characterizes the four types of E -RD cycles [ 11, 13 ].
1.1 E-R Diagrams
In its original version, atomic ( entity -type) object sets are represented by rectangles,
compound ( relationship -type) and structural function (RDM foreign key) ones by dia-
monds, and RDM non -foreign key attributes (object set properties) by ellipsis (attached
to the corresponding rectangles and diamonds). Especially for complex E -RDs, but not
only, we advocate drawing first atomic ones, having either only one rectangle and its
associated ellipsis or only one diamond, its associated ellipsis, and corresponding rec-
tangles (and, as an extension allowing for relationship hierarchies, diamonds) that are
connected by the diamond, and then only structural diagrams without any ellipsis .
In the original E -RDM, structural E -RDs are directed graphs whose edges are so –
called “ roles ” (of both mapping domains and co -domains in the corresponding relation-
ships, be them functional or not). We are using a slightly different notation [ 9]: atomic
(entity -type) object sets are represented by rectangles, just like in the original version,
mathematic non -functional relation type ones (i.e. subsets of Cartesian products) are
represented by diamonds, but function al relationships are represented as arrows , just
like in math. Hence, in our version, structural E -RD (from now on abbreviated as E –

RD) nodes are only object sets and their edges are (structural) functions. In dbs, object
sets are implemented as tables and views, while structural functions as fore ign keys.
Obviously, as in any lattice -type graph, E -RD ones may have cycles (polygons).
1.2 Relational and Non -Relational Constraints
All business rules of any data sub -universe to be modeled, be them explicit or implicit,
should be discovered, added to o ur data models, and enforced to be able to guarantee
that only plausible data is stored in the corresponding dbs. In db schemes, business rules
are incorporated as constraints. RDM provides only five types of constraints (that are
embedded in almost all Re lational Database Management Systems (RDBMS)), namely:
domain (range, co -domain; e.g. BirthDate between 1/1/1900 and SysDate ), totality (not
null, function total definition; e.g. FirstName not null), key (uniqueness, minimal one –
to-oneness; e.g. SSN unique , StateName • Country unique), referential integrity (for-
eign keys, typed inclusion; e.g. Folder references FILES ), and tuple (check; e.g.
BirthDate  MarriageDate ).
As these relational constraint types are not enough for accurate data modeling, both
exten ded and embedded SQL provide means to also enforce non -relational constraints,
namely triggers and trigger -type event driven methods, respectively.
For example, an obvious non -relational constraint exists even in an extremely simple
db only consisting of t he two tables COUNTRIES (ID, Country , CapitalCity ) and
CITIES (ID, City, Country ): “any country has as capital a city of its own” (or, dually,
“no country may have as its capital a city of another country”). Considering functions
Country : CITIES  COUNTRIES and CapitalCity : COUNTRIES  CITIES , this con-
straint can be formalized as Country  CapitalCity = 1COUNTRIES (where  denotes func-
tion composition and 1COUNTRIES is the unity mapping of COUNTRIES , 1COUNTRIES (x) =
x, xCOUNTRIES ) or, equivalently, as Country  CapitalCity reflexive . This con-
straint is associated to the E -RD cycle of length 2 from Fig. 1.
Country
CITIES COUNTRIES 1COUNTRIES
CapitalCity
Fig. 1. An example of an E -RD cycle h aving an associated non -relational constraint.
Failing to enforce this constraint could result, for example, in letting users store in
this db instance the fact that New York is the capital of Romania and/or that Craiova is
the capital of the U.S.!
E-RD cy cles are privileged places to search for non -relational constraints: generally,
there are very many uninteresting ones, which do not have any associated constraint,
but many such cycles “hide” constraints.
1.3 E-RD Cycle Types
Apart from the ones of length one (i.e. autofunctions), there may be only the following
three types of such cycles [ 11, 13 ] (where a source node is a node that is the domain of
both functions that connects it to the cycle, a destination node is the co -domain of both

functions that con nects it to the cycle, whereas all other nodes are intermediate ones –
i.e. they are the domain of one function and the co -domain of the other):
✓ commutative : any cycle having only one source and one destination nodes (connected
by two paths);
✓ circular : any cycle having only intermediate nodes (i.e. no source or destination ones);
✓ general : any other type of cycle than commutative and circular.
The general ones have length greater than 3, at least two source and two destination
nodes, and may have attac hed only generalized commutativity constraints (i.e. first or-
der logic closed formulas only involving the mappings of an E -RD cycle), which, du-
ally, may also be associated to commutative and circular types cycles. The commutative
and circular ones may also “hide” constraints of particular well -known types.
1.4 Related Work
Generally, there are very few results on non -relational constraints, except for (E)MDM
related ones ([ 5, 6, 8, 9, 11]). For example, section 6.3 of [ 3] only presents enforcement
of some p articular ones, by using the SQL functions COUNT, IS_EMPTY, and its in-
clusion operator.
Constraints associated to E -RD cycles were investigated in [ 7], which also includes
a first much simpler version of the algorithm presented in this paper, as, at that t ime,
(E)MDM provided far less constraint types than today.
MatBase provides its users with the ability to detect and classify all cycles in any db
scheme structural E -RD it manages , by using an extended DFS -type algorithm [13].
1.5 Paper Outline
Single aut ofunctions are analyzed in Section 2. Sections 3 to 5 are devoted to the three
types of E -RD cycles , respectively . Section 6 discusses constraints associated to adja-
cent such cycles. Section 7 presents the algorithm for assisting discovery of non -rela-
tiona l constraints associated to E -RD cycles, while Section 8 discusses its complexity,
optimality, and u sefulness . Section 9 provides hints for enforcing such non -relational
constraints in MatBase . The paper ends with conclusions and references.
2 Autofunctions
Autofunctions (i.e. functions defined on and taking values from a same set, hence cir-
cular cycles of length 1) are very privileged places to search for non -relational con-
straints: even as, generally, there are many uninteresting ones, which do not have any
associated constraint, many of them “hide” constraints.
Besides general function properties, like one -to-oneness and ontoness, in the partic-
ular case of autofunctions (which are dyadic relations too) we should always wonder
whether they are acyclic, refle xive, irreflexive, symmetric, asymmetric, idempotent,
or/and anti -idempotent (as Euclideanity and connectivity do not make sense for func-
tions).
For example, all autofunctions that model trees (e.g. Folder : FILES  FILES , Re-
portsTo : EMPLOYEES  EMPLOYEES , Mother : PEOPLE  PEOPLE , Father :

PEOPLE  PEOPLE ) are acyclic (which, in this context, means that they are also
irreflexive, asymmetric, and anti -idempotent [ 11]), as trees do not contain cycles (e.g.
no folder may be its subfolder, neither directly, n or indirectly; no employee may report
to her/himself, neither directly, nor indirectly; nobody may be his/her ancestor, neither
directly, as parent, nor indirectly).
For example, ElectedRepresentative : PEOPLE  PEOPLE is idempotent, as any
elected represe ntative is also representing him/herself. Generally, any canonical surjec-
tion is not only onto, but also idempotent.
For example, Spouse : PEOPLE  PEOPLE is trivially irreflexive and symmetric
(as nobody can get married to her/himself and as whenever y is a spouse of x, then x is
a spouse of y too).
The only interesting cases of single autofunction reflexivity constraints are those for
mappings that are not totally defined (i.e. that may take null values, but, whenever for
a given x they are not null, they should always be x): what would be the use of storing
in a db table a column whose values should always be equal to those of the primary
surrogate key of that table? On the contrary, reflexivity is very often encountered for
composed autofunctions, as pro ved by Section 4 below, as well as by the example in
Fig. 1. Any reflexive autofunction is also symmetric, idempotent, and, when totally
defined, bijective too [ 11].
As any asymmetric or anti -idempotent is irreflexive too [ 11], to conclude, for any
autofun ction the following should be done:
➢ Check whether it is acyclic; if yes, then
✓Add corresponding acyclicity constraint;
➢If no,
✓Check whether it is reflexive; if yes, then
❖ If it is atomic and totally defined then remove autofunction;
❖ Else Add corresponding reflexivity constraint ;
✓If no, then
❖ Check whether it is symmetric; if yes, then
  Add corresponding symmetry constraint;
❖ If no, check whether it is asymmetric; if yes, then
  Add corresponding asymmetry constraint;
❖ Check whether it is idempotent; if yes, then
  Add corresponding idempotency constraint;
❖ If no, check whether it is anti -idempotent; if yes, then
Add corresponding anti -idempotency constraint;
❖ If neither asymmetric nor anti -idempotent then check whether it is
irreflexive; if yes , then Add corresponding irreflexivity constraint .
3 Commutative -Type E -RD Cycles
The first three subsections of this section deal only with commutative -type cycles of
length greater than two. As they need special treatment, those of length two are dealt
with in the fourth subsection.

3.1 Commutative Function Diagrams
Math studies function diagram commutativity [2]: although most of the time exempli-
fied with commutative type cycles of length three, for which a diagram made out of
mappings f : A  B, g : B  C, and h : A  C commutes iff (i.e. if and only if ) h = g 
f, they can be generalized to any cycle length greater than 1; given any mappings f1 : A1
 A2, f2 : A2  A3, …, fn : An  An + 1, g1 : A1  B1, g2 : B1  B2, …, gm : Bm – l  An +
1, for some strictly positiv e naturals n and m, such a diagram commutes iff fn  …  f2 
f1 = gm  …  g2  g1.
Recall that the technique used for deciding whether a diagram commutes is the fol-
lowing: you consider any element of the source, compute for it both elements of the
destin ation for each path and wonder whether they should always be the same; if they
should, then the diagram commutes.
Let us consider, for example, the commutative -type diagram from Fig. 2 (having n
= m = 2, length n + m = 4, STATES as source and CONTINENTS as destination).
Continent
REGIONS CONTINENTS

Region Continent

STATES COUNTRIES
Country
Fig. 2. An example of a commutative diagram of length four
As, for any state, both the country and the region to which it belongs must belong to
a same continent this diagram commutes and the corresponding constraint ( C1) should
be added to this db scheme: C1: Contin ent  Country = Continent  Region
Failing to enforce this constraint might allow storing implausible data such as Texas,
which is a state of the U.S.A., which belongs to North America, belongs to the South
America’s Andes region.
A particular case of com mutative diagrams that needs a special type of treatment
was already discussed in [ 9] (see best practice rule R -DA-7 from section 2.10.7): those
for which either n or m is equal to one. Whenever the corresponding computable map-
pings are not canonical ones and null values are not interfering with them either, they
might and should be broken (by eliminating the mapping that is computable from the
other ones forming the cycle or by replacing it with a computed one).
For example, the commutative -type diagram of Fig. 3 ( n = 1, m = 3, length 4, source
CUSTOMERS , destination COUNTRIES ) commutes (i.e. CCountry = Country  State
 CCity ), as, for any customer, the country where it has its headquarters is the country
containing the state that includes the city where i ts headquarters are located.
The cycle in this E -RD should be broken, by dropping CCountry (which may be
computed anytime when needed), implying that no extra constraint is needed anymore.
Whenever querying speed is critical or updates to CCountry are much less frequent
than queries involving it (and additional needed db space is affordable), it may be added

as the computed function * CCountry = Country  State  CCity (with controlled redun-
dancy , i.e. being read -only to end -users and automatically updated w henever changes
occur in CCity , State , and/or Country corresponding values, by trigger -like methods);
note that this solution (see Fig. 4) is as costly as the initial one with the commutativity
constraint added too, since plausibility is always guaranteed .
CCity
CUSTOMERS CITIES

CCountry State

COUNTRIES STATES
Country
Fig. 3. An example of a breakable com-
mutative diagram CCity
CUSTOMERS CITIES
*CCountry State

COUNTRIES STATES
Country
Fig. 4. Resulting E -RD after replacing in
Fig. 3 the computable CCountry with the
correspondingly computed * CCountry
Moreover, in such cases, even if costlier, in fact it is often better that this redundant
function does not store pointers to the corresponding countries, but plain names for
customer cities, states, and countries (i.e. * CCity = CityName  CCity , *CState = Stat-
eName  State  CCity , and * CCountry = CountryName  Country  State  CCity ), like
in Fig. 5: with this solution, when querying data about customers, only CUSTOMERS
have to be accessed (whereas even in the previous one, from Fig. 4, for getting corre-
sponding city, state, and country names too, all four un derlying tables have to be ac-
cessed).
Theoretically, cycle breaking can be done in some cases even if both n and m are
greater than one: for example, if f  g = e  h and, say, f is bijective, then g is obviously
computable ( g = f –1  e  h, where f –1 : B  A is the inverse of f : A  B, i.e. f  f –1 =
1A and f –1  f = 1B). However, bijective functions are not at all interesting in conceptual
data modeling, as equipotent object sets should always be merged into only one set [ 9,
11].
CCity
CustNam e CUSTOMERS CITIES CityName

*CCity *CCountry *CState State

CountryName COUNTRIES STATES StateName
Country
Fig. 5. Resulting E -RD after optimizing the co ntrolled redundancy of the one in Fig. 4
It is true that ontoness is easily achievable by restricting the co -domains to the cor-
responding function images, so one -to-oneness might be sometimes enough to obtain
at least partially reversible functions. For ex ample, we could declare CAPITAL_CITIES
= {xCITIES | yCOUNTRIES , Capital (y) = x} and the restricted Capital :
COUNTRIES  CAPITAL_CITIES becomes bijective.

Generally, however, commutativity constraints do not embed all needed one -to-one
mappings to be a ble to compute one of the involved ones from the rest of them, so the
only choice in such cases is to enforce them. For example, in C1 above there is no one –
to-one mapping, as, generally, continents include both several regions and countries,
whereas both countries and regions include several states.
Moreover, there are cases when commutative -type diagrams cannot be broken even
when n = 1 or m = 1. The first one is whenever the syntactically computable mapping
is not also semantically computable because it is a canonical one. For example, the
cycle from Fig. 6 is obviously of commutative -type (with n = 1, m = 2, length 3, source
ISLANDS_SHARING , and destination COUNTRIES ), but you should never wonder
whether it should commute, as SharingCountry is a canonica l Cartesian projection, so
it is not computable.
Area Population
ISLANDS_SHARING
IslandPopulation
Island SharingCountry

IslandArea ISLANDS COUNTRIES
Country
Fig. 6. An example of an unbreakable commutative type E -RD cycle, because canonical Car-
tesian projections are not computable
In this example, Country stores the country which either fully owns the correspond-
ing island or the biggest part of it; if an island is fully owned by only one country, then
ISLAND_SHARING does not store anything on it; for example, nothing is stored for
Britain; for shared islands, all other countries (except for the one stored in Country , as
no data should be stored more than once in any db, according to axiom A-DA03 from
[9]) are stored in it (together with the corresponding area and population); for example,
Country stores for Ireland the Irish Republic and ISLAND_SHARING stores for it the
United Kingdom of Great Britain and Northern Ireland.
Obviously, this cycle should not commute, but if no constraint is associated with it,
then users might violate axiom A-DA03 , for example by also adding in
ISLAND_SHARING a pair <Ireland, Irish Repub lic>. To prevent it, the following anti –
commutativity constraint (corresponding to the business rule “no country may own
more than one share of any island”) should be added to th is Geography db scheme:
C’: (xISLANDS )(yISLANDS_SHARING )
(Country (x) = SharingCountry (y)  Island (y) ≠ x)
Moreover, trivially, another constraint must be added to this E -RD cycle too in order
to prevent storing implausible data, namely: “For any shared island, the sum of the areas
owned by all corresponding sharing countries sho uld be at most equal to the total island
area; similarly, the sum of the populations of the corresponding areas should also be at
most equal to the total island population”. Its formalization is:
C’’: (xISLANDS )(yISLANDS_SHARING , Island (y) = x)
(Islan dArea (x) ≥ sum(Area (y))  IslandPopulation (x) ≥ sum(Population (y)))

Obviously, C’ and C’’ above may be merged into the following equivalent con-
straint: C: (xISLANDS )(yISLANDS_SHARING , Island (y) = x)
(Country (x) ≠ SharingCountry (y)  IslandArea (x) ≥ sum(Area (y)) 
IslandPopulation (x) ≥ sum(Population (y)))
In (E)MDM, because it is associated to an E -RD cycle, such an object constraint is
considered of type generalized commutativity and the corresponding cycle is said to
unconventionally commute according to that constraint. Obviously, any E -RD cycle of
length at least 2 might have such an associated constraint.
To conclude, whenever f = f1 or g = g1, you should not ever wonder whether f = gm 
…  g2  g1 or g = fn  …  f2  f1 conventionally commute if f or g are a canonical
projection, inclusion, or surjection, but only if the corresponding commutative -type cy-
cle unconventionally commutes.
The second case in which commutative cycles cannot be broken is due to interactions
with null values. For example, c onsidering the commutative -type diagram from Fig. 7
(n = 1, m = 5, length 6, source RIVERS , destination CONTINENTS ), let us first note
that Mountain may take null values too (as there are rivers that do not take their sources
from mountains). Obviously, wh enever it doesn’t, this diagram is commuting ( Conti-
nent = Continent  Range  Subrange  Group  Mountain ), because any river that
springs from a mountain belongs to the same continent as that mountain.
For example, the Mississippi has its source at only 4 50m altitude in the Itasca lake;
as its source is not in the mountains, Mountain has for it a null value, which makes
impossible computing its continent from Continent  Range  Subrange  Group 
Mountain ; dually, the Danube springs from the Southeastern Black Forest mountains,
a massive of the European Alps, so the db should enforce the constraint that the Danube
cannot belong to any other continent but Europe.
Continent Continent
RIVERS CONTINENTS MOUNTAIN_RANGES
Mountain Range

MASSIVES MOUNT_GROUPS MOUNT_SUBRANGES
Group Subrange
Fig. 7. An example of a commutative diagram with a non -total mapping
To conclude with, no commutative cycle cont aining at least one non -totally defined
mapping should be broken either.
For easing their task, MatBase does not allow its users to break unbreakable cycles.
3.2 Anti -Commutative Function Diagrams
Sometimes, as we’ve already seen with constraint C’ associated to the cycle from Fig.
6 above, commutative -type diagrams are anti -commuting (i.e. commutativity’s dual):
(xA1)((fn  …  f2  f1)(x) ≠ gm  …  g2  g1)(x)). Let us also consider, for example,
the commutative -type diagram from Fig. 8 (having n = 3, m = 2, length n + m = 5,
ISLANDS_SHARING as source and CONTINENTS as destination), in which OCEANS
is a subset of CONTINENTS (i.e. oceans are considered as being continents too, because

data for them is identical, except for some dualisms –e.g. MaxAltitude stores for oceans
the corresponding maximum depth -, and a Boolean Ocean? is distinguishing between
them: OCEANS = {xCONTINENTS | Ocean? (x)} and iOCEANS is the associated canon-
ical inclusion mapping (i.e. iOCEANS (x) = x, xOCEANS ).

ISLANDS_SHARING
Islan d SharingCountry

ISLANDS COUNTRIES
Ocean Continent
OCEANS  CONTINENTS
iOCEANS
Fig. 8. An example of an anti -commutative E -RD cycle
Trivially, as, for any country sharing a part of an island, the continent to which it
belongs must be distinct from the ocean to which that island belongs, this diagram anti –
commutes and the corresponding constraint ( C2) should be added to this db scheme:
C2: (xISLANDS_SHARING )((iOCEANS  Ocean  Island )(x) ≠ Continent 
SharingCountry )(x))
The technique used for deciding whether a diagram anti -commutes is almost identi-
cal to the one employed for commutative ones: you consider any elem ent of the source,
compute for it both elements of the destination for each path and wonder whether they
are never the same; if they are, then the diagram anti -commutes.
Please note that anti -commutativity is a much stronger constraint than function ine-
quality; for example, let us denote by f = fn  …  f2  f1 and by g = gm  …  g2  g1,
both of them being functions defined on A1 and taking values from An + 1; by function
equality definition, as they have same domains and codomains, f = g iff f(x) = g(x),
xA1; when negating this definition for such mappings (i.e. having same domains and
codomains), it trivially follows that f ≠ g iff xA1 such that f(x) ≠ g(x), which is much
weaker than anti -commutativity (that requires this inequality to hold for any value of x,
not for just one or some of them).
3.3 Commutative -Type Diagrams that Commute Unconventionally
As constraint C proves (see Fig. 6 above), commutativity -type E -RD cycles may also
have associated generalized commutativity constraints.
The technique u sed for deciding whether a commutative -type diagram unconven-
tionally commutes is almost identical to the one employed for (conventional) commu-
tative ones: you consider any element of the source, compute for it both elements of the
destination for each path and wonder whether there is any other kind of connection
between them (other than equality and inequality); if there is, then the diagram has the
corresponding associated generalized commutativity constraint.

3.4 Peculiarities of Commutative -Type Diagrams of Length 2
“Degenerated” commutative -type diagrams of length two need special treatment:
First, any commutative one should always be broken, by eliminating any of the two
involved mappings: what would be the sense of storing in a table two columns that must
always be identical?
Anti-commutativities should always be enforced, just like for corresponding cycles
of length greater than two. For example, to the BOARDING_PASSES set from Fig. 9,
the following constraint should be added:
(xBOARDING_PASSES )(Departu re(x) ≠ Destination (x)).
Departure
BOARDING_PASSES AIRPORTS
Destination
Fig. 9. An example of an anti -commutative diagram of length two
Note that, in this particular case of commutative -type diagr ams of length two, made
out of mappings f : D  C and g : D  C, commutativity corresponds to f • g reflexivity
and anti -commutativity to f • g irreflexivity.
Generally, according to the equivalence between E -R and functional data modelling
[8, 11], entity -type object set D is equivalent to a dyadic relationship -type object set D’,
whose canonical Cartesian projections are f and g; hence, all homogeneous binary func-
tion products (i.e. products of two functions having same co -domain) may also have
any dyadic relation properties. Consequently, in the framework of (E)MDM, for such
diagrams it is natural to also investigate f • g for symmetry, asymmetry, transitivity,
intransitivity, Euclideanity, inEuclideanity , acyclicity, and connectivity.
Let us consider, f or example, the diagram from Fig. 10, in the context of any kind
of championship w here each team plays against any other one twice (once home and
once away): HomeTeam
MATCHES TEAMS
VisitingTeam
Fig. 10. An example of a length two diagram having several associated dyadic type constraints
As, trivially, no team may play against itself, this diagram is anti -commuting, i.e.
HomeTeam • VisitingTeam is irreflexive; as there are always two matches between any
two teams (with each of them playing once home and once away) HomeTeam • Visit-
ingTeam is symmetric too; as it is a championship (i.e. any team must play against all
other ones) HomeTeam • VisitingTeam is transitive, Euclidean, and connected too; as
it is symm etric, it cannot be acyclic. Consequently, the following constraints should be
added to th is MATCHES scheme: HomeTeam • VisitingTeam irreflexive , symmetric ,
transitive , Euclidean , connected .

Similar to autofunctions, dyadic relation properties are related by several implica-
tions [ 11], out of which in this context the following are relevant: acyclicity implies
asymmetry; asymmetry, intransitivity, as well as inEuclideanity imply irreflexivity.
3.5 Uninteresting Commutative -Type Diagrams
Generally, most of th e commutative -type diagrams are uninteresting, as they do not
have any associated constraint, like, for example, the one from Fig. 11 (having n = 2,
m = 2, length 4, STATES as source and CITIES as destination ; Capital is one -to-one as
no city may simultane ously be the capital of more than one country ).
Capital
REGIONS CITIES

Region Capital
STATES COUNTRIES
Country
Fig. 11. An example of an uninteresting commutative -type d iagram
Obviously, as there is only one state per country to which the country capital belongs
(and even fewer ones for which the capitals of the regions to which they belong is also
the corresponding country’s capital), this diagram does not commute.
Duall y, it does not anti -commute either: for example, Bucharest is the capital of both
Romania and the Bucharest state. Moreover, it does not have any other associated con-
straint, so it is uninteresting: considering any state s belonging to a region r that has
capital c and to a country t that has capital c’ there is no relation whatsoever between c
and c’ (as sometimes c’ = c, sometimes c’ ≠ c, and sometimes c and/or c’ may even be
nulls).
3.5 Commutative -Type Cycles Analysis
For any commutative -type diagram of len gth > 2 the following should be done:
➢Check whether it is (conventionally) commuting;
If yes, then
✓Check whether cycle can be broken; if yes, then
❖Break cycle by removing the computable mapping and, if needed, add com-
puted mapping(s) instead
✓If no , then add corresponding commutativity constraint
➢If no, then check whether it is anti -commuting; if yes then
✓Add corresponding anti -commutativity constraint
➢Check whether it is unconventionally commuting; if yes, then
✓Add corresponding generalized commutativity constraint
For any commutative -type diagram of length two the following should be done:
➢Check whether it is commuting; if yes, then
✓Break cycle by eliminating any of the two involved functions.

➢If no, check whether it is anti -commuting ; if yes, then
✓Add corresponding irreflexivity constraint.
➢Check whether the function product is acyclic; if yes, then
✓Add corresponding acyclicity constraint.
➢If no, then
✓Check whether the function product is symmetric; if yes, then
❖Add corres ponding symmetry constraint.
✓If no, check whether the function product is asymmetric; if yes, then
❖Add corresponding asymmetry constraint.
➢Check whether the function product is transitive; if yes, then
❖Add corresponding transitivity constraint.
✓If no, check whether the function product is intransitive; if yes, then
❖Add corresponding intransitivity constraint.
➢Check whether the function product is Euclidean; if yes, then
❖Add corresponding Euclideanity constraint.
✓If no, check whether the fu nction product is inEuclidean; if yes, then
❖Add corresponding inEuclideanity constraint.
➢Check whether the function product is connected; if yes, then
✓Add corresponding connectivity constraint.
4 Circular -Type E -RD Cycles
To any node of a circular -type cycle a corresponding composed autofunction is associ-
ated. As such, we should always investigate what properties such auto -functions have
(among reflexivity, irreflexivity, symmetry, asymmetry, idempotency, anti -idempo-
tency, and acyclicity).
4.1 Reflexivi ty and Irreflexivity
Most frequently, circular -type cycles have associated reflexivity constraints (e.g. Fig.
1). For example, let us consider the diagram from Fig. 12 (length 3, all nodes are inter-
mediate ones): Continent
1REGIONS REGIONS CONTINENTS 1CONTINENTS

Region MaxAltitudeSite
1SITES
SITES
Fig. 12. Another example of a locally commutative circular -type diagram
1. Considering any region r belonging to a continent c having the maximum altitude
site s belonging to region r’ it is obvious that r and r’ are not always equal (and not
always unequal either, as ther e is only one maximum altitude site per continent, but
there are several regions in a continent). Consequently, this diagram does not either
commute or anti -commute in its REGIONS node.
2. Considering any continent c having the maximum altitude site s belonging to re-
gion r’ of continent c’ it is obvious that c and c’ are always equal. Consequently, this

diagram commutes in its CONTINENTS node and the corresponding constraint Conti-
nent  Region  MaxAltitudeSite reflexive should be added to the CONTINENTS
scheme. If failing to enforce it, users might store such implausible data as the Death
Valley, which contains the lowest altitude point of North America, belongs to the South
America’s Andes region.
3. Considering any site s belonging to region r belonging t o a continent c having the
maximum altitude site s’ it is obvious that s and s’ are not always equal (and not always
unequal either). Consequently, this diagram does not either commute or anti -commute
in its SITES node either.
The technique employed for ch ecking whether a circular -type diagram locally com-
mutes in one of its nodes is obviously a particularization of the one used for (conven-
tional) commutative ones: you consider any element of the current source node, com-
pute for it the value of the correspon ding composed mapping and wonder whether they
are always the same; if they are, then the diagram locally commutes in that node (as the
composed function is reflexive, i.e. equal to that node’s unity mapping); if they should
always be distinct, then the dia gram anti -commutes.
Composed function reflexivity is also called in the (E)MDM local commutativity
because it is a particular case of (conventional) commutativity, where one member of
the equality is a unity mapping. For example, the diagram from Fig. 12 a bove locally
commutes in CONTINENTS , as Continent  Region  MaxAltitudeSite = 1CONTINENTS .
Similarly, corresponding irreflexivities are called local anti -commutativities . For ex-
ample, let us consider the circular cycle from Fig. 13 (where iEMPLOYEES is the canonical
injection associated to the inclusion EMPLOYEES  PEOPLE and MD stores for any
person his/her doctor of medicine): as nobody may be his/her own MD, it is obviously
anti-commuting in EMPLOYEES (i.e. MD(iEMPLOYEES (x))  x, xEMPLOYEES ).
MD
EMPLOYEES  PEOPLE
iEMPLOYEES
Fig. 13. An example of a locally anti -commutative circular -type diagram
4.2 Circular -Type Diagrams that Have Other Associated Constraint Types Too
Let us co nsider, for example, the circular diagram (length 2, all nodes are intermediate
ones, and RootFolder is one-to-one, as no folder may be the root one for more than one
logic drive) from Fig. 14.
FILES

LogicDrive RootFolder

LOGIC_DRIVES
Fig. 14. A circular -type cycle that has an associated idempotency constraint too

Let us analyze first whether it is locally commuting in node LOGIC_DRIVES , i.e.
Logic Drive  Root Folder reflexive ?; considering any logic drive x, x is either not for-
matted (i.e. RootFolder (x)  NULLS) or it is, in which case it has a root folder y =
RootFolder (x)  FILES ; as any file, y should belong to a logic drive and it is obvious
that it has to belong to x, the logic drive whose root folder it is (trivially, no root folder
of a logic drive may belong to another one), i.e. x = Logic Drive (y), which means that
this mapping composition is reflexive.
Being reflexive, as autofunction reflexivity impli es both symmetry and idempo-
tency, it is also symmetric and idempotent, but these constraints should not be added to
this db scheme, as it would become not minimal. Being reflexive, it cannot be acyclic
(as its graph is made out only of length one cycles).
Consequently, the constraint Logic Drive  RootFolder reflexive must be added to
LOGIC_DRIVES .
Let us analyze now whether it is locally commuting in node FILES , i.e. RootFolder
 Logic Drive reflexive ?; considering any file x, x belongs to a logic drive y = Logic –
Drive (x); as it has at least one file, y has to be formatted, so there is a folder z belonging
to FILES such that z is the root folder of y: z = RootFolder (y)  FILES ; trivially, as not
all files in a logic drive may be its root folders, generally x ≠ z, i.e. this cycle is not
locally commuting in FILES , that is RootFolder  Logic Drive ≠ 1FILES.
Then, we should analyze whether it is locally anti -commuting in node FILES , i.e.
RootFolder  Logic Drive (x) irreflexive ?; using the reasoning dual to the o ne above, it
is trivial too that this is not true, as any formatted logic drive has to have a root folder,
for which x = z.
Then, we should analyze whether f = RootFolder  Logic Drive is symmetric (i.e. f 2
= 1FILES): using above notations, for any file x, z = RootFolder (y)  FILES , y = Logic –
Drive (z) (as any file stored on a logic drive is stored on the same drive as its root folder),
so f 2 = f, which obviously means that f is not symmetric, but it is idempotent.
It is very easily provable that f is neit her asymmetric (as equality holds for any root
folder), hence nor acyclic either . Consequently, constraint RootFolder  Logic Drive
idempotent must be added to this db scheme too.
Generally, in each node of any circular -type diagram the corresponding compo sed
autofunction should be investigated just like explained in section 2 above.
Obviously, the techniques used to discover any other (but reflexivity) constraint
types that are associated to circular -type cycles are based on the corresponding type
definiti ons and are very similar to the ones employed for the corresponding autofunc-
tions ones: the only difference is that instead of dealing with an atomic function, in such
cases we deal with composed ones.
Moreover, as circular -type diagrams may also have asso ciated generalized con-
straints, their existence should be considered too. For example, the diagram from Fig.
15 (where SOLAR_SYSTEMS is modeled as a subset of CELESTIAL_BODIES , with
Sun as the corresponding canonical inclusion) has associated not only the constraint
“the sun of any solar system should belong to its solar system” (i.e. SolarSystem  Sun
reflexive ), but also the generalized (unconventional) commutativity one ”solar systems
may not contain solar systems” (i.e. ( x,ySOLAR_SYSTEMS )(SolarSystem (Sun(x)) 
y  SolarSystem (Sun(y))  x)).

SolarSystem
SOLAR_SYSTEMS  CELESTIAL_BODIES
Sun
Fig. 15. An example of a circular -type diagram that has an associated generalized commuta-
tivity constraint
In this case, fortunately, this constraint should not be enforced, as it is implied by
the reflexivity of SolarSystem  Sun, hence it is redundant.
5 Generalized Commutativities
Let us consider, for example, the general -type cycle from Fig. 16 (length 7, source
nodes NEIGHBOR_SEAS and NEIGHBOR_OCEANS , destination nodes COUNTRIES
and CONTINENTS ).
Consider any country c that is neighbor to a sea s which belongs to an ocean o (for
example c = France, s = English Channel; o = Atlantic); by transitivity, it follows th at
c is also neighbor to o, so that this diagram has the following associated generalized
commutativity constraint (“any country that is neighbor to a sea embedded in an ocean
is also neighbor to that ocean”): (xNEIGHBOR_SEAS , Ocean (Sea(x))NULLS)
(yNEIGHBOR_OCEANS )(SCountry (x) = OCountry (y) 
OOcean (y) = Ocean (Sea(x)))
Ocean i OCEANS iOCEANS
SEAS OCEANS  CONTINENTS OCEANS
Sea OOcean

NEIGHBOR_SEAS COUNTRIES NEIGHBOR_OCEANS
SCountry OCo untry
Fig. 16. An example of general -type diagram that has an associated generalized commutativity
constraint
Failing to enforce this constraint might allow users to store in the corresponding db
such implausible data as Fra nce is neighbor to the English Channel, which is embedded
into the Atlantic Ocean, but France is not neighbor to the Atlantic as well.
The technique used for deciding whether or not a general -type diagram unconven-
tionally commutes is of the same type to th e one employed for (conventional) commu-
tative ones: you consider any element of a source, compute for it both elements of the
destination for each path and wonder whether there is any other kind of connection
between them and those similarly obtained for a ny or at least for one element of another
source; if there is, then the diagram has the corresponding associated generalized com-
mutativity constraint.
To conclude, for any general -type diagram you should check whether it has an asso-
ciated generalized commu tativity constraint and whenever this is the case you should
add it to the corresponding db scheme.

6 Constraints Associated to Adjacent Cycles
Two cycles are adjacent if they share at least one node. Sometimes, adjacent cycles
have associated constraints to o.
For example, the constraint “any two neighbor countries should belong either to a
same continent or to neighbor continents” is associated to the three adjacent cycles from
Fig. 17 (all of them of type commutative, two having length 2 and the one betwee n
them length 3), where Continent : COUNTRIES  CONTINENTS stores, for each
country, the continent where their capital is located (e.g. North America for the U.S.A.,
Europe for Russia, Asia for Turkey, etc.), while the COUNTRIES_CONTINENTS bi-
nary relations hip stores the other continents on which countries may also span, if any
(e.g. Australia and Oceania for the U.S.A., with Hawaii, Asia for Russia, Europe for
Turkey, etc.). Obviously, failing to enforce it might allow users to store in
NEIGHBOR_COUNTRIES such implausible data as South Africa being neighbor to
Brazil.
NEIGHBOR_
CONTINENTS
Continent NeighborContinent
CONTINENTS
Continent COUNTRIES_
Continent CONTINENTS
Country
COUNTRIES
Country NeighborCountry
NEIGHBOR_
COUNTRIES
Fig. 17. An example of three adjacent cycles having an associated constraint
Formalization of this const raint is the following: ( xNEIGHBOR_COUNTRIES )
(Continent (Country (x)) = Continent (NeighborCountry (x)) 
(yCOUNTRIES_CONTINENTS )(Country (x)) = Country (y))  Continent (Neigh-
borCountry (x)) = Continent (y)  NeighborCountry (x)) = Country (y)  Conti-
nent(Country (x)) = Continent (y))  (zNEIGHBOR_CONTINENTS )(Continent (z) =
Continent (Country (x))  NeighborContinent (z) = (NeighborCountry (y))  Conti-
nent(z) = Continent (NeighborCountry (x))  NeighborContinent (z) = Continent (Coun-
try(y))))
7 MatBase E-RD Cycles Analysis Assistance Algorithm
Fig. 18 and 19 show the pseudocode algorithm for assisting analysis of E -RD cycles
and discovery of all their associated constraints, which summarizes all the above and
that is implemented in both current MatBase versions :
ALGO RITHM A1. MatBase E-RD Cycles Analysis Assistance

Input : a db scheme S and its associated set of E -RDs
Output : S augmented with the newly discovered constraints associated to its E -RD
cycles (if a ny).
loop for all E-RDs d
loop for all autofunctions a of d
investigateAutoFunction (a);
end loop ;
loop for all cycles c of d having n = length (c) > 1
case type(c) :
commutative:
if length (c) > 2 then
if c anti-commutes then S = S  {c anti -commutes };
else
if c commutes then
if c can be broken by eliminating edge f from it then
if it is not d esired that computed mappings be added
then drop f;
else replace f by the corresponding computed ones;
end if ;
else S = S  {c commutes };
end if ;
end if ;
end if ;
else // cycle of length 2 (mappings f and g)
if f = g then remove redundant f or g;
else if c anti-commutes then S = S  {f • g irreflexive };
if f • g is acyclic then S = S  {f • g acyclic };
else if f • g symmetric then S = S  {f • g symmetric };
else if f • g asymmetric then
S = S  {f • g asymmetric }  {f • g irreflexive };
end if ;
end if ;
if f • g transitive then S = S  {f • g transitive };
else if f • g intransitive then
S = S  {f • g intransitive }  {f • g irreflexive };
end if ;
if f • g Euclidean then S = S  {f • g Euclidean };
else if f • g inEuclidean then
S = S  {f • g inEuclidean }  {f • g irreflexive };
end if ;
if f • g is connected then S = S  {f • g connected };
end if ;
end if ;
circular:
loop for all edges f = fi + 1 … fn  f1 … fi of c (1 ≤ i ≤ n)
investigateAutoFunction (f);

end loop ;
end case type(c) ;
if c unconventionally commutes according to constraint G then S = S  {G};
if c and some adjacent cycle(s) unconventionally commute according to constr aint
G’ then S = S  {G’};
end loop (for all cycles c of d);
end loop (for all E -RDs d);
End ALGORITHM A1;
Fig. 18. Algorithm A1 (MatBase assistance for analyzing E -RD cycles )
ALGORITHM A2. MatBase investigat eAuto Function (f) procedure
if f is acyclic then
S = S  {f acyclic };
if f is idempotent then S = S  {f idempotent };
else if f is anti -idempotent then S = S  {f anti-idempotent };
end if ;
else
if f is reflexive then
if f is atomic and totally defined then remove f;
else S = S  {f reflexive };
end if ;
else if f is symmetric then S = S  {f symmetric };
else if f is asymmetric then S = S  {f asymmetric };
end if;
if f is idempotent then S = S  {f idempotent };
else if f is anti -idempotent then S = S  {f anti-idempotent };
end if ;
if not (f asymmetric or f anti-idempotent) then
if f is irreflexive then S = S  {f irreflexive };
end if ;
end if ;
end if ;
End ALGORITHM A2;
Fig. 19. Algorithm A2 (MatBase investigateAutoFunction procedure )
8 Results and Discussion
8.1 Algorithm Complexity and Optimality
It is very easy to check that this algorithms is very fast, as its time complexity is O(|AF|
+ |C>1|) (i.e. linear in the sum of the cardinals of the set of single autofunctions and
compound ones associated to the nodes of its circular -type cycles (denoted AF) and the
one of the greate r than 1 length non -circular cycles subset (denoted C>1)): each single
autofunction (i.e. length 1 cycle) is considered only once; each cycle of length 2 is
considered at most twice (which is the number of compound autofunctions associated

to its node, for circular ones; for commutative ones it is considered only once); for any
cycle of length greater than 2, if it is commutative or general is considered only once,
but if it is circular every compound autofunction associated to its nodes is considered.
More over, this algorithm is also optimal, as, using math (e.g. the second algorithm
from the previous section) , it asks db designers the minimum number possible of ques-
tions for any cycle type and subtype . For example, trivially, if something is reflexive,
it cannot be irreflexive (and the same goes for any dual pair of properties, e.g. those
corresponding to symmetry, transitivity, idempotency, and Euclideanity); not that ob-
vious: if a dyadic relation is acyclic, then it is also irreflexive , asymmetric, and an ti-
idempotent; autofunctions cannot be Euclidean or connected ; transitivity for autofunc-
tions is called idempotency .
8.2 Algorithm Usefulness
First, analyzing E -RD cycles is interesting even per se , within the study of sets, func-
tions, and relations semi -naïve algebra, as it helps getting a better understanding on
function diagram commutativity and anti -commutativity, as well as on dyadic relation
properties of both single and compound autofunctions a nd homogeneous binary func-
tion products . Moreover, the genera lized commutativity constraints (e.g. the one at-
tached t o the cycles presented in Fig. 6 and 15 to 17 ) are excellent real -world examples
of closed first order predicate calculus with equality formulas.
The main utility of this algorithm is, of course, in t he realms of data modeling, db
constraints theory, db and db software applications design and development.
All constraints (business rules) that are governing the sub -universes modeled by dbs,
be them relational or not, should be enforced in the correspond ing dbs’ schemas: oth-
erwise, their instances might be implausible. Structural E -RD cycles have sometimes
associated non -relational constraints that may be much more easily discovered by ap-
plying the assistance algorithm presented in this paper.
Generally, almost all autofunctions have associated non -relational constraints. Very
many circular -type cycles have reflexivity (but not only) type constraints associated. A
significant number of commutative -type cycles also have associated constraints, while
some of them should be broken by eliminating computable functions (or sometimes
replacing them with redundant computable ones). Although infrequently, even general –
type cycles have associated constraints, especially when their length is small.
For example, in a g eography db (from which we’ve extracted almost all examples
presented in this paper) that has in its E -RD 63 nodes and 352 edges there are 21,806
cycles of le ngth at most 16, out of which 36 are circular, 8 50 commutative, and the rest
are of the general ty pe. Analyzing them with the help of this algorithm, we discovered
7 circular cycles that have a reflexivity constraint associated to one of their associated
compound autofunctions, 4 having reflexivity and 7 irreflexivity ones, 4 commutative –
type cycles th at commute and are unbreakable, 8 which are anti -commutative , 9 irre-
flexivities, 8 asymmetries, and one acyclicity for compound autofunctions, 1 6 general-
ized commutativity constraints (out of which 6 are associated with adjacent cycles), and
plus 7 acyclic autofunctions and one that is irreflexive, as well as one acyclic, 8 asym-
metric, and 9 irreflexive dyadic relations .

Obviously, except for single autofunctions, this algorithm may be used only after all
cycles of a db E -RD have been detected and classifie d, which is done by MatBase too
[13], as a prerequisite of applying it .
9 Hints on Enforcing Non -Relational Constraints in MatBase
Unfortunately, the state of the art in db and db software application design and devel-
opment related to non -relational constrai nts is exclusively using ad -hoc approaches:
very few db and/or software architects are aware of their types, optimal enforcing ways
per type, algorithmic approaches to discover all of them for any sub -universe of dis-
course, automatic enforcement, and even of their paramount importance; only from ex-
perience and common sense (e.g. nobody may be simultaneously present in several
places, no slot may be simultaneously occupied by several objects, etc.) are they con-
sidering some such constraints and enforce them in db software applications (through
either RDBMS triggers in extended SQL or/and high level programming languages
trigger -type methods).
Very many such constraints are only discovered in production, in time, generally by
db software application users, wh o report them as bugs. It would be highly preferable,
of course, that db and software architects discover all of them in the data modeling
phase and then developers enforce them from the beginning, up until MatBase (or/and
other similar advanced DBMS produ cts) will become worldwide available, to provide
automatic code generation for enforcing such constraints too, just like it is the case
today with the relational ones.
Structural functions are implemented in relational dbs as foreign keys. Database ap-
plica tions are presenting them to users as combo -boxes. Generally [ 11], whenever pos-
sible, non -relational constraints should be enforced preventively, by eliminating from
these combo -boxes all implausible data. When this is not possible [ 11], they should be
enforced through triggers or trigger type methods. Here are some hints on how MatBase
automatically generated code is enforcing non -relational constraints associated to E –
RD cycles.
For example, the anti -commutative constraint C2 (see Fig. 8 above) is prevent ively
enforced by simply adding in the Continent combo -box row/data source SQL statement
of the forms based on the COUNTRIES table the clause WHERE not [Ocean? ] and in
the Ocean one of the forms based on the ISLANDS table the dual clause WHERE
[Ocean?, thu s guaranteeing that users can select in Continent only continents and in
Ocean only oceans, which , trivially, could never violate constraint C2.
Similarly, the reflexivity constraint associated to Fig. 1 above is preventively en-
forced partially with only t wo VBA / C# statements of the Current event -driven method
associated to cursor entering on a line: the first one dynamically changes the WHERE
clause of the Capital combo -box of the forms based on the COUNTRIES table, such
that only cities belonging to the current country are selected, and the second one re –
queries the combo -box to apply its changed definition. However, this constraint might
be also violated whenever users were moving capital cities to another country: there-

fore, MatBase also automatically generates code in the BeforeUpdate (for its MS Ac-
cess version) and Validating (for its MS .NET version) event -driven methods attached
to the Country combo -box of class CITIES forms to reject such requests.
Autofunction associated constraints are also enfor ced by MatBase through automatic
generated code for the corresponding combo -boxes in their BeforeUpdate / Validating
event -driven methods to reject invalid requests. Acyclicity -type constraints, the hardest
to enforce, need more complex algorithms: out of the many possible ones, for speed
reasons, MatBase favors one based on partially computing transitive closures, by using
the semantics of the least fixpoint of relational algebra equation systems [ 11].
For dyadic relations and homogeneous binary mapping pr oducts, as there are two
combo -boxes involved, MatBase generates needed code for enforcing their constraints
in the corresponding BeforeUpdate / Validating event -driven methods of the related
forms: trying to enforce them at each of the two involved combo -boxes would annoy
users, by imposing on them certain updates order and/or tricks. For example, if a plane
ticket from Bucharest to Helsinki was initially wrongly entered in the db as one from
Helsinki to Bucharest, then, when enforcing too early this const raint (i.e. at combo –
boxes levels), to correct it users should use first another third airport; only enforcing it
later, at the form level, after both departure and destination airports have been updated,
values swapping is possible simply, without any tri ck.
For commutative function diagrams (e.g. C1 associated to the cycle from Fig. 2
above), MatBase generates in the corresponding combo -boxes of the source node (e.g.
Region and Country of STATES in Fig. 2), as well as in each corresponding ones of the
involved intermediate nodes (e.g. Continent of both REGIONS and COUNTRIES in
Fig. 2) needed code in their BeforeUpdate / Validating associated event -driven methods
for rejecting any update that woul d violate corresponding commutativity constraints.
Similarly, for general -type c ycles (e.g. the one from Fig. 16 above), MatBase is gen-
erating code for the source nodes where the existence quantifier applies (e.g.
NEIGHBOR_OCEANS in Fig. 16 ) in their Del ete event -driven methods to reject dele-
tion of rows that would violate the corresponding constraint (e.g. for not allowing de-
letion of <France, Atlantic>, for example, while there is data on seas embedded in the
Atlantic Ocean that are neighbor to France); similar code is also generated for their
form BeforeUpdate / Validating associated event -driven methods (e.g. for not allowing
update of <France, Atlantic>, for example, while there is data on seas embedded in the
Atlantic Ocean that are neighbor to Franc e); dually, for the source nodes where the
universal quantifier applies (e.g. NEIGHBOR_SEAS in Fig. 16 ), code is generated in
the AfterUpdate / Validated event -driven methods to automatically insert needed rows
in the existentially quantified ones, wheneve r needed (e.g. when inserting a <U.S.A.,
Mexico Gulf> row, for example, and Mexico Gulf belongs to the Atlantic Ocean, to
insert in NEIGHBOR_OCEANS a row <U.S.A., Atlantic> if it does not exist already;
similarly, if changing <U.S.A., Mexico Gulf> to <U.S. A., Alaska Gulf>, for example,
and the Gulf of Alaska belongs to the Pacific Ocean, to insert in NEIGHBOR_OCEANS
a row <U.S.A., Pacific> if it does not exist already); finally, just like for the commuta-
tive function diagrams, for every intermediate node co de is generated in the involved

combo -boxes (e.g. Ocean of SEAS and iOCEANS of OCEANS from Fig. 16 ) in their Be-
foreUpdate / Validating associated event -driven methods for rejecting any update that
would violate corresponding generalized commutativity const raints.
10 Conclusion
In summary, we have designed , implemented , and successfully tested in both MatBase
latest versions (for MS Access and C# and SQL Server) an algorithm for assisting de-
tection (and enforcement) of all non -relational constraints associated to E-RD cycles,
analyzed its complexity and optimality, as well as outlined its u sefulness for both sets,
functions, and relations algebra, and, especially, for data modelling, db constraints the-
ory, db and db software application design and development pr actices. Moreover, we
have also provided hints on how is MatBase automatically enforcing such constraints
through automatic code generation in the software applications managing correspond-
ing databases .
Very many non -relational db constraint types may be a ttached to E -RD cycles. The
algorithm presented in this paper helps users to analyze each such cycle exhaustively
and intelligently, such that they discover all non -relational constraints associated to
them in the minimum possible time . Moreover, MatBase also includes automatic en-
forcement of these constraints, through automatic co de generation .
This algorithm is successfully used both in our lectures and labs on Advanced Data-
bases (for the postgraduate students of the Mathematics and Computer Science Depar t-
ment of the Ovidius University, Constanta and the Computer Science Taught in English
Department of the Bucharest Polytechnic University) and by two Romanian IT compa-
nies developing db software applications for many U.S. and European customers in the
Fortu ne 100 ones.
References
1. Abiteboul, S., Hull, R., Vianu , V.: Foundations of Databases. Addison -Wesley, Reading,
MA (1995) .
2. Adámek, J ., Herrlich , H., Strecker , G. E .: Abstract and Concrete Categories (The Joy of
Cats) . John Wiley & Sons , Hoboken, NJ (1990) .
3. Chen , P. P. : The entity -relationship model: Toward a unified view of data. ACM Transac-
tions on Dat abase Systems 1(1), 9 –36 (1976) .
4. Codd , E. F. : A relational model for large shared data banks. CACM 13(6), 377 –387 (1970) .
5. Mancas , C.: A Deeper Insight into the Mathematical Data Model. In: Proc. 13th ISDBMS
Intl. Seminar on DBMS, pp. 122–134, ICI Bucharest, Romania (1990).
6. Mancas , C.: On knowledge representation using an Elementary Mathematical Data Model.
In: Proc. 1st IASTED Intl. Conf . on Information and Knowledge Sharing (IKS’02), pp. 206-
211. Acta P ress, Calgary, Canada (2002 ).
7. Mancas , C.: On Modeling Closed E -R Diagrams Using an Elementary Mathematical Data
Model. In : Proc. 6th ADBIS Conference on Advances in DB and Inf. Syst. , pp. 65-74. Slo-
vak Technology University Press, Bratislava, Slovakia (2002).
8. Mancas, C.: On the Equivalence between Entity -Relationship and Functional Data Model-
ling. In Proc. 7st IASTED Intl . Conf . on Software Engineering and Applications (SEA’03),
pp. 335 -340. Acta Press, Calgary, Canada (2003) .

9. Mancas, C.: Conceptual Data Mo deling and Database Design: A Com pletely Algorithmic
Approach. Volume I: The Shortest Advisable Path. Apple Aca demic Press / CRC Press,
Waretown, NJ (2015) .
10. Mancas, C.: Algorithms for key discovery assistance. In: Proc. 15th Intl. Conf. on Perspec-
tives in Business Informatics Research (BIR 2016) , LNBIP 261, pp. 322-338. Springer Ver-
lag, Berlin, Germany (2016 ).
11. Mancas, C.: Conceptual Data Modeling and Database Design: A Com pletely Algorithmic
Approach. Volume II: Refinements for an Expert Path. Apple Aca demic Press / CRC Press
(Taylor & Francis Group) , Waretown, NJ (201 9, in press ).
12. Mancas , C., Dorobantu , V.: On enforcing relational constraints in MatBase . London Journal
of Research in Comp. Sci. and Technology 17, 1 (Jan. 2017), 39 -45 (2017 ).
13. Mancas , C., Mocanu , A.: MatBase DFS Detecting and Classifying E -RD Cycles Algorithm .
Journal of Computer Science Applications and Information Technology 2 (4) , 1–14 (2017).
14. Thalheim , B.: Fundamentals of Entity -Relationship Modeling. Springer -Verlag, Berlin
(2000) .