Unit - 3

Relational Database Design

3.1 Relational Model: Basic concepts, Attributes and Domains

The primary data model is the Relational Data Model, which is commonly used for data storage and processing around the world. This model is simple and has all the features and functionality needed to process data with efficiency in storage.

The relational model can be interpreted as a table with rows and columns. Each row is called a tuple. There's a name or attribute for each table in the column.

Basic concept:

Table: Relationships are saved in the format of tables in a relational data model. The relationship between entities is stored in this format. A table includes rows and columns, where rows represent information, and attributes are represented by columns.

Tuple: A tuple is called a single row of a table, which contains a single record for that relationship.

Attributes and Domains

Domain: It includes a set of atomic values that can be adopted by an attribute.

Attribute: In a specific table, it includes the name of a column. Every Ai attribute must have a domain, a domain (Ai).

Relational instance: The relational example is represented in the relational database structure by a finite set of tuples. There are no duplicate tuples for relation instances.

Relational schema: The name of the relationship and the name of all columns or attributes are used in a relational schema.

Relational key: Each row has one or more attributes in the relational key. It can uniquely identify the row in the association.

Example:

STUDENT Relation

●      In the given table, NAME, ROLL_NO, PHONE_NO, ADDRESS, and AGE are the attributes.

●      The instance of schema STUDENT has 5 tuples.

●      t3 = <Laxman, 33289, 8583287182, Gurugram, 20>

3.2 CODD's Rules

After his thorough study into the Relational Model of Database Systems, Dr. Edgar F. Codd came up with twelve rules of his own that, according to him, must be followed by a database in order to be called a true relational database.

These principles can be extended to any database system that only uses its relational features to handle stored data. This is a simple rule that serves as the basis for all the other rules.

1. Information Rule: The data contained in a database must be the value of a table cell, whether it is user data or metadata. It is important to store everything in a database in a table format.
2. Guaranteed Access Rule: Each data element must be accessible by means of the name of the table, its primary key, and the name of the attribute whose meaning is to be determined.
3. Systematic Treatment of NULL values: A systematic and uniform treatment must be given to the NULL values in a database. This is a very relevant rule since it is possible to interpret a NULL as one of the following: information is missing, information is not known or information is not applicable.
4. Active Online Catalog: The definition of the structure of the whole database must be stored in an online catalogue, known as a data dictionary, accessible by registered users. The same query language can be used by users to access the catalogue that they use to access the database itself.
5. Comprehensive Data Sublanguage Rule: A database should be available in a language that is supported for the process of description, manipulation and transaction management.
6. View Updating Rule: Various views that are generated for different purposes should be automatically modified by the framework.
7. High level insert, update and delete rule: High-level addition, upgrading, and removal must be assisted by a database. This must not be limited to a single row, which means that union, intersection and minus operations must also be assisted in order to generate data record sets.
8. Physical data independence: At each relationship level, the Relational Model should support insert, remove, update, etc. operations. Set operations such as Union, Intersection and minus should also be endorsed.
9. Logical data independence: Any alteration of a table's logical or conceptual schema does not involve modification at the level of the application. Merging two tables into one, for example, does not impact access to the application, which is difficult to do.
10. Integrity Independence: Changed integrity restrictions at the database level do not implement changes at the application level.
11. Distribution Independence: For end-users, the distribution of data over different locations should not be noticeable.
12. Non-Subversion Rule: Low level access to data should not be able to circumvent honesty rules to alter data.

3.3 Relational Integrity: Domain, Referential Integrities, Enterprise Constraints

Domain

●      As a description of a valid set of values for an attribute, domain constraints can be specified.

●      The domain data type consists of a string, character, integer, time, date, currency, etc. In the corresponding domain, the value of the attribute must be available.

Fig 1: Example of domain constraints

Referential integrity

●      Between two relations or tables, the referential integrity constraints are defined and used to preserve the consistency between the tuples in two relationships.

