Databases (theory)

What a database system is and how it is built

Imagine a school that keeps every student's address in two places: the office writes it in one notebook and the cafeteria writes it in another. A student moves house, the office fixes its notebook, and the cafeteria forgets. Now the school has two different answers to the same question. Keeping the same fact in several places is called redundancy. When the copies stop agreeing, we have inconsistency.

A database system fixes this by putting the data in one integrated place, shared by everybody, and by putting a program in charge of it: the DBMS. Some redundancy may stay for speed, but then the DBMS itself takes care of updating every copy.

Three levels of description

The classic ANSI/SPARC architecture describes the same data in three levels, like three ways to look at a building: the floor plan, the photo from the street and the pipes inside the walls.

  user A view      user B view        EXTERNAL level
       |                |             (what each user sees)
       +--- mapping ----+
                |
        conceptual schema             CONCEPTUAL level
                |                (the whole data, logically)
          mapping
                |
         internal schema              INTERNAL level
                         (files, indexes, physical order)

• External level: the view of each user or program. Many different views can exist.
• Conceptual level: one common logical description of the whole database.
• Internal level: how the data is physically stored: stored record formats, indexes, physical order.
• Mappings translate between the levels, so that a change in one level can be absorbed without touching the others.

Data independence

Data independence means that programs are not broken when the way the data is stored or arranged changes. Without it, every program would know the exact file format and would stop working when someone changed it. There are two kinds:

Example of logical independence: the table EMP is split into EMP_PESSOAL and EMP_SALARIO. A view named EMP that joins the two tables lets old programs keep working. Queries are fully protected. Updates only work if the view is updatable, because not every change to a view can be translated in one clear way to the real tables. Creating an index, on the other hand, is a physical change: only the internal schema and the conceptual/internal mapping change.

Languages, catalog and people

• DDL (data definition language) describes the objects: CREATE TABLE is a DDL statement.
• DML (data manipulation language) works on the content: SELECT, INSERT, UPDATE, DELETE.
• The catalog holds the metadata, which is data about the data: tables, columns, constraints, users. In a relational system the catalog is itself made of tables, so you can query it with the same language you use for ordinary data.
• The data administrator (DA) decides which data the organisation keeps and the policies about it. The database administrator (DBA) is the technical person who implements those decisions: schemas, security, recovery and tuning.

The relational model: tables, keys and integrity

A class list on paper has a title row (name, number, grade) and one line for each student. The relational model turns that picture into precise words. A relation is the table. Its heading is the set of column names, called attributes. Its body is the set of rows, called tuples. The degree is how many attributes there are, and the cardinality is how many tuples there are right now.

Because a relation is built from sets, it has four properties: no two tuples are equal, tuples have no order, attributes have no order, and each attribute holds one single value in each tuple. A table on paper is only a picture of a relation, and the order in which you see the rows means nothing. Each attribute is declared over a domain, which is the same as a data type: the set of values it may take.

A small but important point from Date: a relation value never changes, just like the number 5 never changes. What changes is the variable that holds the value. That variable is called a relvar (relation variable). When people say 'updating a relation', they really mean putting a new value into a relvar.

Keys

How do we tell students apart when two share a name? With a key. A superkey is any set of attributes whose values are unique in every tuple. A candidate key is a superkey with nothing to spare: if you remove any attribute, it stops being unique. A relation can have several candidate keys. One is picked as the primary key, and the others are the alternate keys.

Counting trick: every superkey is a set that contains some candidate key. If MATRICULA(aluno, disciplina, nota) has the single candidate key {aluno, disciplina}, the only free attribute is nota. You may add it or not, so there are exactly 2 superkeys: {aluno, disciplina} and {aluno, disciplina, nota}.

Every relation has at least one candidate key. The reason: there are no duplicate tuples, so the set of all attributes is always unique, and removing unnecessary attributes from it leaves a candidate key. SQL tables that accept duplicate rows lose this guarantee.

