Rules for functional dependencies

You'll get far with these, but they can also be derived to:

So what can these rules be used for?

Closure of a set of functional dependencies

We have a set of functional dependencies F. The closure of F is a set of functional dependencies F' that are logically implied by F. In more human terms, it is the set of all possible functional dependencies that can be derived from the functional dependencies of F using the rules specified above.

As well as finding the closure of a set of functional dependencies, you might want to work out the closure of just one or more attributes, using the set F. (This is the set of all things you can know, knowing only the values of this or these attributes). The algorithm can be described with the following steps:

1. Start with a set $S$, the attributes that you want to find the closure of.
2. For the set $F$ of functional dependencies, look at each functional dependency and see if you have all the left-hand side attributes in $S$. If so, add all the right-hand side attributes of this particular functional dependency to a set of new attributes, $N$.
3. Now, $S = S \cup N$
4. If $N$ was empty, you have found all possible attributes that can be known from the initial $S$. If $N$ was not empty, repeat from step 2 – there might still be territory to explore.

Equivalent functional dependencies

Two sets of functional dependencies A and B are said to be equivalent if the closures of their sets of functional dependencies are the same. However, you'll not want to do this by hand on your exam (unless you possess the ability to travel back through time).

The quick and easy way is to see if you can apply the rules above to derive A from B as well as B from A. If you're able to derive every functional dependency in each set from the other, they are functionally equivalent.

Nonadditive join test for a binary decomposition

A binary decomposition is a decomposition of one relation into two (and only two) relations. As mentioned above, a nonadditive (or lossless) join is a join in which no additional tuples are generated. (In other words, this is really a test for whether it is possible to generate the original table from the two new)

$F^{+}$ is the closure of the functional dependencies of the original relation $R$, which has been decomposed into the two relations $R_{1}$ and $R_{2}$ – a binary decomposition. The binary decomposition has the lossless join property if either:

• The functional dependency $((R_{1} \cap R_{2}) \rightarrow (R_{1} - R_{2}))$ is in $F^{+}$, or
• The functional dependency $((R_{1} \cap R_{2}) \rightarrow (R_{2} - R_{1}))$ is in $F^{+}$.

Hashing schemes

B+ trees

A B+-tree is a storage structure that is constructed as an $n$-ary tree. We expect that you already have some basic knowledge about trees. In the tree, each node (including leaves) corresponds to one disk block.

Recoverability of a schedule

All schedules can be grouped into either nonrecoverable or recoverable schedules. A schedule is recoverable if it is never necessary to roll back a transaction that has been committed. In the group of recoverable schedules, we have a subgroup: Schedules that Avoid Cascading Aborts (ACA), and this again has a subgroup: Strict schedules.

$$ Recoverable \supset ACA \supset Strict $$

Here are the different levels of recoverability:

Serializability of a schedule

Ideally, every transaction should be executed from start to end (commit or abort) without any other transactions active (a serial schedule). However, this is a luxury we cannot afford when working with databases, mainly because a transaction spends a lot of time waiting for data being read from the disk. Therefore, transactions are executed in an interleaved fashion: When there is available time, another transaction jumps in and does some of the work it wants to do.

It is apparent that interleaving operations introduce some new problems. For instance: $A$ is your bank account. Transaction $T_1$ reads the amount in $A$ and adds 500 dollars while $T_2$ reads the amount in the account and adds interest (i.e. multiplies the value by some number). As you can imagine, reordering the operations might affect the end result (if $T_2$ reads while $T_1$ prepares to add the 500 dollars, the result of $T_1$ will be forgotten when $T_2$ writes its values). If we can interleave the operations so that the end result is guaranteed to be the same as if they execute in a serial way, the schedule is called serializable.

In short:

This course only looks at conflict serializability. If you are interested in what this actually means, consult the book; you only have to be able to test for conflict serializability to pass this course. The best test for conflict serializability is constructing a precedence graph.

Before looking at the precedence graph, it is necessary to define the concept of a conflict between transactions. Two operations are in conflict if all of these criteria are met:

1. They belong to different transactions.
2. They access the same item X.
3. At least one of them is a write operation.

For a schedule $S$, the precedence graph is constructed with the following steps:

1. For each transaction $T_{i}$ in $S$, draw a node and label it with its transaction number.
2. Go through the schedule and find all conflicts (see criteria above). For each conflict, draw an edge in the graph, going from the transaction that accessed the item first to the transaction that accessed the item last in the conflict.

If there are no cycles in the graph, the schedule is conflict serializable.

The isolation levels of SQL

