1. Each transaction is a node in the schedule
2. Two edges Ti and Tj are connected if
• Wi(X) precedes Rj(X)
• Wi(X) precedes Wj(X)
• Ri(X) precedes Wj(X)

• Locks - each transaction locks the item it uses and unlocks the items when the transaction is complete. The two phase-locking protocol (2PL) guarantees a legal schedule of consistent transactions
• Timestamps - A unique identifier for each transaction generated by the system. 
• Read/Write locks - Allows several transactions to access X if they all access X for reading only so you have read_lock(X), write_lock(X) and unlock(X)

• The Coffman Conditions by Edward G. Coffman:
• Mutual exclusion - At least two resources must be non shareable. Only one process can use a resource given at any given time. In other words; you have a critical region protected by semaphores.
• Hold and wait or resource holding - a process is currently holding at least one resource and requesting additional resources which are held by other processes
• No pre-emption The operating system must not de-allocate resources once they have been allocated - they must be released by the resource voluntarily on comletion
• Circular wait - if you have a set of waiting resources P = {P1, P2, ... Pn} then P1 is waiting for P2, P2 is waiting for P3 and so on until Pn is waiting for P1. 

A way of detecting a state of deadlock

1. Put all transactions as nodes
2. Whenever a transaction Ti is waiting to lock the item X thatis currently locked by Tj, we construct a directed edge Ti -> Tj
3. If graph has cycles, there is a state of deadlock

• Assign a time to the start of a transaction and then use it to order events. Each transaction has a property TS(T) assigned by the DBMS.
• If TS(T1) < TS(T2) means that T1 is before T2
• Each database item X is associated with:
• Rt(X) - highest timestamp of a transaction that was read(X)
• Wt(X) - Highest timestamp of a transaction that has write(X)
• C(X) - a boolean which is true iff the most recent transaction to write(X) has committed

• Request R(X): from Transaction T
• If TS(T) >= WT(X) the read is realizable.
• If C(X) is true grant the request. If TS(T) > RT(X) update RT(X) to TS(T).
• If C(X) is false delay until C(X) is true, or the other transaction aborts.
• If TS(T) < WT(X) the read is unrealizable. Rollback T, abort and restart with a new larger timestamp.
• Request W(X): from Transaction T
• If TS(T) >= RT(X) and TS(T) >= WT(X)  the write is realizable
• Write new value for X
• Set WT(X) = TS(T)
• Set C(X) = false
• If TS(T) >= RT(X) but TS(T) < WT(X) then the write is realizable but there is already a later value in X.
• If  C(X) is true then ignore the write by T.           
• If C(X) is false delay T.
• If TS(T) < RT(X) then the write is physically unrealizable. Abort and rollback. 

• Does not have the formal structure of a relational database
• Still contains tags or other markers to separate semantic elements and enforce hierarchies of record and fields within data
• Known as schema less or self-describing structure

• Data is organized in semantic entities
• Similar entities are grouped together
• Entities in a group may not have the same attributes
• Order of attributes is not necessarily important
• Not all attributes may be required
• Type and size of attributes in group might be different

• De-Facto model for semistructured data
• Graph based self-describing object instance model
• Lorel is a query language for OEM
• Can be thought as a graph

• Each node corresponds to an object with a unique identifier (&12)
• Atomic values at leafs; integer, real string, image audio
• Other objects are complex; they are a set of (lable, oid) pairs

Sample queries in Lorel:

Select Guid.restaurant.address WHERE Guide.restaurant.address.zipcode = 92310

Result: {&14} -- This is an object id

Using Wildcards

Select Guide.restaurant.name, Guide.restaurant(.address)?.zipcode

WHERE Guide.restaurant.% grep “cheap”

% matches any sub-object. Grep similar to UNIX grep

• Must have correct syntax
• Must have a root element
• Must have a closing tag
• Tags are case sensitive
• Proper nesting
• Attributes are quoted
• Heading contains information and other items such as stylesheet of DTD (Document Type Definition) which is the document structure what elements are permitted in what order

DTD (Document Type Defintions): Define the document structure what elements are permitted in a document and in what order.

Limitations

• Not written in XML syntax so need to learn a new syntax to write them
• No support for namespaces
• No constraints imposed on the kind of character data allowed
• Little support for modularity and no support for inheritance which makes it hard to maintain