南京信息工程大学高级数据库期末复习资料.doc

一、Concept explaining 1. ordered index Based on a sorted ordering of the values 2. hash index A hash index organizes the search keys, with their associated pointers, into a hash file structure.3. search key An attribute or set of attributes used to look up records in a file is called a search key. 4. Transaction A transaction is a unit of program execution that accesses and possibly updates various data items5. conflict serializable We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule6.data warehouseA data ware house is a repository of information gathered from multiple sources, stored under a unified schema, at a single site. 7.data mining Date mining refers loosely to the process of semi-automatically analyzing large databases to find useful patterns.8.distributed database system In a distributed database system the database is stored on several computers9.local transaction A local transaction is one that accesses data only from sites global transaction10.global transaction A global transaction is one that either accesses data in a site different form the one at which the transaction was initiated, or accesses data in several different sites11.homogeneous distributed database In a homogeneous distributed database system, all sites have indentical database-management system software, are aware of one another, and agree to cooperate in processing usersrequests12.heterogeneous distributed databaseA distribute database has to be constructed by linking together multiple already-existing database systems, each with its own schema and possibly running different database-management software 二、Fill blanks 1.A clustering index is an index whose search key also defines the sequential order of the file. 2.To ensure integrity of the data,we require that the database system maintain the following properties of the transactions: Atomicity,Consistency , Isolation , Durability . 3. Transactions access data using two operations, write(X), which transfers the data item X from the local buffer of the transaction that executed the write back to the database . 4. Ensuring durability is the responsibility of a software component of the database system called the recovery-management component . 5. If a schedule S can be transformed into a schedule Sby a series of swaps of nonconficting instructions, we say that S and Sare conflict equivalent . 6. A recoverable schedule is one where,for each pair of transactions Ti and Tj such that Tj reads a data item previously written by Ti,the commit operation of Ti appears before the commit operation of Tj . 7. A cascadeless schedule is ne where,for each pair of transactions Ti and Tj such that Tj reads a data item previously written by Ti,the commit operation of Ti appears before the read operation of Tj . 8.There are main two main modes: shared and exclusive in which a data item may be locked. 9.There are two types of errors: Logical error and System error that may cause a transaction to fail. 10.According to relative speed, capacity,and resilience to failure, storage media can be classified volatile storage and nonvolatile storage . 11.Block movements between disk and main memory art initiated through the following two operations,output(B) transfers the buffer block B to the the disk , and replaces the appropriate physical block there.12.The deferred-database modification technique ensures transaction atomicity by recording all database modifications in the log . 13.Server system can be broadly categorized as transaction servers and data servers .14.Transaction-server systems,also called query-server systems, provide an interface to which clients can send requests to preform an action,in response to which they execute the action and send back results to the client .15.Data-server systems allow client to interact with the servers .16.The processes that form part of the database system include lock manager process , , database writer process, log writer process, checkpoint process, process monitor process.17.There are two main measures of performance of a database system: (1) throughput , the number of tasks that can be completed in a given time interval, and (2) response time , the amount of time it takes to complete a single task from the time it is submitted.18.Running a given task in less time by increasing the degree of parallelism is called speedup .19.Handling larger tasks by increasing the degree of parallelism is called scaleup .20.There are several reasons for building distributed database systems, including sharing data , Autonomy , and Availability .21.Consider a relation r that is to be stored in the database. There are two approaches to storing this relation in the distributed database: replication and global fragmentation .22.There are two different schemes for fragmenting a relation: account .23.Data transparency includes three main forms: fragmentation , and transparency .24.A distributed system may suffer from the same types of failure that a centralized system does. The basic failure types are failure of a site , loss of message, failure of a communication link and Network partition .三、Answer questions 1. How to avoid starvation of transactions? A: We can avoid starvation of transactions by granting locks in the following manner:When a transaction Ti requests a lock on a data item Q in a particular mode M,the concurrency-control manager grants the lock provided that (1)There is no other transaction holding a lock on Q in a mode that conflicts with M (2)There is no other transaction that is waiting for a lock on Q and that made its lock request before Ti 2. Explains two-phase locking protocol, strict two-phase locking protocol and rigorous two-phase locking protocol. A:The two-phase locking protocol allows a traction to lock a new data item only if that traction has not yet unlocked any data item. Cascading rollbacks can be avoided by a modification of two-phase locking called the strict two-phase locking protocol.This protocol requires not only that locking be two phase,but also taht all exclusive-mode locks taken by a traction be held until that traction commits. Another variant of two-phase locking is the rigorous two-phase locking protocol,which requires that all locks be held until the traction commits.3.There are three different logs, please recovery the database with immediate-modification technique,write the final results of A,B and C values of these cases respectively. Fig.1 Three different logA:A-$950 B-$2050 C-$6004. Suppose you were in charge of the database operations of a company whose main job is to process transactions. Suppose the company is growing rapidly each year, and has outgrown its current computer system. When you are choosing a new parallel computer,what measure is most relevant-speedup, batch scaleup, or transaction scaleup? Why?A:With increasing scale of operations, we expect that the number oftransactions submitted per unit time increases. On the other hand,we wouldntexpect most of the individual transactions to grow longer, nor would we requirethat a given transaction should execute more quickly now than it did before.Hence transaction scale-up is the most relevant measure in this scenario5. Consider a bank that has a collection of sites, each running a database system. Suppose the only way the databases interact is by electronic transfer of money between one another. Would such a system qualify as a distributed database? Why?A:In a distributed system, all the sites typically run the same databasemanagement software, and they share a global schema. Each site provides anenvironment for execution of both global transactions initiated at remote sitesand local transactions. The system described in the question does not havethese properties, and hence it cannot qualify as a distributed database.四、Application1. Given the set of key values as follows. (10,15,21,37,44,51,59,63,72,85,91,97) Assume that the tree is initially empty and values are added inasending order. Please finish following operation:(1) Construct a B+-tree for four pointers. (2) Insert 26 and 32 values into the above B+-tree.(3) Delete 63 value2. Suppose that we are using extendable hashing on a file that contains records with the following search-key values: 2,3,5,7,11,17,19,23,29,31The hash function is h(x)=x mod 8 and buckets can hold three records. 1Construct a extendable hash structure 2Delete 11 3Insert 15 3. Consider the following two transactions: T1: read(A); read(B); if A=0 then B:=B+!; write(B); T2: read(B); read(A); if B=0 then A:=A+!; write(A). Let the consistency requirement be A=0 or B=0, with A=B=0 the initial values.(1) Show a concurrent execution of T1 and T2 that produces a nonserializable schedule.(2) Is there a concurrent execution of T1 and T2 that produces a serializable schedule, Why? A(1)(2)There is no parallel execution resulting in a serializable schedule. Frompart a. we know that a serializable schedule results in A = 0 B = 0. Supposewe start with T1 read(A). Then when the schedule ends, no matterwhen we run the steps of T2, B = 1. Now suppose we start executing T2prior to completion of T1. Then T2 read(B) will give B a value of 0. Sowhen T2 completes, A = 1. Thus B = 1 A = 1 (A = 0 B = 0).Similarly for starting with T2 read(B).4. Is the expression rirj necessarily equal to rjri for the relations of Figure 1.Why? Under what conditions does rirj = rjri hold?In general, ri rj = rj ri. This can be easily seen fromExercise 22.11, in which r s = s r. r s was given in 22.11,whileBy definition, ri rj = Ri (ri rj) and rj ri= Rj (ri rj), whereRi and Rj are the schemas of ri and rj respectively. For Ri (ri rj) to bealways equal to Rj (ri rj), the schemas Ri and Rj must be the same.5. Consider the relations Employee(name, address, salary, plant_number) Machine(machine_number, type, plant_number) Assume that the employee relation is fragmented horizontally by plant_number, and that each fragment is stored locally at its corresponding plant site. Assume that the machine relation is stored in its entirety at the Armonk site. Describe a good strategy for processing each of the following queries.a) Find all employees at the plant that contains machine number 1130.b) Find all machines at the Almaden plant.c) Find employeemachine. A:a)i. Perform plant number (machine number=1130 (machine) at Armonk.ii. Send the query name (employee) to all site(s) which are in the resultof the previous query.iii. Those sites compute the answers.iv. Union the answers at the destination site.b) i. Perform plant number = x (machine) at Armonk, where x is the plantnumber for Almaden.ii. Send the answers to the destination site.c) Strategy :i. Group machine at Armo