SQL has different isolation levels that are used to combat these problems, each employing some of the techniques described in other parts of this article. What you should be concerned with are what problems might appear when using the different isolation levels. In MySQL, the Serializable level is default.

Two-phase locking (2PL) protocols

A lock is a variable associated with a data item. A lock is basically a transaction's way of saying to other transactions "I'm reading this data item; don't touch" or "I'm writing to this data; don't even look at it".

By making sure that the locking operations occur in two phases, we can guarantee serializable schedules, and thus we get two-phase locking protocols. The two phases are 1. Expanding (growing): New locks on items can be acquired but none can be released. (If the variation allows, locks can also be upgraded, which means converting a read lock to a write lock.) 2. Shrinking: Existing locks can be released. No new locks can be acquired. If the variation allows, locks can be downgraded from write-locks to read locks.)

Problems that may occur in two-phase locking

Deadlock: A deadlock occurs when each transaction $T$ in a set $S$ of two or more transaction are waiting for some item that is locked by some other transaction $T'$ in the same set; the transactions all hold some item hostage, and are not willing to let go until they get what they need to continue.

Ways to deal with it:

• Conservative 2PL: This requires every transaction to lock all the items it needs in advance. This avoids deadlock.
• Deadlock detection: This can be done with the system making and maintaining a wait-for graph, where each node represents an executing transaction. If a transaction T has to wait, it creates a directed edge to the transaction it's waiting for. There's a deadlock if the graph has a cycle. A challenge is for the system to know when to check for the cycle. This can be solved by checking every time an edge is added, but this may cause a big overhead, so you may want to also use some other criteria, eg. checking when you go above a certain number of executing transactions.
• Timeouts: This requires that a transaction gets a time to live beforehand. If it has not finished executing within that time, it is killed off. This is simple and has a small overhead, but it may be hard to estimate how long a transaction will take to finish. This may result in transactions being killed off needlessly.

The last two are the most used, but there are also two other schemes based on a transaction timestamp TS(T), usually the time the execution started. We have two transactions A and B. B has locked an item, and A wants access:

• Wait-die: A gets to wait if it's older than B, else it restarts later with the same timestamp
• Wound-wait: If A is older, then we abort B (A wounds B) and restart it later with the same timestamp. Otherwise, A is allowed to wait.

Two methods that don't use timestamps have been proposed to eliminate unnecessary aborts:

• No Waiting (NW): Transaction that cannot obtain a lock are aborted and restarted after a time delay
• Cautious waiting: If $T_{B}$ is not waiting for some item, then $T_{A}$ is allowed to wait. Else abort $T_{A}$.

Starvation: This occurs when a transaction cannot proceed for an indefinite period of time, while other transactions can operate normally. This may happen when the waiting scheme gives priority to some transactions over others. Use a fair waiting scheme, eg. first-come-first-serve or increase priority with waiting time, and this won't be a problem.

High-level overview

Recovery algorithm designed to work with a no-force, steal database approach. ARIES has three main principles:

Two datastructures must be maintained to gather enough information for logging: the dirty page table (DPT) and the transaction table (TT):

ARIES periodically saves the DPT and the TT to the log file, creating checkpoints (list of active transactions), to avoid rescanning the entire log file in the case of a redo. This allows for skipping blocks that are not in the DPT, or that are in the DPT but have a recLSN that is greater than the logg post LSN.

In case of a crash ARIES has three steps to restore the database state:

1. Analysis: Identifies dirty pages in the buffer, and the set of transactions active at the time of the crash.
2. Redo: Reapplies updates from the log to the database from the point determined by analysis.
3. Undo: The log is scanned backward and the operations of transactions that were active at the time of the crash are undone in reverse order.

In-depth explanation

Simple select example with conditions

SELECT attributes you want, use commas to separate
FROM where you want this to happen
WHERE condition;

For instance

SELECT s.name, s.address
FROM Student AS s, Institute AS i
WHERE s.instituteID = i.ID AND i.name = "IDI";

Queries with grouped results

SELECT attributes you want, use commas to separate
FROM where you want this to happen
GROUP BY attribute you want it grouped by
HAVING some condition for the group;

You may add this after having if you want the groups sorted.

ORDER BY some_attribute DESC/ASC;

You can also run a regular WHERE-statement and GROUP BY some attribute. Example:

SELECT Item.name, Item.price, Item.type
FROM Item
WHERE price > 200; 
GROUP BY type
HAVING SUM(Item.price) > 2000;

Alter a table

Add an attribute

