Database Concepts

Before databases, data was often kept in a file-based approach: each program had its own text files, and each line of a file held the data for one item.

Think of a theatrical agency that makes bookings for bands. It sets up a computerised system that uses text files. One text file stores data about individual band members. Each line of the file holds this data for one band member:

• name
• contact details
• banking details
• band name
• band agent name
• band agent contact details

The file can be used when the agency needs to contact a band member, directly or through the band’s agent, and after a gig when the band member has to be paid. The file might have a thousand or more lines. Here is a selection of the given names, family names and band names from various lines:

There are clear problems with this data:

• When Vandana Graham’s data was first entered, her names were put in the wrong order. A correct entry was added later, but the wrong one was never deleted. No validation check could have found the first mistake, and this problem can happen in any system, not only a file-based one.
• Dylan Stoddart has no band name. Validation should have caught this missing value.
• The Precious Olsen lines are examples of duplicated data and inconsistent data: she is stored twice, in two different bands. (Mahesh Ravuru is also stored twice.)
• A band name could also be typed in for a band that does not exist, and nothing in the file would show this.

So a file-based approach can lead to data integrity problems in a single file. The reason is that there is no built-in control when data is entered. The database approach can prevent these problems, or at least make them less likely.

A second problem is data privacy. The file was designed so that the finance section could find banking details and the recruitment section could find contact details. But there is no way to control access to only part of a file, so staff in recruitment could also see the band members’ banking details. A database system can handle data privacy properly.

Because of the privacy problem, the agency decides to keep a separate file for each department. The table shows the main data stored in each department’s file:

Now the same data is stored in several files. This is called data redundancy. It does not mean the data is no longer useful: it means that once data has been stored in one file, there should be no need to store it again in a different file. In a file-based system some data redundancy cannot be avoided.

Data redundancy can lead to data inconsistency: two copies of the same data that do not match. This happens because of mistakes when the data is first entered, or because one copy is edited later and the other is not. This is a second cause of data lacking integrity. One of the main aims of the database approach is to remove data redundancy.

The problems so far are about storing the data. There are also problems when programs use the files.

Traditionally, a programmer wrote a program and, at the same time, defined the data files that the program needed. In the agency, each department would have its own programs to use its own files. The programmer must know exactly how the data is laid out in the files, for example that the fourth item on a line is the band name. This is called data dependency: the programs depend on the structure of the files.

Files used by one department probably hold some of the same data as other departments’ files, but there is no plan for sharing files.

Data dependency causes two more problems:

• Changing what is stored is expensive. Suppose more and more bands perform with extra session musicians, and their data must be added to some files. The existing files must be rewritten, and then the programs must be rewritten so that they read the new files correctly. With a database, the existing programs could still run after the new data is added: the only new programming is for the programs that use the new data.
• New applications are hard to build. File structures designed to suit particular programs may not suit a new use. If the agency wanted to analyse how successful its gigs have been over several years, getting that data out of the files would be complex and would take a long time.

A flat file keeps all the data in one single table. Here is a single table that stores which students are in which classes:

A relational database avoids many of the flat-file problems by storing the data in several tables that are linked together by relationships. The single table above could be stored as a relational database with this structure:

Each box is a database table, and the list in each box shows the categories of data (the fields) stored in that table. The lines between the tables are the relationships that link them.

Look at the Student and Enrolment tables. The StudentID field is in both. Each student’s details appear in the Student table only once, but the student can be enrolled in many classes. The data could now look like this:

In the Student table each student is recorded once. In the Enrolment table, only the StudentID is repeated. If a student’s details need to change, they are changed in one place, the Student table. So there is much less data redundancy, and less chance of errors that lead to inconsistent data.

A database is an organised collection of data. In theory, even a well organised filing cabinet is a database. But computer systems produce huge amounts of data, so electronic databases have become a necessity. You could not realistically keep an index of every website on the internet in a filing cabinet, and even if you could, imagine how long it would take to find all the websites about cats.

Electronic databases must be well designed from the start, so that data can be stored and retrieved as efficiently as possible, and to avoid problems such as inconsistent and duplicated data.

A table is a collection of related data, made up of records and fields. Imagine a school that stores data about students, staff, classes and grades. This is a table it might use to store data about each student:

• Fields give the category heading for each item of data in the table. Here the fields are StudentID, LastName, FirstName and Email.
• A record is a collection of data about one object, person or thing. In the student table, a record is one row: the data about one student.

Each table in a database should represent a single entity. An entity is an object in the real world that can be told apart from other objects. It can have:

• a physical existence, for example a customer or a product
• a conceptual existence, for example an order or a booking.

In the example, the entity is a student. Everything the school wants to store about a student is an attribute of the entity, and each attribute becomes a field. Each student has their own row in the table: a record.

In relational database language, a record is also called a tuple. So a tuple is one row of a table, such as (246524, Afridi, Shaheen, s.afridi@cswithzain.com).

Note Indexing is also part of this topic: an index is a separate, quick-to-search list of key values with pointers to the matching records, which makes searching a large table faster. It is explained with the other DBMS features in 8.2.

A primary key is a field (or fields) in a table that acts as a unique identifier for each record. A primary key value can never be repeated within a table, so each record in the table is unique.

Here is part of a Subjects table from a school’s database:

Which field is suitable as the primary key?

• SubjectName is not unique: Computer Science and Math each appear more than once, so it cannot be the primary key.
• Level is not unique either: GCSE and A Level are repeated, so it cannot be the primary key.
• SubjectID has been included to make sure each record has something unique about it.

Making SubjectID the primary key means no other record in the table can have a SubjectID that is already in use.

Sometimes there is an obvious choice for the primary key. Every published book has an ISBN (International Standard Book Number) that is unique to that book, so a table of the books in a library can use the ISBN as its primary key.

In other cases it is harder to find a suitable field. A common solution is to give each record a number as its primary key, like StudentID in the student table:

A composite key is a primary key made up of more than one attribute.

Suppose a school offers tutoring sessions after lessons. Each teacher must deliver one session a week for each subject they teach. The Tutoring table stores which teacher delivers each session, on which day, and in which room:

Even in this small sample, no single attribute can be guaranteed to be unique:

• There can be more than one session for the same subject: subject 5 has sessions on Monday and Friday.
• The same teacher can deliver more than one session a week: teacher 278 delivers sessions for subjects 3 and 4.
• There can be more than one session (for different subjects) on the same day.
• More than one session can take place in the same room (on different days).

But a teacher delivers only one session for a given subject each week. So the combination of SubjectID and TeacherID is unique for every record, and these two attributes together form a composite primary key.

When you design your first database with several tables, you may want to avoid composite keys by adding a new attribute that is unique for each record, such as an auto-incremented TutoringID. This is not necessary. Even with a TutoringID, the table would still need the SubjectID and TeacherID columns to show which teacher delivers each session. Since that data is already in the table, and the two values together are unique, they are an effective and correct choice for the primary key.

A candidate key is an attribute, or the smallest set of attributes, in a table where no tuple has the same value. In other words, it is any attribute (or set of attributes) that could be chosen as the primary key.

In this table, StudentID and Email are both candidate keys: no two students share either value. LastName (two students called Ronaldo) and FirstName (two called Shaheen) are not.

StudentID has been chosen as the primary key. A secondary key is a candidate key that is an alternative to the primary key, so here Email is a secondary key.

A foreign key is the primary key field of one table that appears in another table, to make a link between (join) the two tables. Foreign keys help keep the relationships between tables correct: for example, a foreign key value can only be put into a table if that value already exists as a primary key in the other table.

The example below has three tables:

• Student: StudentID, LastName, FirstName, Email
• Subject: SubjectID, SubjectName, Level
• Enrolment: EnrolmentID, SubjectID, StudentID, TargetGrade

Each table has its own primary key, and the Enrolment table has two foreign keys that link it to the Student and Subject tables. The data in the Enrolment table could look like this:

SubjectID and StudentID are foreign keys: the data in these fields links to the tables where those fields are the primary keys. A student can enrol on more than one subject, so including StudentID as a foreign key links each enrolment to the student’s record in the Student table. This avoids storing all the student’s details again for every enrolment: only the StudentID is repeated.

To find out who student 246524 is, look in the Student table:

Student 246524 is Shaheen Afridi, and the Enrolment table shows she takes the subjects with IDs 1, 3 and 5. To find out what these are, look in the Subject table:

Opening every table to match up the foreign keys by hand would take a long time. Because the data is linked, SQL can query the database and pull out this information for you. For example, an SQL query can find all the subjects taken by Shaheen and give this output:

A relational database can improve data integrity further by enforcing referential integrity. At its simplest, when a record is added to a table and a value is put in a foreign key field, the system checks that the value exists in the primary key field of the linked table.

For example, students are enrolled on subjects. If referential integrity is enforced, the system checks that a student with the given StudentID exists in the Student table. If it does not, that StudentID cannot be used in an enrolment record.

Referential integrity can also say what happens when a record is updated or deleted:

• If a primary key value is changed, the matching foreign key values can be updated automatically.
• If a record is deleted, the records with matching foreign key values can be deleted too.
• There are other options as well, such as stopping the change.

Very often you will not want data to be deleted automatically, because it gives useful management information or is still needed for day-to-day queries. When a student leaves the college, it is more likely that you would store a ‘date left’ attribute than delete their data. The student can then be left out of registers and progress monitoring, but still be counted when enrolments or course completions are analysed.

As a database designer, one of your jobs is to keep the integrity of the data as high as possible. You learn how to enforce referential integrity when you create tables with SQL.

In an entity-relationship (E-R) diagram, each entity is drawn as a rectangle. A relationship between two entities is drawn as a line, and it is one of three types:

The line shows the cardinality of the relationship. Cardinality can be one or many: it is the number of times one instance of an entity can be linked to instances of the other entity. Read the cardinality at the end of the line nearest each entity. For a cardinality of one, the end of the line is straight. For a cardinality of many, the end splays out into a crow’s foot.

By far the most common relationship is one-to-many. In the early stages of design you will also find the other types. A many-to-many relationship cannot be implemented directly in a relational database: it has to be resolved first (see below).

Examples of each type:

• Many-to-many: pupil and teacher. Each pupil is taught by many teachers, and each teacher has many pupils.
• One-to-many: pupil and appointment. Each pupil books many appointments, and each appointment is for one pupil.
• One-to-one: head teacher and school. Each head teacher runs one school, and each school is run by one head teacher.

Once you have found all the entities and relationships, you can put them together into an E-R diagram:

There is a standard notation for describing an entity:

EntityName(PrimaryKey, attribute1, attribute2, attribute3, …)

It starts with the name of the entity, followed by its attributes in brackets. The primary key is underlined, and is usually written first. If the primary key is a composite key, every attribute in it is underlined. (On this page, the primary key is shown in bold. In the exam, underline it.) Entity names are written in the singular, for example Member, not Members.

A sports club records the courses its members are assessed on. These are its entities in standard notation:

• Member(MemberId, FirstName, LastName, Phone)
• Course(CourseCode, Description, Fee)
• Instructor(InstructorId, FirstName, LastName, Email)
• Certificate(MemberId, CourseCode, AssessmentDate, InstructorId)

Certificate has a composite primary key. The combination of MemberId and CourseCode makes each record unique, so no entry can be duplicated.

The relationship between Member and Course is many-to-many: each member can be assessed for many courses, and each course is assessed for many members.

The relationship between Member and Certificate is one-to-many: each member can gain many certificates, and each certificate is awarded to just one member.

The relationship between Course and Certificate is also one-to-many: each course can have many certificates (one for each member who completes it), and each certificate is for just one course.

The relationship between Instructor and Certificate is also one-to-many: each certificate has one instructor, and each instructor can carry out many assessments.

The completed E-R diagram looks like this:

If an exam question gives you entity descriptions, you can find the relationships from the keys. Here are the sports club entities again:

• Member(MemberId, FirstName, LastName, Phone)
• Course(CourseCode, Description, Fee)
• Instructor(InstructorId, FirstName, LastName, Email)
• Certificate(MemberId, CourseCode, AssessmentDate, InstructorId)

Look at each entity whose primary key is a single attribute. If that attribute is also in another entity, either as a non-key attribute or as part of a composite primary key, there is a one-to-many relationship from the first entity to the second.

• If two entities have the same primary key, the relationship is one-to-one.
• If two entities share an attribute that is the primary key (made of a single attribute) of one of them, the relationship is one-to-many.
• If two entities share an attribute that is not a single-attribute primary key in either of them, there is a many-to-many relationship that needs resolving.

Take care with composite primary keys. No part of a composite key is unique on its own: only the combination is a unique identifier. In Certificate, each part of the composite key is also a foreign key, so CourseCode is a foreign key (and part of the composite primary key), and the relationship between Course and Certificate is one-to-many.