Integrity rules

• Entity integrity: no component of the primary key of a base relation may be null. Otherwise there would be a recorded thing with no known identity.
• Referential integrity: a foreign key is a set of attributes whose values must match a candidate key of another relation, or of the same relation. Every non-null foreign key value must exist as a value of the referenced key. The rule is checked when inserting into the referencing relation and when deleting or changing the referenced tuple.
• A foreign key may point to its own relation. In EMP(eno, nome, gerente_eno), the attribute gerente_eno can reference eno of EMP itself: the manager is an employee too.

When a referenced row is deleted, a referential action says what the DBMS does with the rows that point to it:

CREATE TABLE emp (
	eno CHAR(3) PRIMARY KEY,
	dno CHAR(2) NOT NULL
		REFERENCES dept (dno) ON DELETE CASCADE
);
-- DELETE FROM dept WHERE dno = 'D1'
-- also deletes every employee of D1 (CASCADE).
-- RESTRICT / NO ACTION would refuse; SET NULL / SET DEFAULT
-- would change the foreign key instead.

Constraints by scope, and the missing value

Date sorts integrity constraints by how much must be examined to check them: a type constraint looks at one value, an attribute constraint at the type of one attribute, a relation variable constraint at one relvar, and a database constraint at two or more relvars. 'The salary of an employee cannot be greater than the budget of their department' mentions EMP and DEPT, so it is a database constraint. Referential integrity is the best-known database constraint.

Sometimes a value is unknown. SQL marks it with NULL, and uses three-valued logic: a condition can be true, false or unknown. Any comparison with NULL is unknown, and WHERE keeps only the rows where the condition is true.

Designing before building: entities and relationships

Before building a house you draw a plan. Before building a database you also draw a plan, and the most famous one is the entity-relationship (E/R) diagram. An entity is a thing we want to remember (a student, a course). A relationship connects entities (a student takes a course). Both can have attributes.

In Chen's original notation, rectangles are entities, diamonds are relationships and ellipses are attributes. The lines are labelled with the cardinality (1 or M).

+--------------+          /\          +-----------+
| DEPARTAMENTO |--1----- <  > ---M--| EMPREGADO |
+--------------+          \/          +-----------+
                         tem

rectangle = entity    diamond = relationship

Cardinality

The cardinality of a relationship says how many occurrences of one entity connect to one occurrence of the other. To find it, read the relationship in both directions: how many employees does a department have? Many. How many departments does an employee have? One. So the relationship is one-to-many. The three kinds are one-to-one, one-to-many and many-to-many.

Why a third table for many-to-many? A foreign key holds one single value, so it can only point to the 'one' side. A student takes many courses and a course has many students, so neither table can hold the link. The new table is called an associative relation. In the 'one' side nothing is stored: to find the employees of a department you query EMPREGADO by its foreign key.

Relationships can have attributes of their own, when a fact only makes sense for the pair. The grade nota belongs to the relationship MATRICULA, not to the student or to the course alone, because {aluno, disciplina} determines it and neither one alone does.

Weak entities and subtypes

• A weak entity depends on another entity for its existence. If the owner goes, the weak one goes too. The dependants of an employee, or the lines of an order, are examples. In tables, the key of the weak entity usually includes the key of the owner.
• In the extended E/R model, a supertype and its subtypes express 'is a'. Every ENGENHEIRO is an EMPREGADO, and inherits its attributes. A common design is one table for the supertype and one for each subtype, where the primary key of the subtype is also a foreign key to the supertype.

The ternary trap

A ternary relationship links three entities in one fact: 'supplier F delivers part P to project J'. It is tempting to replace it with three binary relationships (supplier-part, part-project, project-supplier). But three weaker facts do not add up to the one strong fact: joining them can invent combinations that never happened. This mistake is the connection trap. The replacement is safe only when the ternary table satisfies a join dependency on its three projections, which is the subject of fifth normal form.

