Introduction to database management systems

The database course starts with an introductory week in which you learn the language of the rest of the semester. In the exam this week usually shows up as definition, classification and “which one?” questions: schema or instance, physical or logical independence, DDL or DML, which letter of ACID. They are short questions, but it is easy to lose points on them. Five things to keep in mind:

1. A DBMS = data + the collection of programs that access that data. The goal is to keep data both easy to use and safe.
2. The schema is the design, the instance is the data right now. The schema rarely changes, the instance changes constantly.
3. Three levels: external, logical, physical. The independence between them comes in two kinds.
4. DDL changes the structure, DML changes the data.
5. A transaction either happens completely or not at all. ACID describes this with four properties.

The database we use all semester

In every week we use the same small university database. That way the ER diagram, relational algebra, SQL and normalization are all discussed on the same tables, and you can check the result of every query by hand. There are six tables:

• department(dept_name, building, budget)
• instructor(inst_id, name, dept_name, salary)
• student(stu_id, name, dept_name, tot_cred)
• course(course_id, title, dept_name, credits)
• teaches(inst_id, course_id)
• takes(stu_id, course_id, grade)

This week we only need to look at the student table:

Gizem’s department is not known yet, so it is NULL. This row will be very useful in the SQL weeks.

Why a DBMS instead of a file system?

Before databases became common, organizations kept their data in operating system files. Each department wrote its own file and its own program. This is called a file-processing system. These are the problems of that approach that you are expected to list in the exam:

A DBMS gives a central solution to each of these problems. For example, integrity constraints are written once in the schema, and the DBMS checks them at every insertion:

INSERT INTO course VALUES ('CS999', 'Test', 'CS', 9);     -- credits must be 1..6
INSERT INTO student VALUES ('S9', 'Ilke', 'PHYS', 0);    -- there is no PHYS department
INSERT INTO student VALUES ('S1', 'Kopya', 'CS', 0);     -- S1 already exists

CHECK constraint failed: credits BETWEEN 1 AND 6
FOREIGN KEY constraint failed
UNIQUE constraint failed: student.stu_id

All three statements were rejected. No application program had to write these checks.

Data models

A data model is a collection of concepts used to describe data, the relationships between data, their meaning and constraints. The ones you will meet in this course:

• Relational model: Data is kept in tables (relations). Today it is the most common model and the center of the course. Details in week 3.
• Entity-relationship model (ER): A model used in the design phase that thinks in terms of entities and the relationships between them. Week 2.
• Object-based model: Brings ideas such as inheritance and encapsulation from object-oriented programming to data.
• Semi-structured model: Records of the same kind may have different fields. JSON and XML are examples.
• Historically there were also the network and hierarchical models, which are rare today.

Schema and instance

An analogy from programming: the schema is like the type definition of a variable, and the instance is like the current value of that variable.

• student(stu_id, name, dept_name, tot_cred) is a schema. Column names, types, keys, constraints.
• The 7-row table above is the current instance.

When you add a row, the instance changes and the schema stays the same. In the verification run, the row count went from 7 to 8 after the INSERT, and the column count stayed at 4. Changing the schema requires a DDL command such as ALTER TABLE, and that is done rarely.

PITFALL · “schema” is used in two senses. Sometimes it means the structure of a single table (relation schema), sometimes the design of the whole database (database schema). Work it out from the context in the exam. In both cases the opposite term is “instance”.

Three-schema architecture and data independence

To protect the user from details, a DBMS describes data at three levels of abstraction:

   external (view) level     advisor screen   |  accounting screen   |  ...
              |                 (each user group sees a part of the data)
   logical (conceptual) level   all tables, columns, relationships, constraints
              |
   physical (internal) level    files, blocks, indexes, record layout

• Physical level: How is the data stored on disk? A heap file or a sorted file? Which column has a B+ tree?
• Logical level: What data exists and how is it related? The student, course and takes tables and their constraints. The DBA and the designer work at this level.
• External (view) level: The part a particular user sees. For example, an advisor sees only a student’s name and department, not the grades.

Thanks to the mappings between levels, a change at one level does not break the level above it. This is called data independence.

We actually ran both examples. Before the index was added, the SQLite query plan scanned the whole table; afterwards it used the index, but the result rows stayed the same:

SELECT name FROM student WHERE tot_cred > 40
plan before: SCAN student
plan after : SEARCH student USING INDEX idx_cred (tot_cred>?)
result (in both cases): Ada, Cem, Defne

For logical independence, the student table was split into student_core and student_credit, and then a view named student was defined that joins the two. The old query, without any change, gave the same result:

CREATE VIEW student AS
  SELECT c.stu_id, c.name, c.dept_name, k.tot_cred
  FROM student_core c JOIN student_credit k USING (stu_id);

SELECT name FROM student WHERE dept_name = 'CS';

Ada
Bora
Ece

PITFALL · which one is harder? Achieving logical data independence is harder than achieving physical independence. Applications depend directly on table and column names. If you drop a column, no view can bring it back.

Database languages: DDL and DML

SQL is one language, but its commands fall into two groups:

The output of DDL is stored in the data dictionary. This is a special collection of tables that holds “data about data” (metadata). The DBMS looks there before every query.

DML can be of two styles. In procedural DML, you tell the system step by step “how to find the data”. In declarative DML, you say only “what you want”, and the DBMS decides how to find it. SQL is declarative:

SELECT stu_id, name FROM student WHERE tot_cred > 40;

S1 | Ada
S3 | Cem
S4 | Defne

In this query we did not say which index to use or in what order to read the rows. The query processor chose that. Weeks 12 and 13 explain exactly how that choice is made.

Transactions and ACID

A transaction is a sequence of operations that counts logically as a single unit of work. The classic example is a money transfer: take from A, add to B. Both must happen together. The DBMS makes four promises for each transaction:

We tried atomicity in SQLite. The accounts are A = 500, B = 200 and the constraint is balance >= 0. The transaction first adds 700 to B, then tries to subtract 700 from A:

BEGIN
UPDATE account SET balance = balance + 700 WHERE acc = 'B'   -- succeeded, B = 900
UPDATE account SET balance = balance - 700 WHERE acc = 'A'   -- CHECK error (A would be -200)
ROLLBACK
result: A = 500, B = 200

Although the first UPDATE succeeded, ROLLBACK undid it too. A valid transfer of 300, on the other hand, completed with COMMIT: A = 200, B = 500, and the total of 700 was preserved.

Users and the parts of a DBMS

Four kinds of people talk to a database:

• Naive user: Uses ready-made interfaces. A student who picks a course on the registration page.
• Application programmer: Writes those interfaces. Calls SQL from inside a program.
• Sophisticated user: Writes queries directly or uses analysis tools. A data analyst.
• Database administrator (DBA): Defines the schema, chooses the physical layout and indexes, grants permissions, takes backups, monitors performance.

Inside the DBMS there are three main parts. The storage manager writes data to and reads it from disk and handles buffer management. The query processor parses the SQL, chooses the cheapest plan and runs it. The transaction manager provides ACID through concurrency control and crash recovery.

Common mistakes