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

1、第 1页共 6页 、Concept explaining 1. ordered in dex Based on a sorted orderi ng of the values 2. hash in dex A hash index organizes the search keys, with their associated pointers, structure. 3. search key An attribute or set of attributes used to look up records in a file is called a search key. 4. Tran

2、 sact ion A transaction is a unit of program execution that accesses and possibly updates various data items 5. c on flict serializable We say that a schedule S is con flict serializable if it is con flict equivale nt to a serial schedule 6. data warehouse A data ware house is a repository of inform

3、ation gathered from multiple sources, stored un der a uni fied schema, at a sin gle site. 7. data mi ning Date mining refers loosely to the process of semi-automatically analyzing large databases to find useful patter ns. 8. distributed database system In a distributed database system the database i

4、s stored on several computers 9.lo cal tran sact ion A local tran sact ion is one that accesses data only from sites global tran sact ion 10. global tran sact ion A global transaction is one that either accesses data in a site different form the one at which the tran sacti on was in itiated, or acce

5、sses data in several differe nt sites 11. homoge neous distributed database In a homoge neous distributed database system, all sites have inden tical database-ma nageme nt system software, are aware of one ano ther, and agree to cooperate in processing users requests 12. heteroge neous distributed d

6、atabase A distribute database has to be constructed by linking together multiple already-existing database systems, each with its own schema and possibly running differe nt database-ma nageme nt software 、Fill blanks 1. A clustering index is an index whose search key also defines the sequential orde

7、r of the file. 2. To en sure in tegrity of the data,we require that the database system maintain the follow ing properties of the tran sact ions: Atomicity,Con siste ncy , Isolati on , Durability . 3. Transactions access data using two operations, write(X), which transfers the data item X from the l

8、ocal buffer of the tran sact ion that executed the write back to the database into a hash file 第 2页共 6页 4. Ensuring durability is the responsibility of a software component of the database system called the recovery-ma nageme nt comp onent 5. If a schedule S can be transformed into a schedule S by a

9、 series of swaps of noncon ficti ng in structi ons, we say that S and S are con flict equivale nt . _ 6. A recoverable schedule is one where,for each pair of transactions Ti and Tj such that Tj reads a data item previously writte n by Ti,the commit operati on of Ti appears before the commit operati

10、on 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 writte n by Ti,the commit operati on of Ti appears before the read operati on of Tj . 8. There are main two main modes: shared and exclusive in which a data _ item may b

11、e locked. 9. There are two types of errors: Logical error and System error that may cause a tran sact ion to fail. 10. Accord ing to relative speed, capacity,a nd resilie nee to failure, storage media can be classified volatile storage and non volatile storage . _ II. _ BIock movements between disk

12、and main memory art initiated through the following two operati on s,output(B) tran sfers the buffer block B to the the disk , and _ replaces the appropriate physical block there. 12. The deferred-database modificati on tech nique en sures tran sacti on atomicity by recording all database modificati

13、 ons in the log . 13.Server system can be broadly categorized as transaction servers and data _ _ servers 14. Tra nsact ion-server systems,also called query-server systems, provide an in terface to which clients can send requests to preform an actio n,in resp onse to which they execute _ the action

14、and send back results to the clie nt . 15. Data-server systems allow clie nt to in teract with the servers . _ 16. The processes that form part of the database system in clude lock man ager process , , database writer process, log writer process, checkpoint process, process mon itor process. 17. The

15、re are two main measures of performanee of a database system: (1) throughput , the nu mber of tasks that can be completed in a give n time in terval, and (2) response _ time , the am ount of time it takes to complete a sin gle task from the time it is submitted. 18. Running a given task in less time

16、 by increasing the degree of parallelism is called speedup . 19.Ha ndling larger tasks by in creas ing the degree of parallelism is called 20.There are several reas ons for buildi ng distributed database systems, in cludi ng shari ng data ,Aut onomy ,and Availability . 第 3页共 6页 21. C on sider a rela

17、tio n r that is to be stored in the database. There are two approaches to stori ng this relati on in the distributed database: replicati on and global fragme ntati on 22. There are two differe nt schemes for fragme nti ng a relati on: acco unt . _ 23. Data tran spare ncy in cludes three main forms:

18、fragme ntati on , and tran spare ncy 24. A distributed system may suffer from the sametypes of failure that a centralized system does. The basic failure types are failure of a site , loss _ of message, failure of a com munication link and Networ _ 三、Answer questions 1. How to avoid starvati on of tr

19、an sact ions? 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 con curre ncy-c on trol man ager gra nts the lock provided that (1) There is no other transaction holding a lock on Q i

20、n 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 lock ing protocol. A:The two-phase lock ing protocol allows a tra