Relational algebra: calculating with tables

In arithmetic you take numbers and make new numbers with + and ×. In relational algebra you take relations (tables) and make new relations with operators. The important rule is closure: the result of every operator is again a relation. That is why you can plug operators into each other, like a projection of a selection of a join.

Selection and projection

FORNECEDOR            pi cidade (FORNECEDOR)
fno | cidade           cidade
F1  | Lisboa    --->  Lisboa
F2  | Porto           Porto
F3  | Lisboa           Faro
F4  | Faro
F5  | Porto         3 tuples, not 5

Selection cuts rows, projection cuts columns. Projection can make different tuples equal, and since a relation is a set, the repeated ones are shown once. SQL differs: it keeps repeated rows unless you write DISTINCT.

Union, intersection and difference

These come from set theory, but the result must still be a relation. So both inputs must have the same heading (same attributes and types). This is called union compatibility. Uniting suppliers with parts would give tuples of different shapes.

Difference answers 'in A and not in B'. With A = {1, 2, 3, 4} and B = {3, 4, 5}, A − B = {1, 2}. Unlike union and intersection, it is not commutative: B − A = {5}. Intersection is not even primitive: A ∩ B = A − (A − B).

Product and join

The Cartesian product R × S pairs each tuple of R with each tuple of S. Each result tuple is the two glued together, so the degree is the sum of the degrees and the cardinality is the product of the cardinalities. If R has degree 3 and 4 tuples, and S has degree 2 and 5 tuples, the product has degree 5 and 20 tuples.

The natural join keeps only the pairs that agree on the common attributes, and writes the common attribute once. Tuples without a partner disappear.

EMP            DEPT              EMP join DEPT
eno dno        dno cidade        eno dno cidade
E1  D1        D1  Lima          E1  D1  Lima
E2  D1        D2  Quito         E2  D1  Lima
E3  D2        D4  Bogota        E3  D2  Quito
E4  D3

E4 looks for D3: no match.   Nobody looks for D4.
Result: 3 tuples.

Two extreme cases show that product and intersection are special cases of join. With no common attribute, every pair is accepted, so the join is the Cartesian product. With all attributes in common, only identical tuples pair up, so the join is the intersection R ∩ S.

Division

Division answers 'for all' questions: which suppliers supply every part in P? FP ÷ P returns the fno values that appear in FP together with each pno in P. Extra parts do not matter. One missing part removes the supplier.

FP            P        FP / P
fno pno       pno      fno
F1  P1        P1       F1   (has P1, P2)
F1  P2        P2       F2   (has P1, P2)
F1  P3
F2  P1        F3 has P2 and P3 but not P1: out
F2  P2
F3  P2
F3  P3

Laws that the optimiser loves

Selection decides each tuple by itself, so it distributes over union, intersection and difference. Projection distributes over union, but not over difference or intersection, because dropping attributes can make different tuples coincide. For example π A (R − S) is not always π A (R) − π A (S). Rules like these are what lets a DBMS rewrite a query into a faster equal one.

Calculus and SQL: saying what you want

There are two ways to ask a friend for a sandwich. You can give a recipe: 'take two slices, spread butter, add cheese'. Or you can describe the result: 'I want a sandwich with cheese'. Relational algebra is the recipe: operators applied step by step. Relational calculus is the description: it states a condition that the result tuples must satisfy, using predicate logic. The two are equivalent in power, so a DBMS can accept a description and turn it into algebra internally.

The two quantifiers are linked by negation: FORALL x (p) is the same as NOT EXISTS x (NOT p). SQL has EXISTS and no FORALL, so a 'for all' query uses two negations. 'Students enrolled in ALL courses' becomes: students for whom there is no course in which they are not enrolled.

SELECT a.nome FROM aluno a
WHERE NOT EXISTS (
	SELECT * FROM disciplina d
	WHERE NOT EXISTS (
		SELECT * FROM matricula m
		WHERE m.aid = a.aid AND m.did = d.did));

