1. Introduction <\/p>\n\n\n\n
All subuniverses of discourse are governed by business rules (e.g., \u201dnobody may die before birth\u201d, \u201dnobody may get married before birth\u201d, \u201dpeople\u2019s height is between 30 and 225 cm\u201d, etc.). A database (db) instance is useful only if it is plausible, i.e., only if its data does not violate any business rule governing the corresponding subuniverse of discourse. In dbs and software <\/p>\n\n\n\n
engineering, business rules are formalized as constraints, i.e., closed formulas of the first-order predicate calculus with equality. <\/p>\n\n\n\n
Our (Elementary) Mathematical Data Model ((E)MDM) [1] was introduced as an intermediate conceptual design level between the Entity-Relational Data Model (E-RDM) [2, 3, 4] and the Relational Data Model (RDM) [4, 5, 6]. The E-RDM includes the very powerful E-R Diagrams (E-RDs) that may be easily understood even by customers without computer science background but, despite its many extensions, it has a very limited set of constraints. The RDM has only six constraint types (domain\/range, not null, default values, unique keys, foreign keys, and tuple\/check). The (E)MDM has 76 constraint types, thus allowing for far more accurate conceptual data modeling and db design; they include, explicitly or implicitly, all 6 relational type ones; the non-relational type ones should be enforced by the software applications (sa) that manage the corresponding dbs. <\/p>\n\n\n\n
In [4], we defined E-R data models as triples <ERDS<\/em>, ARS<\/em>, ICSD<\/em>>, where ERDS <\/em>is a set of E-RDs, ARS <\/em>is an Associated Restriction Set, and ICSD <\/em>is an Informal Corresponding Sub universe Description. The associated restrictions, which correspond to the business rules governing the modeled sub-universes, are of the following five types: inclusions between object sets (e.g., EMPLOYEES <\/em>\u2286 PERSONS<\/em>), ranges of the attributes (e.g., Month <\/em>between 1 and 12), compulsory (not null) attribute values (e.g., BirthDate <\/em>compulsory), minimal uniqueness of attributes (e.g., SSN <\/em>unique) and attribute concatenations (e.g., Room <\/em>\u2022 Weekday <\/em>\u2022 StartHour <\/em>unique), and other restriction types (e.g., \u201cno teacher may be simultaneously present in two classrooms\u201d). <\/p>\n\n\n\n An E-RD may be single, i.e., consisting only of an entity or relationship type set and its attributes, or structural, i.e., containing any number of sets, the structural functions (i.e., binary functional relationships) relating them, and no attributes. The single ones for relationship-type sets also contain all the sets over which the relationship is defined. <\/p>\n\n\n\n 2 <\/p>\n\n\n\n MatBase <\/em>[7, 8] is our intelligent data and knowledge base management system prototype, based on both (E)MDM, E-RDM, and RDM. It includes 3 graphic user interfaces (GUI), one for each data model, and automatically translates between them, generates corresponding sa GUIs and code for enforcing a vast majority of the (E)MDM constraint types. <\/p>\n\n\n\n In our previously published paper [9], we presented and discussed the forward MatBase <\/em>algorithm for translating E-R data models into (E)MDM schemes. The algorithm presented in this paper is its dual, a reverse engineering type one. Its necessity arises from the following couple of reasons: <\/p>\n\n\n\n \u2713 Reflecting updates of a(n) (E)MDM schema performed after obtaining it from an E-R data model. <\/p>\n\n\n\n \u2713 Extracting only an E-R data model subset. <\/p>\n\n\n\n The algorithm has two optional input parameters: an object set name of the current db, and a natural radius. If the first one is not null and the radius is either null or 0, then the algorithm outputs the E-R data model of the corresponding object set (whose E-RD is a single one); for any other natural value n <\/em>of the radius, it outputs the E-R data sub-model centered in the desired object set and having radius at most n <\/em>(i.e., whose E-RD is a structural one having length at most n <\/em>for at least one path starting from the desired object set); if the first parameter is null, then it outputs the whole db E-R data model (and the radius is ignored if it is not null). <\/p>\n\n\n\n After the literature review, the third Section introduces and characterizes the pseudocode algorithm used by MatBase <\/em>to translate (E)MDM schemes into E-R data models, then presents and discusses the results of applying this algorithm to an (E)MDM scheme from [10, 11]. The paper ends with conclusions, recommendations, and a reference list. <\/p>\n\n\n\n 2. Related work <\/p>\n\n\n\n Only MatBase <\/em>manages (E)MDM schemes.<\/p>\n\n\n\n Quest has over 30 years of its erwin Data Modeler<\/em>[12] success. For example, it may reverse engineer both relational (e.g., MS SQL Server, Oracle Database, IBM Db2, Sybase SQL Anywhere, SQLite) and noSQL (e.g., mongoDB, cassandra, MariaDB, neo4j) schemas into corresponding E-RDs. <\/p>\n\n\n\n Related algorithms are, however, used by all major commercial RDBMSes for translating relational schemas into E-R data models-like ones. <\/p>\n\n\n\n For example, the MS SQL Server Management Studio [13] provides a Database Diagram <\/em>menu, part of the Visual Database Tools<\/em>. You can create, update, and delete relational diagrams corresponding to the tables of a db. These diagrams are not \u201cstandard\u201d E-RDs but are equivalent to them: nodes are rectangles corresponding to underlying db tables that can be thought of as single E-RDs, as their attributes are listed inside them; edges are the relations between tables, as established by the foreign keys, so that they are equivalent to structural functions and E <\/p>\n\n\n\n RDs. As the RDM is a syntactical one, no relationship-type nodes are present, all of them being of entity-type. This is consistent with our Theorem stating that the only fundamental mathematical relations for conceptual data modeling are the functions [14]. <\/p>\n\n\n\n Similarly, the Oracle SQL Developer provides a Data Modeler <\/em>tool [15]. The IBM Db2 Data Management Console [16], which is the equivalent of both MS SQL Server Management Studio and Oracle SQL Developer does not provide graphical tools. They are available from third parties, such as Dataedo [17]. <\/p>\n\n\n\n Other related approaches to MatBase <\/em>are based on business rules management (BRM) [18, 19] and their corresponding implemented systems (BRMS) and decision managers (e.g., [20 \u2013 22]). From this perspective, (E)MDM is also a formal BRM, and MatBase <\/em>is an automatically code generating BRMS.<\/p>\n\n\n\n 3. Research Methodology <\/p>\n\n\n\n Any (E<\/em>)MDM schema <\/em>[1] is a quadruple DKS = <S, M, C; P>, where S is a finite non empty poset of sets <\/em>ordered by inclusion, M is a finite non-empty set of mappings <\/em>defined on and taking values from the sets of S, C is a finite non-empty set of constraints <\/em>(i.e. closed Horn clauses of the first-order predicate logic with equality) over sets in S and\/or mappings in M , and P is a finite set of Datalog<\/em>\u00ac programs<\/em>, also over sets in S and mappings in M. Whenever P is empty, DKS is a db scheme<\/em>, otherwise it is a knowledge base one<\/em>. In the context of this paper, we are only interested in db schemes. <\/p>\n\n\n\n (S, \u2286) is a poset of sets<\/em>, with S = \u03a9 \u2295 V \u2295 *S \u2295 SysS, where \u03a9 = E \u2295 R (the non-empty collection of object sets<\/em>), where E is a non-empty collection of atomic entity-type sets <\/em>(e.g., PEOPLE<\/em>, COUNTRIES<\/em>, PRODUCTS<\/em>), R is a collection of relationship-type sets <\/em>(e.g., NEIGHBOUR_ COUNTRIES <\/em>\u2282 COUNTRIES <\/em>\u00d7 COUNTRIES<\/em>, STOCKS <\/em>\u2282 <\/p>\n\n\n\n PRODUCTS<\/em>\u00d7WAREHOUSES<\/em>); V is a non-empty collection of value sets <\/em>(e.g., SEXES <\/em>= {\u201cF\u201d,\u201dM\u201d}, [0,16] \u2282 NAT(2), ASCII(32) \u2282 ASCII(n<\/em>), [1\/1\/100, Today<\/em>()] \u2282 DATETIME, with NAT(n<\/em>) being the subset of naturals of at most n <\/em>digits, ASCII(n<\/em>) the subset of the freely generated monoid over the ASCII alphabet only including strings of maximum length n<\/em>, etc.); *S is a collection of computed sets <\/em>(e.g., MALES<\/em>, FEMALES<\/em>, UNPAID_BILLS<\/em>), and SysS is a collection of system sets <\/em>(e.g., \u2205 (the empty set), NULLS (the distinguished countable set of null values<\/em>), BOOLE = {true<\/em>, false<\/em>}, NAT(n<\/em>), ASCII(n<\/em>), DATETIME (the set of date and time values)). <\/p>\n\n\n\n In RDM schemata, generally, the object sets are tables, the computed sets are views (queries), the system sets are corresponding db management system (RDBMS) data types, and the value sets are their needed subsets. <\/p>\n\n\n\n The set of mappings <\/em>(functions<\/em>) is M = A \u2295 F \u2295 *M \u2295 SysM, where A \u2282 Hom(S \u2013 SysS \u2295V, V) is the non-empty set of attributes<\/em>(e.g., x <\/em>: PEOPLE <\/em>\u2194 NAT(10), FirstName <\/em>: PEOPLE<\/em><\/p>\n\n\n\n 5 <\/p>\n\n\n\n \u2192 ASCII(64), BirthDate <\/em>: PEOPLE \u2192 [1\/1\/-6000, Today<\/em>()], Sex <\/em>: PEOPLE <\/em>\u2192 {\u201cF\u201d, \u201cM\u201d), Amount <\/em>: UNPAID_BILLS <\/em>\u2192 (0, 100000], where \u2194 denotes injections (one-to-one functions) and x <\/em>is our notation for object identifiers<\/em>, i.e., functions to be implemented as autonumber surrogate primary keys); F \u2282 Hom(S \u2013 SysS \u2295V, S \u2013 SysS \u2295 V) is the non-empty set of structural functions <\/em>(e.g., BirthPlace <\/em>: PEOPLE <\/em>\u2192 CITIES<\/em>, Capital <\/em>: COUNTRIES <\/em>\u2194 CITIES<\/em>); *M is the set of computed mappings <\/em>(e.g., BirthCountry <\/em>= Country <\/em>\u00b0 BirthPlace <\/em>: PEOPLE <\/em>\u2192 COUNTRIES<\/em>, Mother <\/em>\u2022 Father <\/em>: PEOPLE <\/em>\u2192 (PEOPLE <\/em>\u222aNULLS)2<\/sup>), and SysM is the set of system mappings <\/em>(e.g., 1<\/strong>S <\/em>(the unity function of a set S<\/em>), card<\/em>(S<\/em>) (the cardinal of a set S<\/em>), Im<\/em>(f <\/em>) (the image of a function f<\/em>, i.e., the set of the values it takes), dom<\/em>(f<\/em>) and codom<\/em>(f<\/em>) (the domain and codomain of f<\/em>, respectively), isNull<\/em>(x<\/em>,y<\/em>) (which returns x <\/em>if it is not null, and y <\/em>otherwise)). <\/p>\n\n\n\n In RDM schemata, the attributes, structural functions, and computed mappings are implemented as table or\/and view (query) columns, with structural functions being foreign keys. <\/p>\n\n\n\n The set of constraints <\/em>is C = SC \u2295 MC \u2295 OC \u2295 SysC, where the set constraints <\/em>SC contains both general ones (e.g., inclusion, equality, disjointness) and dyadic relation ones (e.g., reflexivity, symmetry, transitivity); the mapping constraints <\/em>MC contains the general ones (e.g., totality, one-to-oneness, ontoness), dyadic-type self-map ones, general mapping products ones (e.g., minimal one-to-oneness, variable geometry keys and their subkeys, existence), dyadic-type homogeneous binary product ones, function diagram ones (e.g., commutativity, anti-commutativity, representative systems); the set OC of object constraints <\/em>contains any other closed Horn clauses not among the above, and the system constraints <\/em>SysC includes all needed mathematical constraints (e.g., card<\/em>(\u2205) = 0, \u2205 \u2286 S<\/em>, \u2205 \u2229 S <\/em>= \u2205, S <\/em>\u2229 S <\/em>= S <\/em>\u222a S <\/em>= S <\/em>, \u2200S<\/em>\u2208S).<\/p>\n\n\n\n Constraints are not absolute, but relative to the corresponding subuniverses: for example, constraint C<\/em>1 from subsection 3.2 goes not generally hold (e.g., there are several cities called \u201cParis\u201d in the U.S.). <\/p>\n\n\n\n Structural E-RDs are directed graphs having as nodes any type of sets except for the value type ones, and structural functions as edges. Our version of E-RDs [4] uses arrows (i.e., the standard mathematical convention for mappings) instead of diamonds for any binary functional relationship. <\/p>\n\n\n\n In (E)MDM, as a shorthand, the domain of attributes may be omitted if they are listed immediately after their domain set name, and one-to-one mappings use double arrows (e.g., see attribute Country <\/em>\u2194 ASCII(255) from subsection 3.2). <\/p>\n\n\n\n The complexity of an algorithm <\/em>is denoted by O<\/em>(e<\/em>), where e <\/em>is an algebraic expression and means that the algorithm never loops infinitely and ends in a number of steps that is a multiple of e<\/em>. Generally, an algorithm is sound <\/em>if it returns only true answers, complete <\/em>if it accepts any valid inputs, and optimal <\/em>(efficient<\/em>) if it performs in the minimal number of steps possible for any input. Moreover, we say that an algorithm is semi-optimal <\/em>when, even if it visits more than once an object, it processes any object only once. <\/p>\n\n\n\n In our context, soundness <\/em>means that all object and computed sets are translated into same type of sets (i.e., rectangles or diamonds, respectively), attributes into ellipses, structural functions into arrows (all of the above being dotted for computed objects), constraints into restrictions, and comments into informal description texts, while completeness <\/em>means that all valid (E)MDM schemes are correspondingly translated. <\/p>\n\n\n\n In this paper, \u201cmapping\u201d and \u201cfunction\u201d are used interchangeably. Mapping totality is translated into RDM by a corresponding not null constraint.<\/p>\n\n\n\n 4. The REA<\/em>2 Algorithm <\/p>\n\n\n\n The reverse engineering pseudocode algorithm REA<\/em>2 used by MatBase <\/em>for translating (E)MDM schemes into E-R data models is shown in Figures 1 to 10. The dependencies between its 10 methods are presented in Figure 11. <\/p>\n\n\n\n Obviously, value-type sets are not figured in E-RDs: only object or computed ones (which are drawn in dotted lines) are. <\/p>\n\n\n\n 5. Results: two reverse engineering examples <\/p>\n\n\n\n Here is an example of an (E)MDM schema \u2013 a subset of the GENEALOGIES <\/em>sub-universe studied in [10, 11]: <\/p>\n\n\n\n COUNTRIES <\/em><\/strong><\/p>\n\n\n\n x <\/em>\u2194 NAT(3) total <\/p>\n\n\n\n Country <\/em>\u2194 ASCII(255) total (There may not be 2 countries having same name.)<\/p>\n\n\n\n CITIES <\/em><\/strong><\/p>\n\n\n\n x <\/em>\u2194 NAT(6) total <\/p>\n\n\n\n City <\/em>\u2192 ASCII(255) total <\/p>\n\n\n\n Country <\/em>: CITIES <\/em>\u2192 COUNTRIES <\/em>total <\/p>\n\n\n\n Capital <\/em>: COUNTRIES <\/em>\u2194 CITIES <\/em>(No city may simultaneously be the capital of 2 countries.)<\/p>\n\n\n\n C<\/em>1: City <\/em>\u2022 Country <\/em>key (There may not be 2 cities with a same name in a same country.) C<\/em>2: Country <\/em>\u00b0 Capital <\/em>reflexive (The capital city of any country must belong to that country.) <\/p>\n\n\n\n DYNASTIES <\/em><\/strong><\/p>\n\n\n\n x <\/em>\u2194 NAT(8) total <\/p>\n\n\n\n Dynasty <\/em>\u2194 ASCII(255) total (There may not be 2 dynasties having same name.) Country <\/em>: DYNASTIES <\/em>\u2192 COUNTRIES <\/em>total<\/p>\n\n\n\n TITLES <\/em><\/strong><\/p>\n\n\n\n x <\/em>\u2194 NAT(2) total <\/p>\n\n\n\n Title <\/em>\u2194 ASCII(32) total (There may not be 2 titles having same name.) RULERS <\/em><\/strong><\/p>\n\n\n\n x <\/em>\u2194 NAT(16) total <\/p>\n\n\n\n Name <\/em>\u2192 ASCII(255) total <\/p>\n\n\n\n Sex <\/em>\u2192 {\u2018M\u2019, \u2018F\u2019, \u2018N\u2019} total (\u2018N\u2019 is for non-persons) <\/p>\n\n\n\n BirthYear <\/em>\u2192 [-6500, CurrentYear<\/em>()] <\/p>\n\n\n\n PassedAwayYear <\/em>\u2192 [-6500, CurrentYear<\/em>()] <\/p>\n\n\n\n URL <\/em>\u2192 ASCII(255) <\/p>\n\n\n\n Age <\/em>= isNull<\/em>(PassedAwayYear<\/em>, CurrentYear<\/em>()) \u2013 BirthYear <\/em><\/p>\n\n\n\n Mother <\/em>: RULERS<\/em>\u2192 RULERS <\/em>acyclic (Nobody may be his\/her maternal ancestor or descendant.) <\/p>\n\n\n\n Father <\/em>: RULERS<\/em>\u2192 RULERS <\/em>acyclic (Nobody may be his\/her paternal ancestor or descendant.) <\/p>\n\n\n\n KilledBy <\/em>: RULERS<\/em>\u2192