●      If an attribute of the foreign key of the relationship R1 has the same domain(s) as the primary key of the relationship R2, then the foreign key of R1 is said to refer to or refer to the primary key of the relationship R2.

●      Foreign key values in the R1 relationship tuple can either take the primary key values for a certain R2 relationship tuple, or they can take NULL values, but cannot be zero.

Example

Fig 2: Example of referential integrity

Enterprise constraints

Enterprise constraints are additional rules that users or database managers define and may be based on several tables, often referred to as semantic constraints.

Some explanations are here.

●      There can be a maximum of 30 students for a class.

●      A maximum of four classes per semester can be taught by an instructor.

●      An employee is unable to engage in more than five programmes.

●      An employee's compensation cannot exceed the employee's manager's salary.

3.4 Database Design: Features of Good Relational Designs

In a database, we have numerous relations, as we all know. Each relationship must now be identified separately. If this is not the case, there will be a lot of confusion. We'll go over various features that, if followed, will automatically distinguish a relation in a database.

1. Each database connection must have a different or unique name that distinguishes it from the other database relations.

2. There can't be two attributes with the same name in a relation. Each attribute must be given a unique name.

3. A relation must not contain duplicate tuples.

4. For each attribute, each tuple must have precisely one data value. For example, you can see in the first table that we have enrolled two pupils, Jhoson and Charles, for Roll No. 265; this would not work. For each Roll No, we must have only one student.

5. A relation's tuples do not have to be in any particular order because the relation is not order-sensitive.

6. Similarly, the properties of a relation do not have to be in any particular order; the developer can specify how the attributes are ordered.

Key takeaway:

1. Data must be represented as a set of relationships. Each relationship should be clearly depicted in the table.
2. Data about instances of an entity should be contained in rows. Columns must contain information about the entity's attributes.
3. The table's cells should all have the same value. Each column should have its own name.
4. There can't be any two rows that are the same. An attribute's values should all come from the same domain.

3.5 Normalization

Normalization is often executed as a series of different forms. Each normal form has its own properties. As normalization proceeds, the relations become progressively more restricted in format, and also less vulnerable to update anomalies. For the relational data model, it is important to bring the relation only in first normal form (1NF) that is critical in creating relations. All the remaining forms are optional.

A relation R is said to be normalized if it does not create any anomaly for three basic operations: insert, delete and update

Fig 3: Types of normal forms

1NF

If a relation has an atomic value, it is in 1NF.

2NF

If a relation is in 1NF and all non-key attributes are fully functioning and dependent on the primary key, it is in 2NF.

3NF

If a relation is in 2NF and there is no transition dependency, it is in 3NF.

4NF

If a relation is in Boyce Codd normal form and has no multivalued dependencies, it is in 4NF.

5NF

If a relation is in 4NF and does not contain any join dependencies, it is in 5NF, and joining should be lossless.

Objectives of Normalization

●      It is used to delete redundant information and anomalies in the database from the relational table.

●      Normalization improves by analyzing new data types used in the table to reduce consistency and complexity.

●      Dividing the broad database table into smaller tables and connecting them using a relationship is helpful.

●      This avoids duplicating data into a table or not repeating classes.

●      It decreases the probability of anomalies in a database occurring.

Key takeaway:

1. Normalization is a method of arranging the database data to prevent data duplication, anomaly of addition, anomaly of update & anomaly of deletion.
2. Standard types are used in database tables to remove or decrease redundancies.

3.6 Atomic Domains and First Normal Form

In a relational database, atomic means that it can't be divided any further. Factorization Domain is another name for Atomic Domain. An integral domain is an atomic domain. Atomic domains are distinct from factorization domains with unique factors.

The relational database's Normal Form (NF) gives criteria for identifying the table's degree. 1NF, 2NF, 3NF, and so on are examples of normal forms.

First Normal Form (1NF):