The order SQL really thinks in

You write SELECT first, but the DBMS thinks in another order: FROM builds the rows, WHERE throws away rows, GROUP BY makes groups, HAVING throws away groups, and only then the SELECT list is computed. So WHERE filters rows and HAVING filters groups.

-- pedido(cliente, valor): (A,10) (A,30) (B,50)
--                       (C,5)  (C,5)  (C,15)
SELECT cliente
FROM pedido
GROUP BY cliente
HAVING SUM(valor) > 30;
-- A: 40, B: 50, C: 25  ->  A and B

Where SQL departs from the model

• Bags, not sets. A table of 5 suppliers in 3 cities gives 5 rows for SELECT cidade FROM fornecedor. Repeats go away only with SELECT DISTINCT.
• Aggregates skip NULL. SUM, AVG, MAX, MIN and COUNT(column) ignore nulls. Only COUNT(*) counts rows. For bonuses 10, 20, NULL, 30, AVG(bonus) is 20 (three values), not 15.
• NOT IN and NULL. x NOT IN (list) means x <> v1 AND x <> v2 AND .... If the list contains a NULL, one term is always unknown, the whole condition is never true, and the query returns no rows. Use NOT EXISTS, or filter the nulls out of the subquery.

Views

A view is a virtual table: the catalog stores only the query that defines it. When you query the view, the DBMS replaces its name with the definition. So a view always shows the current data: if a new product with price 500 is inserted, the view caros (products above 100) shows it at once.

Updating through a view is harder. A row of a view that averages salaries by department summarises many emp rows, so UPDATE media_depto SET media = 5000 has no single translation to the base rows, and the DBMS rejects it.

Relational completeness

A language is relationally complete when it can express every query that relational calculus can. Algebra and calculus both meet this minimum, and SQL does too. It is only a minimum: recursive questions, like 'all the components of a part at any depth', are outside it.

Functional dependencies and normal forms

Look at a table that stores, in every line, the order, the product, the quantity and also the product name. The name of product 7 is written again in every line that mentions product 7. That wastes space, and worse, when the name changes you must fix many lines. Normalisation is the cure: split the table so each fact is written once.

Functional dependency

A functional dependency X → Y holds when two tuples that agree on X always agree on Y. X is the determinant. Like a zip code that determines the city: same zip, same city. It is a rule about the meaning of the data, so it must hold in every valid value of the relation.

Valid inferences come from Armstrong's rules: reflexivity, augmentation and transitivity. You may split the right side freely (A → BC gives A → B and A → C). You may not shrink the left side: from AB → C you cannot conclude A → C, because that is a stronger claim that may be false.

Closure, keys and covers

The closure X+ is everything X determines. Start with X, then keep adding the right side of every dependency whose left side is already inside, until nothing changes. If X+ is the whole relation, X is a superkey.

F = { A -> B,  B -> C,  CD -> E }

{A}+ :  {A}  --A->B-->  {A,B}  --B->C-->  {A,B,C}
                                CD -> E needs D: stop

result: {A}+ = {A, B, C}

• An attribute that appears on no right side can never be derived, so it belongs to every candidate key. In R(A, B, C, D) with A → B and B → C, both A and D are such attributes, and {A, D}+ is everything, so {A, D} is the only candidate key.
• For R(A, B, C, D) with AB → C, C → D, D → A, the mandatory attribute is B. Trying the others gives three irreducible keys: {A, B}, {B, C} and {B, D}.
• A redundant dependency can be derived from the rest. In {A → B, B → C, A → C}, the dependency A → C goes away, because {A}+ without it already contains C. The cleaned set is called an irreducible (minimal) cover.

The ladder of normal forms

To find the highest normal form, climb from the bottom and stop at the first failure. ITEM meets 1NF but fails 2NF. A 1NF relation whose key has a single attribute is automatically in 2NF. For a transitive chain, decompose into EMP(eno, dno) and DEPT(dno, cidade_depto).

