数据库理论与技术期终考试复习题-带答案

1、数据库理论与技术复习题1. 考虑用二元联系（图1）对三元联系（图2）的表示：ABECRARCRBBARC 图1图1 图21) 分别给出图1中E，A，B，C，RA，RB和RC的一个实例，这些实例不对应图2中A，B，C和R的任何实例；2) 更改图1中的ER图，引入适当的约束以确保满足约束的E，A，B，C，RA，RB和RC的任何实例都对应于A，B，C和R的一个实例；3) 更改以上的转化以表示在三元联系上的全参与约束；4) 以上表示要求为E创建一个主码属性，试问如何将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）的原因，不存在任何实例对应于E,Ra,Rb,Rc2） 如下图所示：通过引入E 和关系 Ra ， Rb ， Rc之间的全部参与的约束条件，以便在 E 中的每个元组都和A ，B，C有关系。3） 假设A全部参与关系R，则在A和Ra之间引入全部参与约束。4） 将 E看作弱实体集，而将Ra,Rb,Rc看作标志联系集。如下图所示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函数(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. 假设用Bloom filter存放集合S(其中元素个数为34亿),hash函数个数为8,允许的错误率最大为0.

7、001,那么该Bloom filter的位数m最小应为多少?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越大，同一个数据的备份越多，系统相对也就越不

9、容易丢失数据。lW越大，系统的一致性会越高，但更新操作也就越慢。lR越大，系统的一致性会越高，但读操作也就越慢。lW+RN，系统是强一致性的。为什么？举例来说，假设N=6，W=R=3，当一个更新操作完成的时候，它至少更新了6个备份中的3个备份，那么当我们去读取这个数据的时候，因为R=3，所以我们至少得读3个数据，并从中选择最新的数据，而W+RN就意味着读取的3个数据跟更新的3个数据至少有一个是重叠的，所以读取的3个数据中一定存在最新的数据，因而就能保证系统是强一致性的。lW+R=N，系统是弱一致性的。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，False，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. 设某WEB内容缓存系统采用一致性哈希算法进行内容分发管理。其环形哈希表地址空间大小N=4096，存储节点A, B, C, D的哈希值分别为: 13，1025，2047，3011；给定数据对象obj1obj14，其ID值分别为：56，256，643，654，726，1365，1276，652，1887，1535，827，2323，892, 1337。哈希值计算方式为： h(id) = (3*id) mod 4096a. 对给定数据对象obj1obj14进行哈希计算，按顺