International Journal of Scientific & Engineering Research, Volume 2, Issue 11, November-2011 1

ISSN 2229-5518

Algorithmic Resolution of an ER Schema into Relational DDL Statements using Artificial Intelligence

Manuj Darbari, Hasan Ahmed, Sunita Bansal

AbstractThe concept of this paper helps resolve an ER schema into an appropriate relational Data Description Language (herein standard SQL statements) while considering all the inherent complexity of such a schema. The algorithm resolves all the relationships between the concerned entities (even weak ones), their associated keys primary and foreign, attributes simple, composite and multivalued and relationships types from binary to n- ary. The algorithm (as implemented in ANSI C) is smart enough to consider the case of cascading weak entities.

Index TermsEntity Relationship Schemas, SQL statements, relational tables.

1 INTRODUCTION

—————————— ——————————

Often a need is felt by applications programmers, comput- er geeks and the like to translate a given ER schema into

SQL statements. Such a translation requires a concerted effort to logically optimize that schema considering all the possibili- ties of entity relationships, primary and foreign keys, all the variants of attributes, weak and owner entities, etc. This leads to a very cautious effort in devising actual SQL tables.
We have just automated this intelligent effort. The user, just, has to input his ER schema in a defined syntax and with a click of mouse, she could get an optimized set of SQL statements which can be readily applied to a stan- dard SQL engine; thereby, creating suitable database tables [1,4].

2. THEORETICAL BASES

Normally, we have ER schema which encompasses enti- ties (regular and weak) delved in relationships amongst themselves. These relationships can be varied including not only binary 1:1 ones but also binary 1:N, binary M:N and N-ary relationships.
We, then, bring in the case of weak entities which have regular owner entities. In these cases, due consideration is to be given to a case (or similar cases) wherein the owner entity of a weak

————————————————

Manuj Darbari is working as Associate Professor with the Department of InfomationTechnology in Babu Banarsi Das National Institute of Technolo- gy and Management,Lucknow, India E-mail: manujuma@gmail.com

Hasan Ahmed, Consultant at SaharaNext, Lucknow, India, hasansin- box@gmail.com

Sunita Bansal, Research Scholar, Department of Computer Science, JJTU

University, Rajasthan, Sunita_bansal301@rediffmail.com
entity is, itself, a weak entity whose owner is a regular entity. Now, we ought to reasonably handle primary and foreign keys. Besides, not to be forgotten is optimized appropriation of attributes of all the entities concerned. Attributes can also come in different variations which demand different interpre- tations. For example, simple attributes of an entity is to be handled differently from the entity’s composite attributes which, in turn, needs to be handled differently from multi- valued attributes of that particular entity.
Our paper does resolve such complex ER schemas into optimized relational SQL statements which can be applied to database engines. Hence, a great reduction in manual effort would be the result.
In our C code, we have adopted the standard mechanisms of ER schema to relational mapping [1,2,3]. Here, we go on to mention how effect such a scheme considering spe- cific cases, one by one.

2.1. REGULAR ENTITIES

For every regular entity E, there is a relation R having all the attributes of E. We include simple components of a composite attribute (in that case) and choose one of the keys of E as a primary key of R. If that chosen key is com- posite, the set of simple attributes that form it will form the primary key of R.

2.2. WEAK ENTITIES

For every weak entity W with owner entity E, there is a re- lation R having all the simple attributes (or simple compo- nents of composite attributes) of W. We, also, include as

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 2, Issue 11, November-2011 2

ISSN 2229-5518

foreign key attribute(s), the primary key attribute(s) of the relation that corresponds to the owner entity type. This helps the identifying relationship type of W. Herein, the primary key of R would be the combination of the primary key(s) of owner entity(-ies) and the partial key of W, if any. Here, our code also considers the case of that weak entity whose owner entity is also a weak entity and, in turn, whose owner entity is a regular entity. Our algo- rithm can handle such a cascading to a good number of weak entity levels. In such cases, the naming and genera- tion of primary key(s) of resultant relations of those weak entities is intelligently handled by our code.

2.3. BINARY RELATIONSHIP