A relation that mixes two subjects suffers three anomalies. Insertion: you cannot record a supplier's city until it supplies a part. Deletion: erasing the last shipment of a supplier erases the city too. Modification: the same fact repeated in many rows must be changed in all of them.

3NF against BCNF

They differ only with composite candidate keys that overlap. Take AULA(aluno, disciplina, professor) with {aluno, disciplina} → professor and professor → disciplina. The keys are {aluno, disciplina} and {aluno, professor}. The dependency professor → disciplina has a non-key determinant but a prime (key) attribute on the right. 3NF tolerates that, BCNF does not. So AULA is in 3NF but not in BCNF.

AULA(aluno, disciplina, professor)
   aluno, disciplina -> professor     professor -> disciplina

BCNF:  R1(professor, disciplina)   R2(aluno, professor)
lossless: yes
lost:     aluno, disciplina -> professor (spans two tables)

A good decomposition is lossless (joining the pieces gives back exactly the original, with no invented tuples) and dependency preserving (each dependency can be checked inside one piece). A decomposition to 3NF with both qualities always exists. To BCNF a lossless one always exists, but a dependency may be lost. Heath's theorem gives a safe case: if R(A, B, C) satisfies A → B, then R(A, B) and R(A, C) join back to R.

Higher forms: 4NF and 5NF

Some redundancy has no functional dependency behind it. In OFERTA(curso, professor, livro), the teachers of a course and the books of a course are independent, so every teacher must be listed with every book. This is a multivalued dependency curso →→ professor. The relation is in BCNF, because the only key is all three attributes, but it is not in 4NF. The fix is two tables: curso, professor and curso, livro.

A join dependency says a relation can be rebuilt by joining some projections. With two projections it is the same as a multivalued dependency. Some relations only decompose losslessly into three or more pieces, and 5NF (projection-join normal form) handles those. It is the last form when only projection and join are used.

Making queries fast: optimiser and indexes

When you ask a taxi to go to the airport, you do not choose the streets. A SQL query is the same: it says what you want, not how to find it. Inside the DBMS, the query optimiser is the driver who picks the route. It rewrites the query into equal ones, lists the possible ways to run it (read the whole table, use an index, which join method), estimates the cost of each with the statistics in the catalog, and picks a cheap plan. This automatic choice is what makes data independence practical.

Do the cutting first

The best-known trick: apply selections as early as possible, and projections too. If you join two large tables and only then keep one city, the join works on everything. If you keep the city first, the join receives far fewer rows. The two plans give the same answer because of the algebra laws, but not the same cost.

slow plan                   fast plan

  select city = X             join
       |                     /    \
     join              select      \
    /    \             city = X     \
  R        S              |          S
                          R

Indexes

An index is the list at the back of a book: it leads from a value to the pages where it appears. Searches become faster, but every insert, update or delete must also fix the index, and the index takes space. That is the trade-off: faster search, slower update. So you index columns that are searched a lot and changed little.

Three ways to join

With 1,000 rows in R and 10,000 in S, the nested loop makes 1,000 × 10,000 = 10,000,000 comparisons. Hash does about 1,000 + 10,000 = 11,000 steps. A join with R.a < S.b is not an equality, so hash does not apply, but the nested loop still works. The optimiser must know which algorithms are possible before it compares costs.

The mini-project Mini relational DBMS measured it: ten times more rows cost the nested loop about 80 times more time (the theory says 100), while hash and sort-merge grow almost in a straight line. The numbers depend on the machine recorded in the project results.

Transactions and recovery

Sending 100 reais from Ana to Bia takes two steps: take 100 from Ana, add 100 to Bia. If the lights go out between the two steps, 100 reais vanish. A transaction is a box around the steps: a logical unit of work that takes the database from one correct state to another correct state. Either everything inside the box happens, or nothing does.

COMMIT and ROLLBACK

