Relational Databases and Data Normalization

Previous Section

Chapter 3 Directory

Online Textbook

Next Section

Chapter 3 Section 4

Relational Databases and Data Normalization

Databases can be either single-user or multi-user applications. A collection of recipes on a personal computer is probably a single-user application, but a student record system on a main frame is a multi-user application. Each database may be either single or multi-user. We introduce them in this chapter.

In this section we will begin with an overview of database terminology and concepts, which will be followed by an examination of how data is organized and managed in relational databases using normalized tables.

In a simple index card database, such as a Rolodex file, each card (or record) contains the same spaces (called fields) for items of data, such as "Last Name" "First Name" "Phone #" "Company" etc. This type of data organization works well for simple tasks, such as organizing a list of phone numbers, but does not allow for the inter-relationships between different groups of data items that more complex data management applications require.

If we examine three records taken from a simple Rolodex file "card by card," the data might look like this:

_______________________________________
Last Name: Smith
Phone #: 843-5467 First Name: Ralph
Company: Roico
_______________________________________
Last Name: Brown
Phone #: 843-7890 First Name: Robert
Company: Bainbridge
_______________________________________
Last Name: Binder
Phone #: 876-5252 First Name: Mike
Company: Albright
_______________________________________

Each "card" above represents one record, and each record consists of four data fields. By contrast, relational databases are based upon data relationships defined through the use of tables. Each table consists of rows and columns, with key relationships between certain data items in each table establishing links. In tabular form, where each row is a record, and each column a field, the same data would look like this:

Last Name First Name Phone # Company
Smith Ralph 843-5467 Roico
Brown Robert 843-7890 Bainbridge
Binder Mike 876-5252 Albright

When more complex databases are created using several tables such as these, the various tables represent different data entities, which exist within the overall view of the data. Entities within databases are simply combinations of certain elements of the data that we wish to examine in terms of both their contents and their relationship to each other. To examine the implications of complex databases, we will use the example of a college's student information system, designed to record and report upon students, courses, and the relationships between the two.

In the following sample database application, there is a table containing information about students. In that table, there is a record for a student (an entity) called John Murdock. Each column (field) in the table represents an attribute of the entity, that is, some data item that describes the entity. For example, "student name" is an attribute of a student.

One or more attributes make up a unique 'key' for the record (also known as an instance or, in terms of the table, a row). If the key is a combination of two or more attributes, it is called a combined or concatenated key. The components of a concatenated key are generally keys from other tables, and each part of the concatenated key also serves as a link to the original table. The components of a concatenated key from other tables are referred to as foreign keys. The use of concatenated keys in normalized data tables is explored in the example at the end of this section.

In the example of the college information system, John Murdock's student identity (ID) number is a unique value that is used on the computer system to identify him as a student. Later we will see how the student ID number key is also used as part of a concatenated key.

Non-key data items only have meaning when associated with their key values. For example, John's record on the student table might contain a phone number. Taken by itself, without the ID number that connects it to a name, the phone number is a meaningless piece of data.

In the student/course database, multiple tables are used to manage the information pertaining to student enrollment in courses. For example, one table contains data about students. A second table will contain data about courses available, while a third table represents the relationship between the other two entities, resulting in a third entity.

The diagram below illustrates the nature of the relationships among these tables. A single point on the connecting arrow denotes a single instance of the entity and a double point represents a multiple instance. What this means in this example is that a single student could be enrolled in many courses, but that each enrollment instance is associated with a single student. Likewise, on the other side of the diagram, a single course can have many enrollments, but each enrollment is only associated with a single course.

TABLE 1 (STUDENTS) <---->>TABLE 2 (ENROLLMENTS) <<----> TABLE 2 (COURSES)

To describe this another way:

A student instance can be related to (or linked with) many enrollment instances.

An enrollment instance must relate to one and only one student instance.

A course instance can be related to (or linked with) many enrollment instances.

An enrollment instance must relate to one and only one course instance.

We would describe the relationship of student instance to enrollment instance in the example above as a one-to-many relationship. In this definition, we have also assumed that a student instance can exist without an enrollment instance. That is, there can be a student who has not yet enrolled in any courses. We have also assumed a course can exist without anyone enrolled in it.