For mapping binary 1:1 relationship, the most optimizing me- thod is to go through foreign key approach, which is em- ployed by us. We, first, identify the two relations S and T par- ticipating in relationship R. We choose that entity in the role of S which totally participates in R. And in S, we include as a foreign key, the primary key of T. Also, we include all the simple attributes (or simple components of composite attributes) of 1:1 relationship R as attributes of S.
For each regular binary 1:N relationship R, we identify the relation S that is the participating entity on the N side of R. Here, we include as foreign key in S, the primary key of relation T (which is the relation representing the other ent- ity of R). Also, we include all the simple attributes (or simple components of composite attributes) of 1:N rela- tionship R as attributes of S.
For the case of binary M:N relationship R, we create a new relationship S to represent R while including as foreign key attributes in S all the primary keys of the relations that represent the participating entity types as their com- bination will form the primary key of S. Apart from this, we include any/all simple attributes of the M:N relation- ship (or simple components of composite attributes) as attributes of S.

2.3. MULTI VALUED ATTRIBUTE

For every multi-valued attribute A, we create a new rela- tion R which includes an attribute corresponding to A, with the primary key attribute P as a foreign key in R, of the relation that represents the entity type that has A as an attribute. In such a case, the primary key of R would be the combination of A and P. Of course, if the multi-valued attribute tends to be composite, we include all its simple components.

2.3. N-ARRAY RELATIONSHIP

For every n-ary relationship R (n>2), we create a new rela- tion S to represent R while including the foreign key attributes in S, the primary keys of the relations that represent the participating entity types. Here again, we include simple attributes of the n-ary relationship type (or simple components of composite attributes) as attributes of S. The primary key of S is usually a combination of all the foreign keys that reference the relations representing the participating entity types. But, we do maintain an ex- ception here. If the cardinality constraints on any of the entity types K participating in R is 1, then the primary key of S should not include the foreign key attribute that ref- erences the relation K’ corresponding to K.

3. ALGORITHMIC IMPLEMENTATION

The algorithm is implemented in ANSI C. The algorithm deals with the ER schema complexities in the order: regular entities, weak entities, binary relationships, multi-valued attributes and n-ary relationships, respectively. The actual code can be requested from the authors’ email contacts.
The algorithm is smart enough to rename and/or automati- cally generate new table names, attribute names, keys, etc. Also, the algorithm picks up other important characteristics of attributes such as it being null (or not null) and being unique (or not unique).
The algorithm extensively uses linked lists as data struc- tures. On the other hand, it does use file handling in C. The use of counters and accumulators is, also, quite common.
As for demonstrability purpose in the example quoted, only
‘int’ and ‘varchar’ types of attributes (of varying siz- es/spaces) have been taken. However, the code is scalable to other data types as well.
The constraints are as follows. The input file has to be strongly typed as the parser moves through character by character. Composite attributes have to be given as simple components of the parent attribute. As per current imple- mentation, the attribute has seven fields: attribute name, da- ta type, whether null, whether unique, whether a part of primary key, whether default, whether multi-valued. The only assumption in the input file is, at least, one output file.

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 2, Issue 11, November-2011 3

ISSN 2229-5518


The sample file is depicted in figure 3 as:

Figure 1. Some macros and linked list definitions.

The snapshot of parts of algorithm code is given in figures 1 and 2. The sample file is depicted as figure 3 while figure 4 depicts the resultant output file.
The snapshot of parts of algorithm code is given in figures 1 and 2. The sample file is depicted as figure 3 while figure 4 depicts the resultant output file.

Figure 2 : Start of the main Function

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 2, Issue 11, November-2011 4

ISSN 2229-5518



Further extension of the output gives the result as:
Further extension of the output gives the result as:

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 2, Issue 11, November-2011 5

ISSN 2229-5518


Figure 4: Generated SQL File

4. CONCLUSION AND FUTURE SCOPE

The concept of this algorithm can be applied for further resolution of complexities like specialization and class dia- grams (as in OOP and data modeling). Also, with the help of GUI, this could be time-saver tool from advanced and naïve users to scholars and practitioners.

References

[1] Chen, P. 1976. The Entity-Relationship Model--Toward a Unified

View of Data. In: ACM Transactions on Database Systems 1/1/1976

ACM-Press ISSN 0362-5915, S.

[2] Elmasri, Navathe, Somayajulu, Gupta. 2006. Fundamentals of Data- base Systems. Pearson Education. ISBN 81-7758-476-6.

[3] CODD, E.F. Normalized data base structure: A brief tutorial. Proc.

ACM-SIGFIDET 1971, Workshop, San Diego, Calif., Nov. 1971, pp. 1-

18.

[4] Codd, E.F. (1990). The Relational Model for Database Management

(Version 2 ed.). Addison Wesley Publishing Company. ISBN 0-201-

14192-2.

IJSER © 2011

http://www.ijser.org