• COMMIT says 'success': the updates become permanent.
• ROLLBACK says 'failure': the DBMS undoes every update since the transaction began, using the old values kept in the log, and the transaction ends.
• After either one, the locks are released and a new transaction may begin.

ACID

The log and the write-ahead rule

The log (or journal) is a sequential file where the DBMS writes the start and the end of each transaction and, for each update, the value before and after. It is the base of all recovery. The write-ahead log rule says the log record always goes to disk before the changed data page does. Before a page is written, the old value is already logged (so it can be undone). Before COMMIT finishes, all the records are on disk (so it can be redone).

The buffer manager has two freedoms. It may write pages of a transaction that has not committed (to free memory): the disk may hold changes to undo. And it is not forced to write pages at COMMIT: the disk may lack committed changes, which must be redone. Most systems use both freedoms, so they need both undo and redo.

Restart after a crash

A checkpoint is a moment when all changed pages are written to disk. At restart, the DBMS reads the log from the last checkpoint and builds two lists: transactions that committed after the checkpoint go to redo, those with no COMMIT up to the crash go to undo. Transactions that finished before the checkpoint are left alone.

                 tc (checkpoint)          tf (crash)
T1  |------|      |                   |   ended before tc: nothing
T2       |--------|--------|          |   COMMIT after tc: REDO
T3           |----|-------------------|   no COMMIT:       UNDO
T4                |   |---------|      |   COMMIT after tc: REDO
T5                |          |---------|   no COMMIT:       UNDO

A system failure loses memory but the disk database remains, so recovery undoes and redoes from the checkpoint. A media failure destroys the disk itself. Then recovery restores the last backup and redoes, from the log, the transactions committed after it. That is why the log lives on a different device from the database.

Two-phase commit

When one transaction changes data in two systems, each with its own log, a separate COMMIT in each could succeed in one and fail in the other. In two-phase commit, a coordinator first asks everyone to prepare and vote. If all say yes, it decides commit. One no makes the decision rollback. Then it announces the decision.

Many users at once: locks and isolation

Two children try to write on the same line of one notebook at the same moment. Without a rule, one of them erases the other's words. A database has thousands of users, so it needs rules for sharing. The classic accident is the lost update.

saldo = 100

T1 (+10)                T2 (+20)
READ saldo  -> 100
                        READ saldo  -> 100
WRITE saldo <- 110
                        WRITE saldo <- 120
COMMIT
                        COMMIT

saldo = 120   (should be 130: the +10 was lost)

Locks

A lock is a sign on the door: 'in use'. A shared lock (S) is taken to read, and many can hold it together. An exclusive lock (X) is taken to change, and it allows nobody else. If a request is incompatible with a lock another transaction holds, the requester waits.

Deadlock

Locks create a new danger: two children each hold one pencil and each waits for the other's pencil. A deadlock is a cycle of transactions in which each waits for a lock of the next. The DBMS draws a wait-for graph (an arrow Ti → Tj means Ti waits for Tj). A cycle means deadlock. It picks one transaction of the cycle as the victim and rolls it back, which frees its locks.

T4 ---> T1 ---> T2
        ^        |
        |        v
        +------ T3

cycle: T1 -> T2 -> T3 -> T1   (T4 only waits)

Serializability and two-phase locking

An interleaved execution is serializable when its result equals the result of some serial execution (one transaction after the other). Each transaction is correct alone, so any serial order is correct. Different serial orders may give different results, and all are accepted.

To test it, build a precedence graph: an arrow Ti → Tj when an operation of Ti comes before a conflicting operation of Tj on the same item (at least one is a write). The execution is serializable if and only if the graph has no cycle. In r1(A) w1(A) r2(A) w2(A) r2(B) w2(B) r1(B) w1(B), w1(A) before r2(A) gives T1 → T2, and w2(B) before r1(B) gives T2 → T1. A cycle, so it is not serializable.

