數(shù)據(jù)庫理論與技術(shù)期終考試復(fù)習(xí)題-帶答案

1、數(shù)據(jù)庫理論與技術(shù)復(fù)習(xí)題1. 考慮用二元聯(lián)系（圖1）對三元聯(lián)系（圖2）的表示：ABECRARCRBBARC 圖1圖1 圖21) 分別給出圖1中E，A，B，C，RA，RB和RC的一個實例，這些實例不對應(yīng)圖2中A，B，C和R的任何實例；2) 更改圖1中的ER圖，引入適當(dāng)?shù)募s束以確保滿足約束的E，A，B，C，RA，RB和RC的任何實例都對應(yīng)于A，B，C和R的一個實例；3) 更改以上的轉(zhuǎn)化以表示在三元聯(lián)系上的全參與約束；4) 以上表示要求為E創(chuàng)建一個主碼屬性，試問如何將E處理為弱實體集，以便不需要主碼？解：1） 令 E = e1, e2, A = a1, a2, B = b1, C = c1, RA =

2、 (e1, a1), (e2, a2),Rb=(e1,b1), Rc=(e1,c1)；可以看出，由于元組（e2,a2）的原因，不存在任何實例對應(yīng)于E,Ra,Rb,Rc2） 如下圖所示：通過引入E 和關(guān)系 Ra ， Rb ， Rc之間的全部參與的約束條件，以便在 E 中的每個元組都和A ，B，C有關(guān)系。3） 假設(shè)A全部參與關(guān)系R，則在A和Ra之間引入全部參與約束。4） 將 E看作弱實體集，而將Ra,Rb,Rc看作標(biāo)志聯(lián)系集。如下圖所示2. Suppose that we are using extendable hashing on a file that contains records wi

3、th the following search-key values: 2, 3, 5, 7, 11, 17, 19, 23, 29, 31,35,271) Show the extendable hash structure for this file if the hash function is h(x) = x mod 8 and buckets can hold three records.2.解：(1)(一點疑惑：這道題用的不是書中的用高位extendable hash?只有憑感覺做了，不一定正確，拉鏈法擴展，超出24后乘2 rehash)(若是按書上的，先mod 8得到hash值

4、，取高位二進制最多111，即directory depth最大為3)Bucket號0：1：17,2：23：3，11，19 - 35，274：5：5，296：7：7，23，31(2) 只注明了修改的行a. Bucket3：3，19，35 - 27b. Bucket7：7，23，31 - 15c. Bucket7：7，23，15d. Bucket1：17，25答案類似下面：2) Show how the extendable hash structure of part 1) changes as the result of each of the following steps:a. Delet

5、e 11.b. Insert 15.c. Delete 31.d. Insert 25.3. Suppose that Bloom filter uses m=32 bits, and 3 hash functions h1, h2, and h3, where hi(x) = (x2 +x3)*i) mod m.3.答：(1)(2)直接套hash函數(shù)(3) 套公式： 任何一位k個hash后還是為0的概率:p=(1-1.0/m)kn 誤判率：f = (1-p)k1) Show the Bloom filter bits following each of the following six e

6、lements insertions in order: 2013, 2010, 2007, 2004, 2001, 19982) For the Bloom filter obtained after part 1), find one value that is not among the six inserted values, but is a false positive.3) Compute the probability of a false positive f.4. 假設(shè)用Bloom filter存放集合S(其中元素個數(shù)為34億),hash函數(shù)個數(shù)為8,允許的錯誤率最大為0.

7、001,那么該Bloom filter的位數(shù)m最小應(yīng)為多少?4.解：M = n*1.44*log2(1.0/f)5. The key-value store uses quorums for consistency. The total number of replicas, N, for a key, is fixed however, N may be different for different keys. Each read has to access at least r replicas (and returns if all of them agree), while each

8、 write has to write to at least w replicas.For each of the following design choices, say whether it (by itself) does or does not guarantee strong consistency, i.e., one copy serializability?a. w=3, r=1b. w = 2N/3c. r+w = Nd. w = Ne. r + w N/2f. r + w 3N/2g. r + w 3N/2, w 2N/3 N越大，同一個數(shù)據(jù)的備份越多，系統(tǒng)相對也就越不

9、容易丟失數(shù)據(jù)。lW越大，系統(tǒng)的一致性會越高，但更新操作也就越慢。lR越大，系統(tǒng)的一致性會越高，但讀操作也就越慢。lW+RN，系統(tǒng)是強一致性的。為什么？舉例來說，假設(shè)N=6，W=R=3，當(dāng)一個更新操作完成的時候，它至少更新了6個備份中的3個備份，那么當(dāng)我們?nèi)プx取這個數(shù)據(jù)的時候，因為R=3，所以我們至少得讀3個數(shù)據(jù)，并從中選擇最新的數(shù)據(jù)，而W+RN就意味著讀取的3個數(shù)據(jù)跟更新的3個數(shù)據(jù)至少有一個是重疊的，所以讀取的3個數(shù)據(jù)中一定存在最新的數(shù)據(jù)，因而就能保證系統(tǒng)是強一致性的。lW+R=N，系統(tǒng)是弱一致性的。6. The following scenario is a distributed file

10、 system which spans multiple datacenters. There are several choices for how to handle network partitions that occur in between datacenters (given below). For each of these choices, tell me: if it violates consistency？(CAP)a. Allow all partitions to process both reads and writes.b. Allow all partitio

11、ns to process reads, but only one special partition (prechosen)to process writes.c. Allow only the partition which has at least a quorum number of servers (measured across all datacenters) to execute writes.d. Until partitions are repaired, allow only reads but no writes.e. Allow only partitions wit

12、h a quorum of servers (measured across all data centers) to execute writes and reads.7. Lamports Logical Clocks, among other things, help make inferences about consistency of replicated data items operated upon concurrently. The following figure shows the time-line diagrams of three processes P, Q a

13、nd R.a. Fill in the logical times for each event (a)(o) in the three processes using the rules of local ordering, send/receive ordering and transitive closure.7.答：(1)從左到右：P ：1， 2，3，4，5，7，8Q ：1，3，4，5，6R：1，5，6(2) False，True，Unknown，F(xiàn)alse，True，Unknownb. Assuming you are given only the logical times for

14、 each event in a process, answer the following True, False or Unknown questions i. Event b happened before event a. ii. Events a, h and m happened concurrently. iii. Event n happened before event c. iv. Events d, k and n occur at the same time instant. v. Event g did not happen before event l. vi. Event o happened after event l. 8. 設(shè)某WEB內(nèi)容緩存系統(tǒng)采用一致性哈希算法進行內(nèi)容分發(fā)管理。其環(huán)形哈希表地址空間大小N=4096，存儲節(jié)點A, B, C, D的哈希值分別為: 13，1025，2047，3011；給定數(shù)據(jù)對象obj1obj14，其ID值分別為：56，256，643，654，726，1365，1276，652，1887，1535，827，2323，892, 1337。哈希值計算方式為： h(id) = (3*id) mod 4096a. 對給定數(shù)據(jù)對象obj1obj14進行哈希計算，按順