A many-to-many relationship cannot be implemented directly in a relational database. One record in a table cannot hold a list of many foreign key values, because that would break first normal form.

Instead, it is resolved with a link table (also called a link entity): a new table between the two entities. The link table holds the primary key of each of the two tables as foreign keys, and usually these two foreign keys together form its composite primary key. The one many-to-many relationship becomes two one-to-many relationships, each with the crow’s foot at the link table.

The sports club already does this. Member to Course is many-to-many, and Certificate is the link table: Member to Certificate and Course to Certificate are both one-to-many, and Certificate’s primary key is MemberId plus CourseCode. In the same way, the Enrolment table links Student and Subject.

Normalisation is a technique used when designing a database to reduce duplicated data. It also improves data integrity.

In his important work on relational databases, Edgar F. Codd proposed a three-stage process, in which each stage reaches a normal form. His work was later extended, and you may see other stages in textbooks or online, but a database is usually considered normalised if it is in third normal form (3NF). For the exam, you only need to normalise to 3NF.

Data that has not been normalised at all is sometimes called 0NF (zero normal form, or unnormalised). Each stage of normalisation removes one kind of problem:

Back to the sports club. If a flat-file approach has been used to store the data about members and their certificates, the instructor might keep it in a spreadsheet or even a word-processed document:

This gives one record for each member, and a member’s certificate data is spread over several values in one cell. The instructor could sort and filter on member details, but could not work with the certificate data, because there are several values in each cell.

Another way is to make each row the award of one certificate. Then the member’s details must be repeated on every row:

Either way works when there are only a few records. But it is not an efficient way to hold the data: it is hard to analyse, and data is duplicated for no reason. In a large system, duplicated data can become inconsistent, as described earlier. If you look carefully at the data, you may spot some inconsistencies already.

To design a better system, the data must be stored in one or more linked tables, and every table must be in third normal form.

Normalisation has a reputation for being difficult, but the basic idea is simple: there must be a table for each entity, and in each record every attribute must be fully dependent on the primary key.

Before the rules of normalisation, you need to know what a dependency is. In database design, a dependency is a value that varies in line with another value.

In the flat file, the course description varies in line with the course code. Whenever you see the code CR0001, you find the description Kayaking. So the description is dependent on the course code.

But be careful not to assume a dependency. Always check any assumption with someone who understands the organisation and its current system. If the design is wrong, the database structure may have to be changed later, which can mean a lot of extra work.

To decide whether data is in first normal form (1NF), check that:

• each record has a primary key
• the data in each field (column) is atomic
• no record has repeating groups of attributes.

Look again at the original flat file, with one record for each member (the first table in the worked example). Check each rule in turn.

Does each record have a primary key? Yes. MemberId is unique for each record, so it can be the primary key. If no attribute, or combination of attributes, could be guaranteed to be unique, you would need to add a new attribute to give each member a unique ID.

Is the data atomic? Data is atomic when a column holds a single value that cannot sensibly be divided further.

• The Name field is not atomic. It has two separate parts, first name and last name, so it is split into two fields: FirstName and LastName.
• The course description is atomic. Some descriptions have two parts, such as Judo L1, but the parts do not make sense on their own.
• AssessmentDate could be said to have three parts (day, month and year), but date fields are not usually split, because there are many date functions that can pull out the parts.
• The instructor’s name is not atomic. There are two instructors called Sue, and one is told apart from the other by being written “Sue R”. So it is split into InstructorFirstName and InstructorLastName.

Are there repeating groups of attributes? A repeating group of attributes is a set of attributes that appears more than once in a record. Sometimes a single attribute repeats, and this must be dealt with too.

Here there is a repeating group about certificates: Abdel Patel, for example, has gained three certificates. The attributes that repeat are CourseCode, Description, AssessmentDate, Fee, Instructor (now split into InstructorFirstName and InstructorLastName) and Email (now renamed InstructorEmail).

A repeating group must be moved to a new table, and removed from the original table. When you move it, you must still be able to link each moved record back to its original record, so the new table also gets a copy of the original primary key. Here, all the attributes about certificates go to a new Certificate table, and each certificate gets the MemberId of the member who gained it.