A relation r is in 1NF if and only if every tuple contains only atomic attributes means exactly one value for each attribute. As per the rule of first normal form, an attribute of a table cannot hold multiple values. It should hold only atomic values.

Example: suppose Company has created an employee table to store name, address and mobile number of employees.

In the above table, two employees John, Mary has two mobile numbers. So, the attribute emp_mobile is a Multivalued attribute.

So, this table is not in 1NF as the rule says, “Each attribute of a table must have atomic values”. But in the above table the attribute, emp_mobile, is not an atomic attribute as it contains multiple values. So, it violates the rule of 1 NF.

Following solution brings an employee table in 1NF.

Key takeaway:

1. A relation r is in 1NF if and only if every tuple contains only atomic attributes means exactly one value for each attribute.

3.7 Decomposition using Functional Dependencies

Functional Dependency (FD) is a constraint in a database management system that specifies the relationship of one attribute to another attribute (DBMS). Functional Dependency helps to maintain the database's data quality. Finding the difference between good and poor database design plays a critical role.

The arrow "→" signifies a functional dependence. X→ Y is defined by the functional dependence of X on Y.

Rules of functional dependencies

The three most important rules for Database Functional Dependence are below:

●      Reflexive law: X holds a value of Y if X is a set of attributes and Y is a subset of X.

●      Augmentation rule: If x -> y holds, and c is set as an attribute, then ac -> bc holds as well. That is to add attributes that do not modify the fundamental dependencies.

●      Transitivity law: If x -> y holds and y -> z holds, this rule is very similar to the transitive rule in algebra, then x -> z also holds. X -> y is referred to as functionally evaluating y.

Types of functional dependency

Fig 4: Types of functional dependency

1. Trivial functional dependency

●      A → B has trivial functional dependency if B is a subset of A.

●      The following dependencies are also trivial like: A → A, B → B

Example

Consider a table with two columns Employee_Id and Employee_Name. 

{Employee_id, Employee_Name} →    Employee_Id is a trivial functional dependency as  

Employee_Id is a subset of {Employee_Id, Employee_Name}. 

Also, Employee_Id → Employee_Id and Employee_Name   →    Employee_Name are trivial dependencies too. 

2. Non - trivial functional dependencies

●      A → B has a non-trivial functional dependency if B is not a subset of A.

●      When A intersection B is NULL, then A → B is called as complete non-trivial.

Example:

ID   →    Name, 

Name   →    DOB 

Key takeaway:

1. The arrow "→" signifies a functional dependence.
2. Functional Dependency helps to maintain the database's data quality.

3.8 Algorithms for Decomposition

By explicitly generating a schema for each dependency in the canonical cover, the decomposition procedure for 3NF ensures that dependencies are preserved. It assures that at least one schema has a candidate key for the one being decomposed, ensuring that the decomposition created is a lossless decomposition.

Decomposition Algorithm

Let Fc be a canonical cover for F;

i=0;

For each functional dependency α->β in Fc

i = i+1;

R = αβ;

If none of the schemas Rj, j=1,2,…I holds a candidate key for R

Then

i = i+1;

Ri= any candidate key for R;

/* Optionally, remove the repetitive relations*/

Repeat

If any schema Rj is contained in another schema Rk

Then

/* Delete Rj */

Rj = Ri;

i = i-1;

Until no more Rjs can be deleted

Return (R1, R2, . . .  ,Ri)

The supplied relation is R, and the given collection of functional dependencies is F, for which Fc maintains the canonical cover. The decomposed portions of the given relation R are R1, R2,..., Ri. As a result, this technique preserves the dependency while also generating a lossless decomposition of R.

A 3NF synthesis algorithm is another name for a 3NF algorithm. It's called so because the regular form works with a dependency set and adds one schema at a time, rather than repeatedly dissecting the basic schema.

BCNF

