Shared Flashcard Set


Comp2004 Revision Set 4
Comp2004 Revision Set 4 - Comp2004 Revision Set 4
Computer Science
Undergraduate 2

Additional Computer Science Flashcards




What is a precedence graph?
Used to determine if a schedule is conflict serializable. A precedence graph is a directed graph representing the precedence of transactions in the schedule reflected by precedence of conflicting operations in the transactions. If the graph is acyclic, then the schedule is conflict-serializable.
What is the algorithm for creating a precedence graph?
  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)
Give an example of a precedence graph
What are some protocols for concurrency control?
Because serial schedules are inefficient, DBMS introduce protocols to ensure serializability in all schedules, the most common approach is the Two-Phase locking
What does two-phase-locking consist of?
In every transaction, all read or write lock actions precede all unlock actions
What are key attributes in concurrency control?
  • 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)
What are conditions necessary for deadlocks to arise?
  • 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. 
What is the Wait-For-Graph?

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
What are transaction timestamps?
  • 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
What are the rules for time-based scheduling?
  • 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. 
What is semistructured data?
  • 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
What are the properties of semi-structured data?
  • 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
What are the characteristics of the Object Exchange Model?
  • 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
What does the OEM consist of?
  • 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 WHERE = 92310

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


Using Wildcards


WHERE grep “cheap”

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

What are the principles of well-formed XML?
  • 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
What are DTDs and what are the limitations?

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


  • 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
CDATA Sections: Contain character data that is not parsed by the XML parser
Supporting users have an ad free experience!