The essential function of such a system is called a query, which is basically a question the user asks the database.

With a system such as this you can obtain answers to many different queries. Some may involve only one table, e.g., "Who is registered in the course COMP?" This would provide student names only. More complex queries involving extracting data from more than one table are also possible, as shown in the following examples.

Who is enrolled in course # 6543–provide student names and numbers

These types of queries are generally written in a fourth-generation language such as SQL (Structured Query Language). This language allows you to use an English-like syntax for expressing the query, rather than having to use the mathematical operators that form the functional basis of relational systems. The following is an example of SQL.

The expression "SELECT STUDENT_NAME, STUDENT_ADDRESS, PROGRAMME_REGISTERED" identifies the fields or data items to include in the response. "FROM STUDENT" tells the system what table to look at, and "WHERE PROGRAMME_REGISTERED= COMP" places a filter on the search, excluding from the report any data from records of students registered in programmes other than "COMP."

Some graphical systems generate SQL for the user by providing a point and click interface to build the query. Graphical languages and SQL are non-procedural programming, which means they involve telling the computer what is wanted, rather than how to do the query, as a procedural programming language like COBOL would require. Fourth-generation languages and graphical interfaces provide tools that can be used by trained users or programmers, depending on the complexity of the problem and skill of the user. Both fourth-generation languages such as SQL and graphical database interfaces make querying the database much easier than using a procedural programming language to perform the same queries.

For relational databases to work properly with multiple tables, the tables must be designed in such a way as to avoid the use of duplicate non-key items, and also to ensure that all non-key items are fully associated with the appropriate key(s). This process is called data normalization and is usually done in stages, usually stopping after three. These stages of normalization are known as 1NF (First Normal Form), 2NF (Second Normal Form) and 3NF (Third Normal Form).

The designer of the database is responsible for ensuring the data is correctly normalized. Only then can the powerful mathematical operators underlying the relational query languages be used with certainty.

We will go through some steps and tests to illustrate the process of normalization to the Third Normal Form (3NF). Students interested in additional tests to normalize relational systems beyond this level may wish to take systems analysis and database courses.

Starting with an un-normalized student record, we would see the following fields:

Here are examples of data that the actual records in this format might contain:

First record:

343567
John Murdock
5214 154 St
Athabasca
AB
Z1Z 2Z2
5200
BSc CIS
120
090197

COMP268
Introductory Programming
3
82
COMP272
Data Structures
3
77

Second record:

444765
Mary Kimbel
3333 123 Ave
Athabasca
AB
Z1Z 2Z6
5100
BA IS
120
090196

The type of record view shown above is sometimes referred to as a user view. This is a useful form for data to appear in reports generated for users of the system, but is not a convenient or efficient form for a relational database program to store or manage the data.

In this state we would have to search every record instance to find out course information such as who is enrolled in a particular course. The form above would not work with relational systems, because it is not in a tabular format with rows and columns. To display data in tabular form, it must be rearranged to eliminate repeating fields. Data in tables cannot have multiple data items, such as those for course information, in the same row and column. For example, in the row on the table for Mary Kimbel, the column for the course field could not contain all three courses.

Stage 1 of the normalization process is to remove repeated fields, convert the design to First Normal Form (1NF) and represent the data in a table. Stage 1 is sometimes called a flat record form. The process creates an additional table that will include the key from the original list of fields. We now have:

Table 1
student ID # (key)
student name
student address
programme #
programme name
programme credits
date registered

In this form, sample student records would contain the following data:

First record:

343567
John Murdock
5214 154 St
Athabasca
AB
Z1Z 2Z2
5200
BSc CIS
120
090197

Second record:

444765
Mary Kimbel
3333 123 Ave
Athabasca
AB
Z1Z 2Z6
5100
BA IS
120
090196

To contain the course information removed from the above, a second table is created, as follows:

Table 2
student ID # (a foreign key and part of the concatenated key)
course # (a foreign key and part of the concatenated key)
course name
credits
grade achieved

Sample records for this table would contain the following data:

343567/COMP268
Introductory Programming
3
82

343567/COMP272
Data Structures
3
77

444765/COMP268
Introductory Programming
3
88

444765/COMP272
Data Structures
3
72
etc.