It is important to check if the given relation is in Boyce-Codd Normal Form before applying the BCNF decomposition technique on it. If it is discovered that the supplied relation is not in BCNF after the test, we can decompose it further to produce BCNF relations.

The following situations necessitate determining whether the supplied relation schema R follows the BCNF rule:

Case 1: Evaluate and compute α+, i.e., the attribute closure of to see if a nontrivial dependency α -> β violates the BCNF rule. Check that + contains all of the attributes of the supplied relation R. It should, therefore, be the super key of relation R.

Case 2: It is not necessary to test all of the dependencies in F+ if the specified relation R is in BCNF. For the BCNF test, all that is required is detecting and checking the dependencies in the specified dependency list F. It's because if no dependent in F violates BCNF, then none of the F+ dependencies will as well.

Decomposition Algorithm

If the supplied relation R is deconstructed into numerous relations R1, R2,..., Rn since it was not found in the BCNF, this algorithm is employed. Thus,

We must validate that α+ (an attribute closure of under F) either includes all the attributes of the relation Ri or no attribute of Ri-α for each subset of attributes in the relation Ri.

Result={R};

Done=false;

Compute F+;

While (not done) do

If (there is a schema Ri in result that is not in BCNF)

Then begin

Let α->β be a nontrivial functional dependency that holds

On Ri such that α->Ri is not in F+, and α ꓵ β= ø;

Result=(result-Ri) U (Ri-β) U (α, β);

End

Else done=true;

This procedure is used to break down a given relation R into its decomposers. This approach does the breakdown of the relation R using dependencies that demonstrate the violation of BCNF. As a result, such an algorithm not only generates relation R decomposers in BCNF, but it is also a lossless decomposition. It signifies that no data is lost when the specified relation R is decomposed into R1, R2, and so on...

The time it takes for the BCNF decomposition procedure to complete is proportional to the size of the original relation schema R. As a result, one disadvantage of this technique is that it may excessively breakdown the given relation R, i.e., over-normalize it.

The decomposition methods for BCNF and 4NF are nearly identical, with one exception. The fourth normal form is concerned with multivalued dependencies, while BCNF is concerned with functional dependencies. The multivalued dependencies aid in reducing data repetition, which is difficult to comprehend in terms of functional relationships.

Key takeaway

1. By explicitly generating a schema for each dependency in the canonical cover, the decomposition procedure for 3NF ensures that dependencies are preserved.
2. It is important to check if the given relation is in Boyce-Codd Normal Form before applying the BCNF decomposition technique on it.
3. If it is discovered that the supplied relation is not in BCNF after the test, we can decompose it further to produce BCNF relations.

3.9 2NF, 3NF, BCNF

Second Normal Form (2NF)

A table is said to be in 2NF if both of the following conditions are satisfied:

●      Table is in 1 NF.

●      No non-prime attribute is dependent on the proper subset of any candidate key of table. It means a non-prime attribute should fully functionally depend on the whole candidate key of a table. It should not depend on part of the key.

An attribute that is not part of any candidate key is known as a non-prime attribute.

Example:

Suppose a school wants to store data of teachers and the subjects they teach. Since a teacher can teach more than one subject, the table can have multiple rows for the same teacher.

For above table:

Candidate Keys: {Teacher_Id, Subject}

Non-prime attribute: Teacher_Age

The table is in 1 NF because each attribute has atomic values. However, it is not in 2NF because non-prime attribute Teacher_Age is dependent on Teacher_Id alone which is a proper subset of candidate key. This violates the rule for 2NF as the rule says “no non-prime attribute is dependent on the proper subset of any candidate key of the table”.

To bring above table in 2NF we can break it in two tables (Teacher_Detalis and

Teacher_Subject) like this:

Teacher_Details table:

Teacher_Subject table:

Now these two tables are in 2NF.

Third Normal Form (3NF)

A table design is said to be in 3NF if both the following conditions hold:

●      Table must be in 2NF.