21、ct ion to lock a new data item only if that tract ion has not yet uni ocked any data item. Cascading rollbacks can be avoided by a modification of two-phase locking called the strict two-phase lock ing protocol.This protocol requires not only that lock ing be two phase,but also taht all exclusive-mo

22、de 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 un til the tract ion commits. 3. There are three different logs, please recovery the database with immediate-modific

23、ation tech niq ue,write the final results of A,B and C values of these cases respectively. start start Af 1000, 950 T0 commit (a) (b) (c) Fig.1 Three differe nt log A:A-$950 B-$2050 C$600 4.Suppose you were in charge of the database operatio ns of a compa ny whose main job is to process transactions

24、. Suppose the company is growing rapidly each year, and has outgrown its curre nt computer system. When you are choos ing a new parallel computer,what measure is most releva nt-speedup, batch scaleup, or tran sact ion scaleup? Why? 第 4页共 6页 A:With in creas ing scale of operati ons, we expect that th

25、e nu mber of tran sact ions submitted per un it time in creases. On the other han d,we would n t expect most of the in dividual tran sacti ons to grow Ion ger, nor would we require that a give n tran sact ion should execute more quickly now tha n it did before. Hence tran sact ion scale-up is the mo

26、st releva nt measure in this seen ario 5.Consider a bank that has a collection of sites, each running a database system. Suppose the only way the databases in teract is by electr onic tran sfer of money betwee n one ano ther. Would such a system qualify as a distributed database? Why? A:l n a distri

27、buted system, all the sites typically run the same database man ageme nt software, and they share a global schema. Each site provides an en vir onment for executi on of both global tran sact ions in itiated at remote sites and local tran sact ions. The system described in the questio n does not have

28、 these properties, and hence it cannot qualify as a distributed database. 四、Application 1. Give n the set of key values as follows. (10,15,21,37,44,51,59,63,72,85,91,97) Assume that the tree is in itially empty and values are added in ase nding order. Please finish follow ing operati on: (1) Con str

29、uct a B +-tree for four pointers (2) Insert 26 and 32 values into the above B +-tree . (3) Delete 63 value 2. 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,31 The hash function is h(x)=x mod 8 and buckets can

30、 hold three records. 1Con struct a exte ndable hash structure 2Delete 11 3I nsert 15 3. Con sider the followi ng two tran sact ions: T1: read(A); read(B); if A=0 the n B:=B+!; write(B); T2: read(B); read(A); if B=0 the n A:=A+!; write(A). Let the con siste ncy requireme nt be A=0 or B=0, with A=B=0

31、the in itial values. (1) Show a con curre nt executi on of T1 and T2 that produces a non serializable schedule. (2) Is there a concurrent execution of T1 and T2 that produces a serializable schedule, Why? A(1)第 5页共 6页 Any interleaving of 1 and results in a non-serializable schedule. read) read(B) re

32、adM) read(B) if 4 = 0 then B = B + 1 if B = 0 thn 4=4 + 1 writcf/l) write! B) (2)There is no parallel executi on result ing in a serializable schedule. From part a. we know that a serializable schedule results in A = 0 V B = 0. Suppose we start with T1 read(A). Then whe n the schedule en ds, no matt

33、er whe n we run the steps of T2, B = 1. Now suppose we start executi ng T2 prior to completion of T1. Then T2 read(B) will give B a value of 0. So when T2 completes, A = 1. Thus B = 1 A A = 1 (A = 0 V B = 0). Similarly for starting with T2 read(B). 4. Is the expression ri* 耳 necessarily equal to rj*

34、 A for the relations of Figure 1.Why? Under what con diti ons does r* 口 = rj* A hold? n Ri (ri rj) and rj ri= n Rj (ri rj), where Ri and Rj are the schemas of ri and rj respectively. For n Ri (ri rj) to be always equal to n Rj (ri rj), the schemas Ri and Rj must be the same. 5. Con sider the relati

35、ons Employee( name, address, salary, pla nt_nu mber) Mach in e(mach ine_nu mber, type, pla nt_nu mber) Assume that the employee relati on is fragme nted horiz on tally by pla nt_nu mber, and that each fragme nt is stored locally at its corresponding plant site. Assume that the machine relation is st

36、ored in its entirety at the Armonk site. Describe a good strategy for process ing each of the follow ing queries. a) Find all employees at the pla nt that contains mach ine nu mber 1130. b) Find all mach ines at the Almade n pla nt. c) Find employee g mach ine. A: a) i. Perform n plant number ( cr m

37、achine number=1130 (machine) at Armonk. ii. Send the query n name (employee) to all site(s) which are in the resultL U r S- 3 6 8 2 3 2 while 第 6页共 6页 of the previous query. iii. Those sites compute the an swers. iv. Union the an swers at the dest in ati on site. b) i. Perform plant number = x (machine) at Armonk, where x is the plant nu mber for Almade n. ii. Send the an swers to the dest in ati on site. c) Strategy : i. Group