# 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

### 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.

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_.

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 transaaction 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. These axioms 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 $$ || Now just use the rules and see if you can get A to be B. If not, they're not equivalent. If you can, try to get B to A. If that works too you've got yourself an equivalence. So what this be used for? __Equivalent functional dependencies__ Two functional dependencies A and B are said to be equivalent if you can derive A to B and B to A. __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. ## 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. || 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. ... 13. ... 14. ... 15. ... 16. ...