Database 1
Introduction

Prof. dr. Paul M.E. De Bra

Dept. of Computer Science

Eindhoven Univ. of Technology

Why do we study databases?

We live in an information-rich society:

Databases are everywhere: in your telephone (address book), your television (presets), your VCR (presets and timer program), the train ticket vending machines (stations, routes and prices), shops and supermarkets (inventory and prices), city hall, tax office, bank, etc.

Behind the user interfaces for these databases is software to manipulate data: database systems. As computer scientists we must be able to configure and optimize databases and manipulate the data stored in the databases.

What is Databases 1 about?

Database design / modeling:

analyzing properties of a database

improving / optimizing database schemes

Data manipulation:

how to translate a question from natural language to a formal query language

how to read and understand queries

Course Organization

Lecture: only week 1

Colstruction (combination of lecture+instruction): weeks 2 to 9

Labsessions: weeks 1 to 9

Homework: weeks 1 to 9

(there are small deviations due to holidays; these will be announced during the lecstructions)

Attending colstructions and labsessions and doing homework is highly advisable if you wish to pass the exam.

Effort calculation

Databases 1 is 4 ects, or 4x28=112 hours:

9 weeks of 2 hours lecture/colstr. = 18 hours

9 weeks of 2 hours labsession = 18 hours

9 weeks of 3 hours studying = 27 hours

9 weeks of 5 hours homework = 45 hours

3 hours of exam

Total: 18+18+27+45+3 = 111 hours.

Conclusion: we are not asking too much of you if you need to spend 3 hours of study and 5 hours on homework each week.

The exam

The exam consists of:

A short “pre-exam” with 3 easy questions. If you make any mistake in any of these questions you score 1/10 (and we ignore the rest of your exam).

A “main” exam consisting of exercises. The exam is “open book”. (all written material allowed, no equipment allowed)

When you are present (and registered) at  6 labsessions and hand in  6 homeworks you are exempt from the “pre-exam”.

Database Design (mostly chapter 7)

We assume that you already master:

Translation of an information system description (in natural language) to an E-R schema).

Addition of cardinality constraints to the E-R schema to express constraints from the description.

Transformation of an E-R schema to a relational schema (with “tables”).

Identification and removal of redundant tables.

Definition of (primary) keys for the tables.

Constraints

Two reasons for using (and studying) constraints:

Avoiding (detecting) data entry errors.

possible but wrong data  not detected (transfer 120₠ instead of 130₠, give student a wrong mark).

impossible data  detected (illegal bank account number or student number).

Avoid database structures that lead to redundant storage of information.

e.g. because of a derived attribute in an E-R schema.

Example of redundancy

Decomposition to avoid redundancy

Inference rules

Checking that a database instance (a table) satisfies constraints is expensive:

We try to change a database scheme so that constraints are automatically satisfied;

We try to verify the constraint on a small amount of data;

We try to avoid verifying too many constraints: some constraints are a logical consequence of others;

We try to find a minimal set of needed constraints.

Schema modification

Dealing with new constraints (or with removal of constraints):

Complete redesign: E-R schema design and translation to tables  new schema may differ a lot from the old one; lot of work adapting interfaces

Small changes to the schema of tables  need to verify the new design; little work on the interfaces

Preparation for labsession 1

Study chapter 7 of the database book, up to and including section 7.3.1.

7.1 talks about “first normal form”: having atomic values

7.2 explains pitfalls in database design: it describes constraints and redundancy

7.3.1 defines functional dependencies, the most important constraints in Databases 1.

Welcome to the course Databases 1.

This course is based on parts of the book “Database System Concepts”, by Silberschatz, Korth and Sudarshan. We will be using the 4th edition of this book.

In this introductory lecture I will be explaining the topic of this course, the way in which the course activities are organized, and the work we expect you to do.

The course material consists of the book, some additional printed material and a website with up to date information and a discussion forum.