Two-phase locking (2PL) is the rule that guarantees serializability. A transaction has a growing phase, where it only takes locks, and then a shrinking phase, where it only releases them. After the first release it may never lock again. So lock(A), unlock(A), lock(B), unlock(B) breaks the protocol, while lock(A), lock(B), unlock(A), unlock(B) obeys it.

Isolation levels

Full isolation costs speed, so the SQL standard offers four levels defined by the phenomena they allow. A dirty read reads data from a transaction that has not committed. A nonrepeatable read reads a row twice and finds it changed or removed by another transaction. A phantom runs the same condition twice and finds a new row that another transaction inserted.

Protecting the rows you read does not protect against rows that did not exist yet. Phantoms need locking the condition or range, which SERIALIZABLE provides.

Intent locks

Locks can be on a whole table or on single rows. Before locking a row, a transaction takes an intent lock on the table: IS to read rows, IX to change rows. Then a request to lock the whole table is decided by looking only at the table locks. IS and IX coexist with each other, S coexists with IS, and X coexists with nothing. So if T1 holds IX on emp, a request by T2 for S on the whole table waits.

Security and integrity: who may do what, and what is valid

A school has two kinds of protection. The door guard asks 'are you allowed to come in?'. The teacher who checks homework asks 'is what you wrote correct?'. A database has the same two. Security protects against unauthorised users. Integrity protects against mistakes by authorised users. Both work the same way: the rules are declared to the DBMS, kept in the catalog and checked at each operation.

Integrity rules were explained earlier (keys, foreign keys and constraints). A user with every permission can still type a wrong salary, and it is integrity that rejects it. Disk failures and power cuts are neither: they belong to recovery.

Discretionary control: GRANT and REVOKE

In discretionary access control, users have privileges (query, insert, change, remove) on objects, and privileges are given with GRANT and taken away with REVOKE. This is the scheme of SQL. With WITH GRANT OPTION, the receiver may pass the privilege on, which forms a chain.

-- DBA:
GRANT SELECT ON emp TO ana WITH GRANT OPTION;
-- ana:
GRANT SELECT ON emp TO bruno;
-- DBA:
REVOKE SELECT ON emp FROM ana CASCADE;
-- bruno loses it too: his privilege came only from ana

In standard SQL, CASCADE also revokes the privileges derived from the one you remove, and RESTRICT refuses the operation if derived privileges exist. A privilege survives only if some other grant still supports it.

Mandatory control

In mandatory access control each data item has a classification level and each user has a clearance level, and fixed rules decide, not the owner. The Bell-LaPadula model protects secrecy with two rules. With levels Public < Confidential < Secret < Top Secret, a user with Secret clearance:

• may read items classified Secret or lower (the simple security property: no reading above your clearance);
• may write only at Secret or higher (the star property: no writing below your clearance), so a program cannot copy a secret item, even by accident, to a place readable by users with lower clearance.

Putting it all together

A database system is a story with a clear order. We describe the data (levels and the relational model), we draw a plan (E/R), we ask questions (algebra, calculus, SQL), we clean the design (functional dependencies and normal forms), we make it fast (optimiser and indexes), and we keep it safe and correct (transactions, concurrency, security, integrity).

Mistakes that catch many students

• Believing a relation keeps rows in insertion order. It does not: a relation is a set.
• Calling something a key because today's rows do not repeat. A key is a rule about the meaning of the data.
• Expecting SELECT to remove duplicates. SQL tables are bags, so use DISTINCT.
• Selecting with a not-equal condition when the question is 'has no': that needs difference or NOT EXISTS.
• Forgetting that NULL makes comparisons unknown, so NOT IN with a null in the list returns nothing and AVG ignores nulls.
• Thinking BCNF is always better. It removes more redundancy, but may lose a dependency, which 3NF always keeps.
• Mixing up security (who) with integrity (what is valid), and both with recovery (failures).
• Believing an index is free. It speeds searches and slows updates.