444765/COMP314
Computer Organization
3
77

In the above records, it is important to note that the concatenated key of student ID number and course number provides a unique identifier for every record. Note that for each row in Table 1, there may be multiple rows in Table 2. This is possible because the student ID # and course # combine to make a concatenated key for Table 2. The student ID # and course # also act individually as links to the related student and course rows. These links are the foreign keys.

In this state we will still have duplicated information about course names and credits. To change the name or credits for a course, we would have find every occurrence of that information.

The duplication occurs for every student/course combination because there is more than one student in a particular course, and the course information appears in more than one place. As well, First Normal Form cannot have any information about a course until at least one person enrolls in that course.

Stage 2 of the normalization process is to ensure that all non-key attributes (data items) are identified by the full key. In other words, there should be no components in a concatenated key that are not required to uniquely identify the data items. For example, in the form above, the course number specifies the course name, which doesn't require the student identifier.

It is generally necessary to create a new table to separate those data items that require different keys. In our case this change splits Table 2, as some attributes need only the course number, others need course number and student identifier.

We now have the following tables:

Table 1

student ID # (key)
student name
student address
programme #
programme name
programme credits
date registered

Table 2

student ID # (a foreign key and part of the concatenated key)
course # (a foreign key and part of the concatenated key)
grade achieved

Our first record in this table would now contain the following data:

444765/COMP314
3
77

The new table would contain the following fields:

Table 3

course # (key)
course name
credits

Note that with the creation of the third table we can now have a record for a course with nobody registered in it, e.g.:

COMP485
Distributed Systems
3

In this state we still have duplicated information about programme name and start date. To change the name or start date for a programme will mean finding every occurrence of that information. That is, information about the name of the programme and the programme credits is stored for every student enrolled in 5200, instead of being stored in one place in a programme table. Also, there will be no information about a programme until at least one person registers for that programme.

Stage 3 of the normalization process is to ensure all non-key attributes (data items) are independent of the other non-key attributes in the table. In the example above, programme name and programme descriptions are dependent upon programme number.

Again, we will need to create new tables. In our case, this change splits Table 1, as some attributes are identified by the non-key attribute, category number. We will leave the programme number in Table 1 to act as a link (foreign key) into the newly created table. We now have:

Table 1

student ID # (key)
student name
student address
programme # (foreign key)
date registered

343567
John Murdock
5214 154 St
Athabasca
AB
Z1Z 2Z2
5200
090197

444765
Mary Kimbel
3333 123 Ave
Athabasca
AB
Z1Z 2Z6
5100
090196

Table 2

student ID # (a foreign key and part of the concatenated key)
course # (a foreign key and part of the concatenated key)
grade achieved

Table 3

course # (key)
course name
credits

Table 4

programme # (key)
programme name
programme credits

Note that we can now have a record for every programme, including those with nobody registered in them.

We have systematically broken the large record structure down into tables–one table for each entity (or thing of interest). All the non-key attributes (data items) in a table are fully related to the key for that table. We have also eliminated all duplication of non-key data items. Some software design tools automate the process for the designer where a dictionary of data items already exists.

In summary, a table is a collection of records collated by a unique key for each record. A record can contain a number of data fields. The process of normalization is a way of organizing the records and data fields within tables to reduce redundancy and optimize ease of access.

In conclusion, we have introduced normalization as a design tool for use in data modeling. Data modeling means basing the design of your application on a relational model of the data. Many different models are used when designing applications. The relational model is widely used but has limitations. Many of these limitations are addressed in the object model. It is expected that in the near future, object databases will be widely used in the more complex applications that cannot be easily handled with relational databases.

Created: January 17, 1997
Last Update: October 27, 1998

_______________________________________
Last Name: Smith Phone #: 843-5467	First Name: Ralph Company: Roico
_______________________________________
Last Name: Brown Phone #: 843-7890	First Name: Robert Company: Bainbridge
_______________________________________
Last Name: Binder Phone #: 876-5252	First Name: Mike Company: Albright
_______________________________________

Last Name	First Name	Phone #	Company
Smith	Ralph	843-5467	Roico
Brown	Robert	843-7890	Bainbridge
Binder	Mike	876-5252	Albright