The website also contains sets of viewgraphs, which are mostly in English, but with Dutch translation where needed or useful. The viewgraphs have auditory comments, which are in English to serve our foreign students. The interactive course activities are all in Dutch.

Before we actually start studying the topic of databases we ask ourselves why this topic exists in the computer science curriculum.

Databases are products of computer science used to manipulate data. These systems are important because they are virtually everywhere. We live in an information-rich society. By this we mean that our society relies on the availability of a huge amount of information, everywhere and at any time. We mention just a few instances of databases that we fequently use:

A GSM phone contains a list of names and numbers and perhaps also addresses. It offers a search function and lets you add, delete and modify this information. As the list consists of structured data that can be manipulated through a special interface we call it a database.

Likewise the TV and VCR contain a database, with information about stations and with timer settings.

The vending machine for train tickets at the station has a database with stations and with the price for every ticket (depending on the departure and arrival station).

Shops have a database used by the cashiers' barcode scanners to retrieve the price of every item, and to update the store's inventory.

There are many more databases used in all types of offices, including government, travel agencies, banks and insurance companies.

We are interested in the configuration, optimization and use of databases. We study how to build a database and how to manipulate the data.

The course “Databases 1” consists of two parts: one about database design or data modeling, and another about data manipulation. In order to give you enough time to become really familiar with both parts we will have two parallel tracks during this course. Each week we will study database design for half of the time and data manipulation for the other half of the time.

In the part about database design we study properties of a database that may have an influence on how we want to structure the data. A property like “the VCR can record only one program at a time” may influence how we structure the timer information in the VCR database. But also when it does not influence the structure we still need to verify that programs do not overlap so as to warn the user about this problem.

This part is fairly theoretical. We are going to learn how to prove properties of a database. You can only learn this by doing and by doing a lot of it. If you do not invest enough time in acquiring this skill you will fail the exam.

In the part about data manipulation we learn how to retrieve information from a database. We often know what we want to ask the database, but we know it in natural language (English or Dutch) and we need to translate the question to a formal query language understood by the database system. Learning to “speak” these query languages fluently can only be done through lots and lots of exercises. This will take a lot of time and effort, and if you do not invest enough time and effort into this course you will fail the exam.

We not only need to learn to ask questions to a database, we also need to be able to read the query languages so that we can understand queries that have been asked by someone else.

This lecture is the first and also last classical plenary lecture. Its main aim is to brief you on the organizational issues of this course. There is also a secondary aim, to prepare you for the first labsession.

As of this week already, you are asked to study a part of the Database book by yourself, before the labsession. During the labsession some “easy” exercises will be made on the part you studied. The instructor will take note of the progress and the problems during the labsession.

As of week 2 there will be “colstructions”. These are a combination of lecture and instruction. Difficult parts of the course material will be explained, and exercises are made that are more difficult than the ones of the labsession.

At the end of each labsession you will be given some homework. This enables you to study more before the next colstruction.

This year (2004) there are labsessions on wednesday and friday. There are a few fridays that are holidays. In these weeks there will also not be a labsession on wednesday.

Attending colstructions and labsessions is strongly recommended. During this course you need to develop new skills. This is best done in an interactive way, through large numbers of exercises. The exam consists only of exercises similar to the ones of the labsessions and colstructions. Attending colstructions and labsessions and doing the homework is a good basis for passing the exam.

It may sound strange to you but we do want to show you the effort calculation for this course. The reason for this is that we want you to understand very clearly how much effort we expect you to put into this course. This effort does not exceed the norm, and thus it is perfectly reasonable. You are at a university here, you are not on vacation!

This is a 4 ects course. Each ects represents 28 hours of work. The total number of hours you are expected to spend on this course is 112. This course is set up in such a way that we give you close to 112 hours of work and the exam is such that you need to spend close to 112 hours on this course in order to pass.

This course has 9 weeks of 2 hours lecture or colstruction and 2 hours of labsession. This makes up 18 plus 18 hours, for a total of 36 hours with guidance by a tutor.