This is the new Certificate table, with all the atomic attributes from the repeating group. Each certificate now has its own record, linked back to its member by MemberId. The instructors’ surnames have been filled in. Its primary key is the composite key MemberId and CourseCode:

Certificate(MemberId, CourseCode, AssessmentDate, Description, Fee, InstructorLastName, InstructorFirstName, InstructorEmail)

This is the Member table, with the name split into two attributes and the repeating group removed:

Member(MemberId, FirstName, LastName, Phone)

Both tables are now in first normal form.

The rule for second normal form (2NF) is: the tables are in 1NF, and there are no partial dependencies.

A partial dependency is a non-key attribute that depends on only part of a composite primary key. So partial dependencies can only happen in a table with a composite key. The Member table has a primary key made of a single attribute, so it is already in 2NF.

The Certificate table has a composite primary key (MemberId and CourseCode), so it must be checked. For each non-key field, ask: does it depend on the whole key, or on just MemberId or just CourseCode? (Remember: a dependency is a value that varies in line with another value.) The two key fields are the first two columns, marked PK:

• AssessmentDate depends on the whole composite key: it is the date that a particular member was assessed on a particular course.
• Description depends only on CourseCode. Whenever you see the code CR0001, you find the description Kayaking. This is a partial dependency.
• Fee also depends only on CourseCode. Whenever you see the code SP8701, you find the fee 30.00. This is a partial dependency.
• InstructorLastName depends on the whole composite key: it is the surname of the instructor who assessed a particular member on a particular course. InstructorFirstName and InstructorEmail are the same.

Note In this small sample, each course happens to have only one assessment date and one instructor. The design follows how the club works: each member is assessed separately, possibly on a different day by a different instructor. This is why a dependency must be checked with the organisation, not guessed from a few rows of data.

The two fields with a partial dependency, Description and Fee, are moved to a new table, together with a copy of the part of the key they depend on, CourseCode. The new table has one record for each course, so it is called Course, and its primary key is CourseCode:

Course(CourseCode, Description, Fee)

Description and Fee can now be removed from the Certificate table. They can be found from the Course table, by linking through CourseCode:

Certificate(MemberId, CourseCode, AssessmentDate, InstructorLastName, InstructorFirstName, InstructorEmail)

Member, Course and Certificate are now all in second normal form.

For third normal form (3NF), the tables must be in 2NF and have no non-key dependencies. A non-key dependency is a non-key attribute that depends on another non-key attribute, rather than on the primary key (it depends on the key only indirectly, through the other attribute, so it is also called a transitive dependency). All three tables must be checked.

Member table. This is in 3NF. Every field depends fully on the primary key, MemberId: each record describes one club member, and the attributes are only about that member.

Course table. This is in 3NF. Every field depends fully on the primary key, CourseCode.

Certificate table. This one has a non-key dependency:

The instructor’s first name and last name depend on the instructor’s email address, which is not a key. Whenever you see a particular email address, such as Jay12@example.net, you find the same first name and last name, Jay Linton. So a new Instructor table is needed.

Email is not a good primary key for the new table. Each email address seems to identify one instructor, but two people could share an email address. When you choose a primary key, do not only look at the data you have; ask yourself: “Could two records ever have the same value in this field?” You should also choose a field whose value will not change, and people often change their email address. InstructorLastName cannot be the key, because two instructors may have the same last name, and InstructorFirstName cannot either, for the same reason.

A practical solution is to add a new attribute, InstructorId. Each instructor gets a unique number, and this number is stored in each certificate record, so the instructor can be identified. In the new Instructor table the word Instructor has been removed from most attribute names, because every record describes an instructor, so there is no confusion:

The instructor details can now be removed from the Certificate table and replaced by the single attribute InstructorId. InstructorId is a foreign key in the Certificate table, and it lets the instructor’s details be found when they are needed. This is the Certificate table in third normal form:

The tables are now in third normal form, and all the unnecessary duplicated data has been removed. Here is the final design of each table, in standard notation, with an extract of its data. A foreign key is marked FK.

Member(MemberId, FirstName, LastName, Phone)

Course(CourseCode, Description, Fee)

Instructor(InstructorId, FirstName, LastName, Email)

Certificate(MemberId, CourseCode, AssessmentDate, InstructorId)

Compare this with the E-R diagram drawn earlier for the same club: there is one table for each entity, and each one-to-many relationship is made by a foreign key in the Certificate table.