ALTER TABLE table_name
ADD new_attribute_name DATATYPE(length) DEFAULT default_value;

Remove an attribute

ALTER TABLE table_name DROP attribute_name;

Insert new entry

INSERT INTO table_name (column1,column2,column3,...)
VALUES (value1,value2,value3,...);

Delete an entry

DELETE FROM where you want this to happen
WHERE condition;

Update an entry

UPDATE table you want to update
SET new values
WHERE condition;

For instance

UPDATE Pricelist
SET price = 20
WHERE price > 20 AND type = "Beer";

Views

A view is a statement that defines a table, but not actually creating a table. In other words, it's a new table composed of data from other tables. Views are often used to simplify queries and for multi-user control. To create a view write a statement on the form:

CREATE VIEW viewName AS (statement);

For instance:

CREATE VIEW IDI_Students AS(
    SELECT s.name
    FROM Student AS s, Institute AS i
    WHERE s.instituteID = i.ID AND i.name = "IDI"
);

Some views may be updated, some may not. There are two standards:

• SQL-92, the one that most implementations use. Very restrictive regarding updating views, and only allows updating views that use projection or selection.
• SQL-99 is an extension of SQL-92. Will update an attribute in a view if the attribute comes from a particular table and that the primary key is included in the view.

Aggregate Functions

Scalar functions

The sort-merge algorithm for external sorting

TL;DR:

• $b$: Blocks to be sorted.
• $n_{B}$: Available buffer blocks.
• $n_{R} = \lceil\frac{b}{n_{B}}\rceil$: Number of initial runs.
• $d_{m} = min(n_{B}-1, n_{R})$: Degree of merging.

Total number of disk accesses: $(2*b) + (2*b)*\log_{d{M}}(n_{R})$.

The long version: The sort-merge algorithm is the only external sorting algorithm covered in this course. The word external refers to the fact that the data is too large to be stored in main memory, and thus is stored on some external storage, such as a hard drive. The algorithm is very similar to the classic merge sort algorithm. We will look at the total number of disk accesses needed for the algorithm, as well as giving an explanation of why it is so.

Sort phase: We start with a file of size $b$ blocks. We have $n_{b}$ available buffers in main memory, each able to store one block from the disk. We read a portion of as many blocks as possible ($= n_{B}$) into the main buffers; each of these portions is called a run. Each run is sorted by some internal sorting algorithm, and the results are written to disk after sorting. The number of such initial runs is called $n_{R}$, and it is equal to the total size divided by total buffer space: $n_{R} = \lceil\frac{b}{n_{B}}\rceil$. Because each block has to be read from disk and then written back, the number of disk accesses needed for this phase is $2*b$, which we'll call $n_{SORT-PHASE}$.

Merge phase: When the algorithm has sorted each of the initial runs and written them to disk, it proceeds to a merge pass, which merges as many runs as possible. In this phase, one of the buffers has to be reserved for the result of the merging. The rest of the buffers are used to store the blocks that are to be merged. The computer reads the first blocks from $n_{B}-1$ runs into the buffers – unless we have fewer than $n_{B}-1$ initial runs, and in that case, $n_{R}$ blocks will be read into memory at a time. This number, the number of blocks being merged at a time, will be called the degree of merging, $d_{M}$. When the blocks have been read into memory, the computer proceeds to find the smallest number from each. When this has been found, it is removed from its buffer and put in the result buffer. When the result block is full, it is written to disk; when a buffer is empty, the next block from that sorted run is read into memory.

The number of merge passes: If we are not able to merge all runs in one merge pass, we might have to do another … and perhaps then another. If you've taken a course in either discrete mathematics or algorithms, you will recognize that this merge phase can be illustrated as a full $d_{M}$-ary tree – each leaf node being an initial run and each internal node the result of a merge. The height of any full $n$-ary tree is decided by the number of leaves (here, the initial runs), which you take the logarithm of, the logarithm having a base equal to the number of children each internal node can have. You'll probably see that this is the number of runs that can be merged in each phase, the degree of merging ($d_{M}$). Thus, the height of the merge tree will be $\log_{dM}(n_{R})$. Because each merge pass has to both read and write a number of blocks equal to the size of the initial file, each merge pass also takes $2*b$ disk accesses. Now, we are almost at the solution: $n_{MERGE-PHASE} = (2*b)*\log_dM(n_{R})$.

The total number of disk accesses is thus: $$n_{SORT-MERGE} = n_{SORT-PHASE} + n_{MERGE-PHASE} = $$ $$(2*b) + (2*b)*\log_{dM}(n_{R})$$