We expect you to spend on average 3 hours per week studying part of the book or other material we provide. We expect you to be able to fully understand the amount of reading required in 3 hours time. The total study time is thus 27 hours.

We give you enough homework to give you 5 hours of work each week, or 45 hours in total.

The exam takes 3 hours, and if you have prepared yourself well you do not need any additional time before the exam.

All these numbers add up to 111 hours. In the past we have had complaints from students that this course required an excessive amount of work. We give you this calculation to make you realise that 8 hours of studying and homework per week for this course is the normal amount of work we expect and this is perfectly reasonable.

The exam consists of 2 parts: a “pre-exam” and a “main exam”. The “pre-exam” exists for 2 reasons:

It checks whether you know at least a little bit, so it is worth for us to really look at your exam and determine a precise score.

It checks whether you are able to work in a precise way. Database work is exact work. A small error in a query can result in a catastrophic difference in answer. You must be able to work precisely, not just in databases but in computer science as a whole.

The score of the exam is determined entirely through your answers on the “main” exam. The exam consists only of exercises. You do not have to learn the database theory by heart. You must be able to use the theory. You must be able to formulate correct queries and to interpret them correctly.

The exam is “open book”. You are allowed to bring any written or printed material you like. However, you are not allowed to bring any computing or communication equipment, including GSM phones, PDA's and laptop computers.

Students who attend at least 6 labsessions and hand in at least 6 homeworks are exempt from the “pre-exam”. These numbers are non-negotiable. You cannot substitute a homework for a labsession. We expect you to attend all labsessions and do all the homework. Requiring only 6+6 is the full extent of our lenience.

In this course we assume that you are already familiar with some database concepts and with the design process, using the entiry-relationship model. This subject is treated in the introductory course on information systems ISO (2R290). We assume not only that you took this course (or some equivalent course at another college or university) but also that you passed that course. In particular, you should by now master the process of database design.

When you read a description of how a company or organization wants to store, manipulate and retrieve information, you can translate this into an E-R schema that represents all the information of the natural-language problem description.

In the natural language description there are constraints, like for instance “every bank account has only one balance”. You can correctly add cardinality constraints to an E-R schema, to express these constraints in the problem description.

You can transform an E-R schema to a relational schema, with tables. You can correctly identify redundant tables or attributes and remove them without loss of information.

You can identify primary keys for the tables.

Conversely you are also able to read a database definition, given either as an E-R schema or as tables, with constraints and primary keys, and describe this information system specification in natural language.

If you do not fit this description, if you do not know enough about database design, you will encounter difficulties during this course. You should certainly study chapter 2 of the database book, and make sure you master this chapter before going on with Databases 1.

In the Database Design part of this course we will spend a lot of time studying constraints. Constraints play an important role in improving the quality of a database by eliminating errors in the data manipulation.

Constraints indicate that the data in the database must have a certain property. If someone tries to change the data in such a way that the database no longer satisfies that property the database will refuse the update. The constraint can be a property of the database as a whole, in which case we call it a static constraint, or it can be a property of the change caused by the update, in which case we call it a dynamic constraint. In this course we only look at static constraints. A good example of a simple constraint is a checksum embedded in certain numbers, like bank accounts and student identities. A typo in such a number is immediately detected by the database and the transaction is then refused. Other examples of constraints are that a birth-date cannot be in the future, people are allowed to have only one birth-date, some bank accounts are not allowed to have a negative balance, the amount withdrawn through an ATM cannot exceed 1000€, etc.

Constraints cannot prevent all errors. You can transfer 120 or 130€ to a friend and the bank has no way of knowing whether 120 or 130 is the correct amount.

Constraints can also be used to help a database designer in changing the database schema in order to avoid redundant storage of information. For instance, it is not a good idea to store people's birth-date and age as one can be derived from the other. And since a bank account can have only one balance, the database schema should be such that the balance of an account is stored only once, even if for instance the account is shared between two people.

