TDT4145: Data Modelling and Database Systems
# Introdcution: Terms and expressions
|| Database || A database is a collection of data. ||
|| Data || Facts that can be recorded and that have an implicit meaning ||
|| Miniworld or Universe of Discourse (UoD) || A database represents a part of the real world, and we call this part a miniworld or UoD. Changes in the real world is reflected in the database.||
|| Database model ||A type of data model that determines the logical structure of a database. A database model can be represented in many different ways, eg. through an [ER-model](#entity-relationship-model). ||
|| Database management System (DBMS) || A collection of programs that allows users to create and maintain a database.||
|| Database system || Refers collectively to the database, database model and the DBMS. ||
# Types of failures
A database system may fail, and there are different types of failures. Failures of type 1-4 are common, and the system is expected to automatically recover from these. Failures of type 5 and 6 are less common, and recovering from them can be a major undertaking.
1. A computer failure / crash
2. A transaction or system error
3. Local errors or exception conditions detected by the transaction
4. Concurrency control enforcement
5. Disk failure
6. Physical problems and catastrophes
# Database storage stuctures
Databases are typically stored on secondary (non-volatile) storage.
## List of storage structures
|| Heap file || The simplest storage structure: an unordered list of records. Records are inserted at the end of the heap file, giving O(1) insertion. Retrieval requires a linear search ( O(n) ), and is therefore quite inefficient for large values of n. Deleted records are only marked as deleted, and not actually removed. This is O(1) (in addition to the time it takes to retrieve a record to be deleted). Highly volatile heap-files must be re-structured often to prune away records that are marked as deleted. ||
|| Hash buckets || Hash functions directly calculate the page address of a record based on values in the record. A good hashing function has an even spread across the address space. When doing calculations on hash buckets (say, for an exam), it is safe to assume about a 60% fill rate. Ignoring collisions, hash buckets are O(1) for retrieval, insertion, modification and deletion. Hash buckets often suck for range retrieval. ||
|| B+-trees || A pretty good all-around, tree, storage structure. Usually safe to assume they are of height 3 or 4. Retrieval, insertion, modification and deletion is O(log n). Good for volatile data, as the index dynamically expands and contracts as the data set grows and shrinks. Less optimal for non-volatile/stable files - use ISAM for that. ||
|| ISAM || (Indexed Sequential Access Method) ||
## Hashing schemes
|| Extendible hashing || Extendible hashing treats a hash as a bit string, and uses a trie for bucket lookup. Re-hashing is done incrementally, one bucket at a time, as needed. Both LSB and MSB implementations are common. ||
|| Linear hashing || Linear hashing allows for expansion of the hash table one slot at a time, round-robin. ||
# Transactions
A transaction is a unit of work performed within a DBMS. They provide reliability and isolation. Transactions are "all or nothing", in the sense that the entire unit of work must complete without error, or have no effect at all.
## ACID: Atomicitiy, consistency, isolation and durability
Databases must conform to the ACID principles:
|| Atomicity || A unit of work cannot be split into smaller parts—a unit of work can either complete entirely, or fail entirely. ||
|| Consistency || A transaction always leaves the database in a valid state upon completion, with all data valid according to defined rules such as constraints, triggers, cascades etc. ||
|| Isolation || No transaction can interfere with another transaction. ||
|| Durability || When a transaction completes, it remains complete, even in the case of power loss, crashes etc. ||
A typical transaction follows the following lifecycle:
1. Begin the transaction
2. Execute a set of data manipulations/queries
3. If no errors occur, then commit the transaction and end it
4. If errors occur, then rollback the transaction and end it
## Protocols for concurrency control
Concurrency control protocols are sets of rules that guarantee serializability, which means that it guarantees that the transactions produces the same result as if they were executed serially without overlapping in time. 2PL (see below) is the only protocol that's a part of the curriculum.
### Two-phase locking protocls (2PL)
A lock is a varaible associated with a data item. It describes what operations that are allowed to be done to the data item.
A transaction is following the protocol if all locking operations precede the first unlock operation.
Two implementations of 2PL are binary and Shared/executive.
Some shared-exclusive implementations are:
#### Binary locks
A binary lock can have two states: locked or unlocked (1 or 0). If the lock on an item is 1, then that data item cannot be accesses by by a database operation. When a transaction starts to operate on an item it locks it. When it's done it unlocks the item again. If a transaction wants to do operations on a locked item it waits until it is unlocked.
Binary lock is not usually used, but it gets across the idea of the lock easiliy.
#### Shared/executive (or Read/Write) locks
Binary locks is too restrictive for database items as it only allows one transaction access at any time, which means transactions takes longer time. This gives us the multi-mode locks. Here there are three locking operations that can be done on a data item X: read_lock(X), write_lock(X) and unlock(X). This means there are three possible states for the data item: _read-locked_ (also called _share-locked_), _write-locked_ (also called _exclusive-locked_) and _unlocked_.
A transactions that follows the protocol can be divided into two phases:
1. Expanding, or growing: New locks on items can be acquired but none can be released.
2. Shrinking: Existing locks can be released, and no new locks can be aquired.
Upgrading means converting a lock from read to write, and downgrading a lock means changing it from write to read. If it's allowed, upgrading has to be done in the first phase and downgrading in the last phase.
##### Variations
||Basic 2PL || What's been described. Puts on locks when needed, but won't unlock any before it's finished putting locks on.||
||Conservative 2PL (aka static 2PL) ||requires a tranasaction to set all locks before the transaction begins. If it is unable to do so it aborts and attempts at a later point in time.||
||Strict 2PL || A transaction does not release any write locks until it has committed or aborted.||
||Rigorous 2PL ||A transaction T does not release any of its locks until after it commits or aborts||
##### Problems that may occur
###### Deadlock
This occurs when each transaction T in a set S of two or more transaction is waiting for some item that is locked by some other transaction $T^{a}$ in the same set S. Said more plainly: two or more transactions are waiting for each other to finish so they can continue, eg. A works on item X and wants to work on Y while B works on Y and wants to work on X.
Ways to deal with it:
- Conservative 2PL requires every transaction to lock all the items it needs in advance. This avoids deadlock.
- Avoid it with deadlock detection. This can for instance be done with the system making and maintaing 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. number of executing transactions.
- Timeouts. Simple, small overhead. May cause transactions to be killed when there's no deadlock.
_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.
Another two that are proposed (because too many aborts/restarts can cause more deadlocks) that doesn't use timestamps:
- 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 procees for an idefinite period of time, while other transactions can operate normally. This may happen when the waiting scheme gives priority of some transactions over others. Have a fair waiting scheme, eg. first-come-first-serve or increase priority with waiting time, and this won't be a problem.
## Caching/buffering Disk Blocks
Disk pages that are to be updated by a transaction are usually cashed into main memory buffers, then updated in memory before they're written back to disk. When the system needs more space it replaces blocks in the cache. To replace blocks is also called flushing blocks.
|| Dirty bit || Indicates whether or not the buffer has been modified. On flush a disk is only written to disk if the dirty bit is 1. (modified). One can also store transaction id(s) of the transactions that changed the block.||
|| Pin-unpin bit || A page in cache is pinned (bit is 1) if it cannot be written to disk yet, eg. if the transaction that changed the page isn't commited yet.||
__Flush strategies__
||In-place updating || Buffer is written back to the original disk location||
||Shadowing || Writes an updated buffer at a different disk location. Multiple versions of dataitems can be maintained. Shadowing is not usually used in practice.||
- BFIM (Before image): Old value of data
- AFIM (after image): New value of data
## Policies used in transaction control
The following are four policies that can be used as policiy for when a disk from the cache can be written back to disk:
|| NO-FORCE policy || Changes made to objects are not required to be written to disk in-place. Changes must still be logged to maintain durability, and can be applied to the object at a later time. This reduces seek-time on disk for a commit, as the log is usually sequentially stored in memory, and objects can be scattered. Frequently updated objects can also merge accumulated writes from the log, thereby reducing the total number of writes on the object. Faster, but adds rollback complexity. ||
|| FORCE policy || Changes made to objects are required to be written to disk in-place. Sucks. ||
|| STEAL policy || Allows a transaction to be written on a nonvolatile storage before its commit occurs. Faster, but adds rollback complexity. ||
|| NO-STEAL policy || Does not allow a transaction to be written on a nonvolative storage before its commit occurs. Sucks. ||
Performance wise, if anyone asks, STEAL NO-FORCE is the way to go. In a STEAL/NO-FORCE scheme both REDO and UNDO might be required during recovery.
## The system log
A DBMS maintains a system log tracking all transaction operations to be able to recover from failures. The log must be kept on non-volatile storage, for obvious reasons. A log consists of records of different types:
1. [start\_transaction, transaction\_id]
2. [write\_item, transaction\_id, item\_id, old\_value, new_value]
3. [read\_item, transaction\_id, item_id]
4. [commit, transaction_id]
5. [abort, transaction_id]
## ARIES (aka Algorithms for Recovery and Isolation Exploiting Semantics)
Recovery algorithm designed to work with a no-force, steal database approach. ARIES has three main principles:
|| Write ahead logging || Any change to an object is first recorded in the log, and the log must be written to non-volatile storage before changes to the object are made. ||
|| Repeating history during redo || On restart after a crash, ARIES retraces the steps in history necessary to bring the database to the exact state at the time of the crash, and then undos the transactions that were still active at the time of the crash. ||
|| Logging changes during undo || Changes made to the database during undo are logged to prevent unwanted repeats. ||
Two datastructures must be maintained to gather enough information for logging: the dirty page table (DPT) and the transaction table (TT):
|| Dirty page table (DPT) || Keeps record of all the pages that have been modified and not yet written to disk. It also stores the sequence number of the first sequence that made a page dirty (recLSN). ||
|| Transaction table (TT) || Contains all transactions that are currently running, as well as the sequence number of the last sequence that caused an entry in the log. ||
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.
## Schedule (aka History)
Schedules are lists of operations (usually data reads/writes, locks, commits etc) ordered by time, eg.
$$ S_{a}: r_1(X); w_1(X); C1; $$
S is the name of the transactins. An r is a read-lock, w is a write-lock. The number identifies the transaction. A C means commit, A means abort.
Schedules can be classified into different classes:
|| Serial || Transactions are non-interleaved. No transaction starts before the previous one has ended. Example: D = R1(X);W1(X);C1;W2(X);C2. ||
|| Serializable || Schedules that have equivalent outcomes to a serial schedule are serializable. A schedule is serializable if and only if its precedence graph is acyclic ||
|| Recoverable || Transactions commit only after all transactions whose changes they read, commit. ||
|| Unrecoverable || A schedule which is not recoverable ||
|| ACA (Avoids Cascading Aborts, aka Cascadeless) || Transactions may not read uncommitted changes from another transaction during the same schedule (RAW is disallowed). All ACA are recoverable. ||
|| Strict || Does not allow a transaction to read nor write non-commited values, eg. $S: r_1(A); w_2(B);$ is not allowed. All strict schedules are ACA. Disallows WAW and RAW. ||
### Conflict
Two operations are said to be in conflict if they satisfy all of the three conditions:
1. They belong to different transactions.
2. The access the same item X
3. At least one of the operations is a _write_item(X)_
# Database normalization
Database normalization is the process of organizing the fields and tables of a relational database to minimalize redundancy and dependency.
## Normal forms (aka NF)
A normal form is a set of criteria for determining a table's degree of vulnerability to logical inconsistencies and anomalies. The most common normal forms are:
|| 1NF || A table represents a relation and has no repeating groups. All attribute values are required to be atomic. ||
|| 2NF || No non-prime attribute in the table is partially dependent on any candiate key. ||
|| 3NF || Every non-prime attribute in the table is directly dependent on every candidate key. ||
|| BCNF || Every non-trivial functional dependency is a dependency on a superkey. ||
Note that to meet the requirements of a normal form, a table must also meet all the requirementes of the lower normal forms.
## Functional Dependencies
A functional dependency, written $ A \rightarrow B $, on some relation (table) where A and B are sets of attributes (columns) in the relation, means that if two tuples have the same value in A they must have the same value in B.
$$ A \rightarrow B \Longleftrightarrow t_{n}[A]=t_{m}[A] \Rightarrow t_{n}[B]=t_{m}[B] $$
If more than one attribute appear on either side of the arrow they should be and'ed together
### Rules for functional dependencies
|| Reflexivity || If Y is a subset of X, then $ X \Rightarrow Y $ ||
|| Augmentation || If $ X \Rightarrow Y$, then $XZ \Rightarrow YZ $ ||
|| Transitivity || If $ X \Rightarrow Y $ and $ Y \Rightarrow Z$ then $ X \Rightarrow Z $ ||
You'll get far with these, but they can also be derived to:
|| Union || If $ X \Rightarrow Y $ and $ X \Rightarrow Z $, then $ X \Rightarrow YZ $||
|| Decomposition || If $ X \Rightarrow YZ $, then $X \Rightarrow Y$ and $X \Rightarrow Z$||
|| Pseudotransitivity ||If $ X \Rightarrow Y$ and $WY \Rightarrow Z$, then $WX \Rightarrow Z$ ||
|| Composition || If $ X \Rightarrow Y $ and $ Z \Rightarrow W $, then $ XZ \Rightarrow YW $ ||
So what can these 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 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.
## Desirable properties of a relational decomposition
According to the solutions to several exams (among them 2013V), there is a checklist of four properties that a decomposition of a relation $ R $ into several relations $ R_{1}, R_{2}, … , R_{n} $ should posess or strive to attain:
|| __Property__ || __Explanation__ ||
|| Preservation of attributes || All rows of the original table should be present in at least one of the rows in the new tables ||
|| Preservation of functional dependencies || All functional dependencies of the original table should be present ||
|| Lossless join || Also called the non additive property. When the tables are joined, no additional tuples should be generated ||
|| Highest possible normal form || The individual relations of decomposition should attain the highest normal form possible ||
### 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^{+}$.
## Keys
|| Superkey || A set of attributes of a relation schema that are unique for each tuple. I.e. if S is a superkey of the relation schema R, then no two tuples in R will have the same combination of values in S: $ t_{n}, t_{m}\in R $, $ n\neq m $, $ t_{n}[S]\neq t_{m}[S] $ ||
|| Key || A minimal superkey: removing one of the key's attributes results in it ceasing to be a superkey. ||
|| Candidate key || If a relation has more than one key, they are called candidate keys: candidate keys are a set of attributes that qualify as a key. ||
|| Primary key || Whichever candidate key is arbitrarily chosen as a relation's key. ||
|| Prime attribute || Key attributes are attributes that are part of one or more candidate keys. ||
# Algorithms for natural join/equijoin
The JOIN-operation is one of the most time-consuming operations, and there are many different ways of doing it. Two-way join is to join two files on two attributes. We call the attributes the files are joined on the join attributes. These methods are for two-way NATURAL JOIN or EQUIJOIN. There's pseudocode for them in the book.
## Nested-loop join
Default brute force algorithm. Does not require any special access. Has an outer and inner loop, and compares on the join attributes. If there's match they are joined.
O is the amount of blocks in outer loop.
I is the amount of blocks in the inner loop.
b is the buffer space.
$I/O = O+( ceil( O/( b-2 ))*I)$
## Single-loop join
If an index or hash keye excists for one of the two join attributes, say attribute A of file X, then we retrieve each record of the other file with respect to the attribute. In our example let's say that is file Y with resepct to attribute A. This is done with one single loop over file Y.
Then we use the access strucutre (such as index or hash key) to retrieve directly all matching records from file X that satisfy x[B] = y[A], where x and y are records frm X and Y respectively.
i = amount of index levels for teh attribute you're joining on.
r = amount of blocks ome is looking for.
b = amount of blocks over which these are spread.
$IO = b + (r ( i+3))$
## Sort-merge join
Given that both the records are physically ordered on the join attributes, then we can implement join the most efficent way possible. Both files are scanned concurrently in order of the join attributes. Then we join the records that have a match on the join attributes.
If the files are not sorted, then the may be with external sorting.
## Partition-hash join
Uses a single hash-function to partion both files, then comparing on the "hash buckets."
We'll explain this with an example. Let's say we have two files X and Y and join attributes A and B respectively, and X has fewer records than Y.
__Partition phase:__
First, we have one single pass through file X and hash its records with a hash function _h_. Let's say X is small enough to fit all the hashed records into memory. Now the records with the same hash _h(A)_ is in the same hash bucket.
__Probing phase:__
We have a single pass through the other file Y and hash each record using the same hash function _h(B)_ to probe that bucket, and that record is joined with all the matching records from X in that bucket.
The general case partition hash-join (when the smallest file does not fit entirely in the main memory) is not a part of the curriculum (as of May 2014).
# Relational algebra
Used to describe how data can be organized into sets. It's what modern query languages is built on. A statement in relational algebra can either be given as text, or as a tree.
## Primitive operators
|| Projection (π) || The projection of a relation R on a set of attributes A is the set of all tuples in R restricted to the set of attributes in A. Basically the SELECT of relational algebra. ||
|| Selection (σ) || A selection with the set of conditions C selects all the tuples in a relation R such that the conditions in C hold. Basically the WHERE of relational algebra. ||
|| Rename (ρ) || Renames attributes in a relation. Basically the AS of relational algebra. ||
|| Natural Join (*) || Joins two relations R and S. The result of the join is the set of all combinations of tuples in R and S that are equal on their common attribute names. Basically the INNER JOIN of relational algebra.||
|| Theta Join (⋈) || Joins on a specific condition. ||
# SQL
## Retrieving records
|| SELECT || Selects attributes||
|| FROM || Specifies where we want the attributes from. Does not have to be tables, can be other results.||
||WHERE || Give a condition for the query. Operates on a single row (eg. a single item in a store)||
|| AS || Renames a column/attribute for further use in your query||
||GROUP BY || Lets you specifiy som attribute you want the result grouped by. ||
|| HAVING || Conditions for a group. Operates on aggregates - multiple rows, eg. a group of items in a store ||
|| ORDER BY || How you want to order the data. attributes and ASC/DESC. ||
Choice of extracted data. Usage: __SELECT__ _OPERATION_
|| __OPERATION__ || __Explanation__ ||
|| MIN(column\_name) || Selects the smallest value of specified column ||
|| MAX(column\_name) || Selects the largest value of the specified column ||
|| AVG(column\_name) || Selects the average value of the specified column ||
Note that WHERE gives conditions for a column and HAVING for a group.
### Simple select example with conditions
SELECT attributes you want, use commas to seperate
FROM twhere 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 seperate
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;
## Modifications of tables or database
### Alter a table
Add a 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";
## DDL-operations
DDL - Data Definition Langugae, so operations here is about defining the data and the structure of it.
|| CREATE TABLE navn (...) || New table based on the data given in the parenthesis ||
|| CREATE VIEW query || Creates a view based on the query||
|| CREATE ASSERTION || ||
|| CREATE TRIGGER || ||
### Views
A view is a statement that define a table, but not actually creating a table. In other words it's a new table thatcomposed 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 extenstion of SQL-92. Will update an attribute in a view if the attribute comes from a particular table and taht the primary key is included in the view.
## Functions
Function descriptions from [W3Schools](http://www.w3schools.com/sql/sql_functions.asp).
### Aggregate Functions
||AVG() || Returns the average value||
||COUNT() || Returns the number of rows||
||FIRST() || Returns the first value||
||LAST() || Returns the last value||
||MAX() || Returns the largest value||
||MIN() || Returns the smallest value||
||SUM() || Returns the sum||
### Scalar functions
||UCASE() || Converts a field to upper case||
||LCASE() || Converts a field to lower case||
||MID() || Extract characters from a text field||
||LEN() || Returns the length of a text field||
||ROUND() || Rounds a numeric field to the number of decimals specified||
||NOW() || Returns the current system date and time||
||FORMAT() || Formats how a field is to be displayed||
# Entity Relationship model
An Entity Relationship Model is a data model for describing the structure and organization of data ultimatly to be implemented in a database. An ER-model is usually described through at ER-diagram. The ER-model is for the most part composed of entities that represent objects or things, and relationship classes that represents the realtionship between two entities. The entities is identified with a name and attributes.
## ER-notation used in the lectures
As of May 2014. Described in norwegian.
# Andre relevante dokumenter:
- [Kompendier skrevet av enkeltpersoner](https://wiki.online.ntnu.no/projects/online/wiki/TDT4145>)
- [Forelesningsnotater fra kapittel 16 til kapittel 24](http://goo.gl/g0nZk)
- ["How to fake database design"](http://blogs.perl.org/users/ovid/2013/07/how-to-fake-database-design.html)
- ["Simple Conditions for Guaranteeing Higher Normal Forms in Relational Databases", eller snarvei til femte normalform](http://researcher.watson.ibm.com/researcher/files/us-fagin/tods92.pdf)
- ["Method for determining candidate keys and highest normal form of a relation based on functional dependencies"](http://www.rlvision.com/blog/method-for-determining-candidate-keys-and-highest-normal-form-of-a-relation-based-on-functional-dependencies/)
# Videoforelesninger
Bortsett fra første video er det bare Svein Erik Bratsberg sine forelesninger som er filmet.
<https://video.adm.ntnu.no/openVideo/serier/5124992265fdb>
1. Normaliseringsteori (Roger Midtstraum)
2. Intro del 2: læringsmål. Fellesprosjektrelatert.
3. ...
4. ...
5. Lagring og indekser
6. ...
7. ...
8. ...
9. ...
10. ...
11. Transaksjoner
12. Transaksjoner
13. Transaksjoner: recoverability
14. ...
16. ...