This assignment is ungraded and should not be submitted. The questions review key concepts from the reading for this module.

Help Policy

Authorized Resources
Any
Notes
You may jointly work on this assignment with classmates

Assignment

Answer the following questions from Fundamentals of Database Management Systems (Gillenson, 2011).

  1. Describe the two different problems that forward recovery and backward recovery are designed to handle. Do mirrored databases address one of these two problems or yet a third one? Explain. (Question 11.13)

    In forward recovery, restoration of a database – e.g., following a crash or system failure – starts with the latest (complete) backup and committed changes in the transaction (or change) log are applied to that backup.

    In backward recovery, changes in the transaction (or change) log are reversed to “undo” all those that follow an erroneous one that corrupted the database. The reversed transactions are then re-executed.

    A mirrored database is a duplicate that is updated simultaneously with the “main” database. If either is destroyed, then applications can continue to use the other.

  2. What is the lost-update problem? (Question 11.18)

    The lost-update problem is an example of a dirty read (i.e., a read phenomenon) where a transaction reads data that has been modified by a concurrent transaction but not yet committed. In the lost update problem, both transactions attempt to update the value and the last write wins – i.e., the two transactions have a race condition where the behavior is dependent on the order of their execution.

  3. What is deadlock and how can it occur? (Question 11.20)

    Deadlock occurs when two (or more) database transactions wait indefinitely for a resource being used by another transaction. The necessary conditions for deadlock are as follows:

    hold and wait
    each transaction must be holding at least one resource and waiting for additional resource(s)
    mutual exclusion
    at least one resource must be held exclusively (i.e., not shared)
    no preemption
    a resource can only be released by the transaction that is currently using (i.e., holding) it
    circular wait
    the dependency graph of transactions waiting for resources must contain a cycle

  4. A large bank has a headquarters location plus several branches in each city in a particular region of the country. As transactions are conducted at each branch, they are processed online against a relational database at headquarters. You have been hired as the bank’s Director of Data Security. Design a comprehensive set of data security measures to protect the bank’s data. (Exercise 11.1)

    A summary of key security controls is as follows:

    Physical security
    Limit access to those personnel required to maintain the equipment and use two-factor authentication for access. Minimize risks due to natural disasters (e.g., floods) and terrorist attacks by placing servers in an interior location within the building. Hire armed security guards for the facility.
    Controlled access to the database
    Limit database access to computers owned by the company and preferably only those used by employees whose jobs require access. Use two-factor authentication to access these computers. Restrict database permissions to only those capabilities required to accomplish an employee’s job functions.
    Data encryption
    Encrypt data at rest and in transit. Encryption minimizes the risks of disks being lost or stolen and the risks of interception.
    Firewalls, intrusion detection, data loss prevention, etc.
    Use the recommended tools to minimize the risks due to malware and advanced persistent threats (APTs).
    Training
    Educate users about security controls and proper cybersecurity hygiene.

  5. The Tasty Seafood Restaurant is a large restaurant that specializes in fresh fish and seafood. Because its reputation for freshness is important to Tasty, it brings in a certain amount of each type of fish daily and, while trying to satisfy all of its customers, would rather run out of a type of fish than carry it over to the next day. After taking a table’s order, a waiter enters the order into a touch-screen terminal that is connected to a computer in the kitchen. The order is sent from the touch-screen terminal to the computer only after all of it has been entered.

    At 8:00 PM there are 10 servings of salmon, 15 servings of flounder, and eight orders of trout left in the kitchen. At 8:03 PM, waiter Frank starts entering an order that includes five servings of salmon, six of flounder, and four of trout. At the same time, on another touch-screen terminal, waitress Mary starts entering an order that includes one serving of salmon, three of flounder, and two of trout. At 8:05 PM, before the other two have finished entering their orders, waitress Tina starts entering an order that includes six servings of salmon, one of flounder, and five of trout. Frank finishes entering his order at 8:06 PM, Mary finishes at 8:07 PM, and Tina finishes at 8:09 PM. (Exercise 11.3)

    1. What would the result of all of this be in the absence of locks?

      Because Tina starts entering her order before Frank and Mary finish entering their orders, Tina sees that there are 10 servings of salmon, 15 servings of flounder, and 8 orders of trout available. When Tina finishes her order, her changes overwrite those made by Frank and Mary, resulting in 6 servings of salmon, 14 servings of flounder, and 3 orders of trout being marked as available.

      Time Frank Mary Tina
      8:03pm Read (salmon)    
        Read (flounder)    
        Read (trout)    
          Read (salmon)  
          Read (flounder)  
          Read (trout)  
      8:05pm     Read (salmon)
            Read (flounder)
            Read (trout)
      8:06pm Write (salmon - 5)    
        Write (flounder - 6)    
        Write (trout - 4)    
      8:07pm   Write (salmon - 1)  
          Write (flounder - 3)  
          Write (trout - 2)  
      8:09pm     Write (salmon - 6)
            Write (flounder - 1)
            Write (trout - 5)

    2. What would the result be with a locking mechanism (specifically strict two-phase locking (2PL)) in place?

      The transaction schedule may vary, but one example is as follows:

      Time Frank Mary Tina
      8:03pm Lock-S (salmon)    
        Lock-S (flounder)    
        Lock-S (trout)    
        Read (salmon)    
        Read (flounder)    
        Read (trout)    
          Lock-S (salmon)  
          Lock-S (flounder)  
          Lock-S (trout)  
          Read (salmon)  
          Read (flounder)  
          Read (trout)  
      8:05pm     Lock-S (salmon)
            Lock-S (flounder)
            Lock-S (trout)
            Read (salmon)
            Read (flounder)
            Read (trout)
      8:06pm Lock-X (salmon) – fails    
      8:07pm   Lock-X (salmon) – fails  
          Deadlock – abort transaction (and release locks)  
        Lock-X (salmon) – fails    
      8:09pm     Lock-X (salmon) – fails
            Deadlock – abort transaction (and release locks)
        Lock-X (salmon)    
        Lock-X (flounder)    
        Lock-X (trout)    
        Write (salmon - 5)    
        Write (flounder - 6)    
        Write (trout - 4)    
        Commit (and release locks)    
      8:10pm   Lock-S (salmon)  
          Lock-S (flounder)  
          Lock-S (trout)  
          Read (salmon)  
          Read (flounder)  
          Read (trout)  
          Lock-X (salmon)  
          Lock-X (flounder)  
          Lock-X (trout)  
          Write (salmon - 1)  
          Write (flounder - 3)  
          Write (trout - 2)  
          Commit (and release locks)  
      8:11pm     Lock-S (salmon)
            Lock-S (flounder)
            Lock-S (trout)
            Read (salmon)
            Read (flounder)
            Read (trout)
            Lock-X (salmon)
            Lock-X (flounder)
            Lock-X (trout)
            Write (salmon - 4)
            Write (flounder - 1)
            Write (trout - 2)
            Commit (and release locks)

      In this instance, locking prevents the “lost update” problem, and Tina’s transaction, which completes last, cannot enter more than the remaining number of salmon and trout. The end result is that there is no servings of salmon, 5 servings of flounder, and no servings of trout remaining, and Tina has several patrons who will have to eat flounder for dinner.

    3. What would happen if versioning was in use?

      The outcome is the same as the prior part (although the transaction schedule would be different – namely, not requiring locks).

  6. Construct examples of the lost update problem for the case of a joint bank account (i.e. two people with access to the same bank account). (Exercise 11.4)

    In the lost update problem, one transaction overwrites the value written by a concurrent transaction. An example is as follows:

    Sue wants to deposit $20 into the bank account while Tom wants to withdraw $5 from an ATM using the same account. The transaction schedule follows:

    Sue Tom
    Read (balance)  
      Read (balance)
    Write (balance + 20)  
      Write (balance - 5)

    In this instance, the account’s balance decreases by $5 even though it should increase by $15. Sue’s deposit and increase to the account balance has been overwritten (i.e., “lost”) by Tom’s concurrent ATM withdraw.

  7. What is a distributed database? What is a distributed database management system? (Question 12.6)

    A distributed database spreads data across multiple servers (including those in disparate geographic locations), but the data comprises a single logical database.

    A distributed database management system (DBMS) manages a distributed database, particularly providing location transparency – i.e., the abstraction of the physical location of the data – for clients.

  8. Describe the two-phase commit approach to updating replicated data. (Question 12.11)

    The two-phase commit protocol has a “prepare” phase where each replica must elect to proceed with the commit and the “commit” phase where the transition is committed if all replicas elected to proceed with the commit. (Conversely, the transaction is aborted if any replica aborts the transaction.)

  9. Australian Boomerang, Ltd. wants to design a distributed relational database. The company is headquartered in Perth and has major operations in Sydney, Melbourne, and Darwin. The database involved consists of five tables, labeled A, B, C, D, and E, with the following characteristics:

    • Table A consists of 500,000 records and is heavily used in Perth and Sydney.
    • Table B consists of 100,000 records and is frequently required in all four cities.
    • Table C consists of 800 records and is frequently required in all four cities.
    • Table D consists of 75,000 records. Records 1-30,000 are most frequently used in Sydney. Records 30,001–75,000 are most frequently used in Melbourne.
    • Table E consists of 20,000 records and is almost exclusively in Perth.

    Design a distributed relational database for Australian Boomerang. Justify your placement, replication, and partitioning of the tables. (Exercise 12.1)

    Based on the information provided, the tables would be located as follows:

    • Table A is replicated at Perth and Sydney because both locations use it frequently. Replication also increases its availability and minimizes communication costs.
    • If the data in Table B is not volatile (i.e., the frequency of updates is low), it is replicated at Perth, Sydney, Melbourne, and Darwin because it is used frequently in each location. If the data is volatile, it may be replicated to two cities for availability, but the expected increase in availability must be weighed against the cost of synchronous (or asynchronous) updates.
    • Table C is replicated in two cities for availability. Given the small number of records, the data can be distributed to other sites when required for distributed joins.
    • Table D is horizontally partitioned in Sydney, and Melbourne. Records 1–30000 are stored in Sydney and records 30001–75000 in Melbourne.
    • Table E is stored in Perth because it is rarely used elsewhere.