Here is an example of a table representing bank account information. It seems logical at first: for every bank account we have an owner, the account number and the balance. However, we see that Smith and Jones are joint owners of account A-215. Luckily for us the balance is listed as 540 twice, otherwise there would have been an error.

But of course the fact that the balance is stored twice and that there is thus a risk of having incorrect information is a sign that this is a bad database design. And even if the database is implemented correctly and always keeps the two balances of A-215 the same, the database has to do twice the amount of work.

We are going to study constraints because we want to design databases that are better than this. We want to avoid redundancy whenever we can.

In this course we will learn how to decide that the two tables we see here represent the same information as the single account table, but without any redundant information. In this new scheme we have a table with names and account numbers, representing the owners and their accounts. People can have several accounts, although in this example table nobody has two accounts. The second table gives for each account the balance. Every account has only one balance and hence every account number is allowed to occur only once in this table. The account number is a key for this table.

This example also illustrates another very important aspect of our study of databases: You cannot see everything in an example table or instance as we call it.

You need to know what the properties of the database are by studying the description of the database. Constraints defined for a database are properties that must always hold, in every instance. We have an instance here in which every person has exactly one account, but this does not mean that in the database every person can have only one account. A constraint is always specified at the schema level, not the instance level. If a constraint holds in a database it is a property of every instance. And if there is one instance that we consider to be a valid instance, and in which the constraint does not hold then the constraint does not hold for the database.

A lot of the database theory we study deals with trying to simplify or even eliminate the verification of constraints.

The bank account example shows that where it was difficult to verify in the large table that every account has only one balance, in the second example this has become trivial since every account number and thus also every balance can only occur once. There is no more need to check whether the duplicates have the same value as there are no more duplicates.

Another approach to reduce the work is to only check changes that are made during an update. We will not investigate this in Databases 1 as it is related to the topic of dynamic constraints that we don't cover.

We sometimes notice that there is redundancy among the constraints. A typical example is transitivity: If for every course there is only one lecturer, and if every lecturer has only one phone number, then for every course there is only one lecturer's phone number. So if we have checked that for every course there is only one lecturer and if we have checked that for every lecturer there is only one phone number we no longer have to check that for every course there is only one lecturer's phone number because that is automatically true. We can thus save time and effort by analyzing whether some constraints already logically imply some other constraints we wish to verify. We use a system of inference rules to find such dependencies between constraints.

To further reduce the amount of work we not only want to eliminate unnecessary constraints, but find the smallest set of constraints, that can be verified with the least amount of effort.

Sometimes a company or organization changes how it deals with information. Business rules may change. A constraint like “for every course there is only one lecturer” may be dropped by the university. A constraint like “every bank account has only one owner” may be introduced.

One approach to deal with such changes is to redo the E-R design, and then translate the new design to a structure of relations or tables. Unfortunately the new relational schema may differ a lot from the old one. This implies that a lot of the software for manipulating the information, like queries on the tables and user interfaces for entering or retrieving information may need to be redesigned and reimplemented.

A different approach is to take the existing relational schema and check whether the changes in the constraints can be handled by a small change in the table structures. Changing very little implies that the programming and the interfaces also change very little. We will therefore investigate how we can adapt relational database schemas to changes in the constraints, without reconsidering the original E-R design.

Before each labsession in this course you need to study part of the database book. During the labsession you will be given exercises that you cannot answer if you have not studied the corresponding part of the book.

For the Database Design track of this course you need to study the beginning of chapter 7, up to section 7.3.1.

Section 7.1 explains “first normal form”, or the need for using only atomic values. Structured entities like a postal address need to be decomposed into atomic parts like street, number, postal code and city in order to use them in a relational database.

Section 7.2 introduces constraints, redundancy and decomposition, and the role these concepts play in databases.

Section 7.3.1 introduces the most important type of constraint for this course: the functional dependencies.

Databases 1, College 1

Introduction and Database Design

Introduction and Database Design

Paul De Bra

2003-04-01T22:52:54

Paul De Bra