●      Transitive functional dependency from the relation must be removed.

So, it can be stated that, a table is in 3NF if it is in 2NF and for each functional dependency

P->Q at least one of the following conditions hold:

●      P is a super key of table

●      Q is a prime attribute of table

An attribute that is a part of one of the candidate keys is known as a prime attribute.

Transitive functional dependency:

A functional dependency is said to be transitive if it is indirectly formed by two functional dependencies.

For example:

P->R is a transitive dependency if the following three functional dependencies hold true:

1) P->Q and

2) Q->R

Example: Suppose a company wants to store information about employees. Then the table Employee_Details looks like this:

Super keys: {emp_id}, {emp_id, emp_name}, {emp_id, emp_name, Manager_id}

Candidate Key: {emp_id}

Non-prime attributes: All attributes except emp_id is non-prime as they are not subpart part of any candidate keys.

Here, Mgr_Dept, Mgr_Name depend on Manager_id. And, Manager_id is dependent on emp_id that makes non-prime attributes (Mgr_Dept, Mgr_Name) transitively dependent on super key (emp_id). This violates the rule of 3NF.

To bring this table in 3NF we have to break into two tables to remove transitive dependency.

Employee_Details table:

Manager_Details table:

Boyce Codd normal form (BCNF)

It is an advanced version of 3NF. BCNF is stricter than 3NF. A table complies with BCNF if it is in 3NF and for every functional dependency X->Y, X should be the super key of the table.

Example: Suppose there is a company wherein employees work in more than one

Department. They store the data like this:

Functional dependencies in the table above:

Emp_id ->emp_nationality

Emp_dept -> {dept_type, dept_no_of_emp}

Candidate key: {emp_id, emp_dept}

The table is not in BCNF as neither emp_id nor emp_dept alone are keys. To bring this table in BCNF we can break this table in three tables like:

Emp_nationality table:

Emp_dept table:

Emp_dept_mapping table:

Functional dependencies:

Emp_id ->; emp_nationality

Emp_dept -> {dept_type, dept_no_of_emp}

Candidate keys:

For first table: emp_id

For second table: emp_dept

For third table: {emp_id, emp_dept}

This is now in BCNF as in both functional dependencies the left side is a key.

Key takeaway:

1. A relation is in the 4NF if it is in BCNF and has no multivalued dependencies.

3.10 Case Study: Normalize relational database designed in Unit I

A database can be defined as a computer-based record-keeping system that allows users to store information in an organized manner. The data is kept in a way that is independent of the programs that utilize it. When adding new data to the database, as well as altering and retrieving current data, a common and regulated technique is employed. A database is useful for automating as much work as feasible in order to improve manual operations by reducing or eliminating paper shuffling.

As a result, a database is frequently thought of as the store of data required to carry out specific duties within a company or organization. Database users can be found in almost any organization you can think of. Consider individuals like bankers, lawyers, accountants, customer service agents, and data entry clerks.

There are many various sorts of databases, some of which are simple and others which are extremely complicated. There are other database models, however the Relational Database Model is the most widely used database model today. It has been around for a long time and will continue to be around for a long time due to its ability to manage massive volumes of data, as well as its performance, dependability, and integrity.

Aiming for Good database design

Any database utilized by any company must have a strong database design in order to be successful in the long run. If extreme caution is not exercised, the finished product's quality will deteriorate. As a result, it necessitates a cognitive process when transforming an organization's data storage requirements into a relational database. The normalization theory is a useful aid in the design process of a database, which is difficult work.

Database Normalization

The process of structuring data in a database is known as normalization. It deals with converting a conceptual schema (logical data structures) into a computer-readable representation. This includes generating tables and defining relationships between them according to rules aimed to secure data while also allowing the database to be more adaptable by removing redundancy and inconsistent dependency.

The concept of normal forms is central to normalization theory. All other normal forms (except 1NF) are optional when building relations, however at least three normal forms (3NF) are advised to minimize update anomalies. As a result, normalization aids in the achievement of the following benefits:

1. It eliminates data redundancy.

2.It aids in the removal of data anomalies.

3.It creates controlled redundancy in order to connect tables.

Automating the Normalization Process is Required

As time passes, practically all businesses will need to enhance their databases by adding new attributes and relationships. The performance of a database under such conditions is totally dependent on its design. If the database is normalized, the data can be rearranged and the database can grow without causing application programs to be rewritten, which is critical given the high and rising costs of protecting an organization's application programs and data from the disruptive impacts of database growth.

In many firms, normalization is done manually, necessitating the hiring of competent employees with experience in the field. It gets more difficult to manually handle the normalization process as the database increases.

As a result, a tool is proposed in this paper that tries to automate the most difficult aspect of the database design process: NORMALIZATION. It will assist in achieving the hallmarks of good database architecture while also removing the disadvantages of the manual normalization process: more time, which amounts to greater expenses, a larger risk of errors, a less structured design and development process, and inconsistent communication.

Proposed system

The goal of the Web Based Relational Database Design and Normalization Tool is to provide an interactive environment in which users can practice database normalization. Relational databases such as Oracle and MySQL work well in this setting. In order to access the system's functions, new users must register with the system, and existing users must login.

The user must next enter basic database information such as Table Name, Number of Attributes, Attribute Name, Data Type, and any enforced constraints, as well as the table's functional requirements. Once all of the user's input has been acknowledged, the relationships are normalized up to 3NF using a predetermined algorithm. The normalized tables are delivered to the user in a ready-to-use format in several formats.

Methodology employed for the proposed work

A methodology is a set of policies, methods, and procedures that are codified and used by a project to practice software engineering. The methodology used by the suggested system is the Iterative Model. The Iterative model's primary premise is that software should be produced in incremental steps, with each step adding a new functional capacity to the system until the entire system is realized.

Advantages of proposed system

1) It has a broader scope than others because it attempts to serve both prominent organizations and students.

2) Our solution attempts to solve the disadvantages of existing tools that use MS-Access 2007 by using Oracle and MySQL as the database, ensuring a more secure, performant, and disaster-recovery approach.

3)It can be used in a variety of scenarios because it is not limited to a specific problem. It deals with a real-time scenario for an issue that the user has defined.

4)It accommodates the needs of beginner users by taking a minimal input from them and providing them with the normalized tables themselves.

Conclusion

All of the current methods for automating normalization essentially provide a learning environment for students by allowing them to work on a predefined or basic dummy issue statement. Users are not given access to a normalized database, which may save them time.

The proposed approach aims to overcome the shortcomings of existing systems that only aim to develop a learning environment for students, as it will not only develop a learning environment in order to give students the ability to easily and efficiently test their knowledge of the different normal forms in practice and can be ev Users will be able to access the normalized database through it.

In comparison to other programs that employ MS-Access 2007, our tool uses Oracle and MySQL as a database, ensuring a more robust approach to security, performance, and disaster recovery.

Future scope

The tool can be enhanced to include more functions such as:

1. Normalize the tables till they reach 5NF. As a result, the tool can be used to generate the following Normal Forms:

2. Because SaaS is an "on-demand software," which is a software delivery model in which software and associated data are centrally hosted on the cloud, the application can be hosted on the cloud and used as Software as a Service (SaaS).

References:

1. Connally T, Begg C., "Database Systems", Pearson Education, ISBN 81-7808-861-4
2. C J Date, “An Introduction to Database Systems”, Addison-Wesley, ISBN: 0201144719
3. S.K.Singh, “Database Systems: Concepts, Design and Application”, Pearson Education, ISBN 978-81-317-6092-5
4. 3. Kristina Chodorow, Michael Dierolf, “MongoDB: The Definitive Guide”, O‘Reilly Publications, ISBN: 978-1-449-34468-9