2000-2001学年第二学期数据库系统原理期末试题

(笔试部分)

 

二○○一年6月28日

 

姓名_________________    专业______________   成绩___________________

 

1．(5 point) 说明以下定义的含义：

       (1) TYPE POINT /* geometric points */

                     POSSREP  CARTESIAN ( X RATIONAL, Y RATIONAL)

                     POSSREP  POLAR (R RATIONAL, THETA RATIONAL)

       (2) THE_X ( P )

 

2．(15 point) 为什么要引入分组（group）和分组还原（ungroup）操作？对以下GROUP和UNGROUP操作的可逆性讨论，判断以下命题正误，对不成立的命题，补充其成立的条件：

       （1）如果通过某种途径对关系r分组，总会有一个可逆的撤消分组操作使我们重新得到r？为什么？

       （2）如果对某个关系r撤消了分组，一个可逆的分组一定存在？为什么？

 

3．(15 point) 证明Darwen的“通用一致性定理”。在证明时运用了什么规则（即自反律，增广律，传递律，蕴涵自含规则，分解规则和合并规则）？哪些规则可以看作是该定理的特例？

 

4．(10 point) C是一个俱乐部，关系变量R{A,B}满足，当且仅当a和b都是C的一员时元组（a,b）才出现在R中。那么R满足什么样的FD，MVD和JD？R属于第几范式？

 

5．(10 point) 为什么提出“逆规范化”？什么是“正交设计”？

 

6．(10 point) 假设关系r正好包含下列元组：

                       (  6,    5,     4   ）

                       ( UNK,  5,     4   )

                       (  6,   UNK,   4   )

                       ( UNK,  UNK,  UNK)

 

（1）假设（a）这三个属性以上面所示的顺序从左到右依次叫作A，B和C，且（b）每一个属性都是INTERGER类型。若V是r上的范围变量，则请说出下列表达式的真值：

a.      EXISTS V (V.B>5)

b.     EXISTS V (V.B>2 AND V.C>5)

c.     EXISTS V (MAYBE(V.C>3))

d.     EXISTS V (MAYBE(IS_UNK(V.C)))

e.      FORALL V (V.A>1)

f.      FORALL V (V.B>1 OR IS_UNK(V.B))

g.     FORALL V (MAYBE (V.A>V.B))

（2）严格地说，IS_UNK操作是多余的。为什么？

 

7．(10 point) Consider the following relations:

       Emp ( eid: integer, ename: varchar, sal: integer, age: integer, did: integer)

       Dept (did: integer, budget: integer, floor: integer, mgr_eid: integer)

Salaries range from $10,000 to $100,000, age vary from 20 to 80, each department has about five employees on average, there are 10 floors, and budgets vary from $10,000 to $1,000,000. You can assume uniform distributions of values.

For each of the following queries, which of the listed index choices would you choose to speed up the query? If your database system does not consider index-only plans, how would you answer change? Explain briefly.

(1)    Query: Print ename, age, and sal for all employees.

(a)    Clustered, dense hash index on <ename, age, sal> fields of Emp

(b)    Unclustered hash index on <ename, age, sal> fields of Emp

(c)    Clustered, sparse B+ tree index on <ename, age, sal> fields of Emp

(d)    Unclustered hash index on <eid, did> fields of Emp

(e)    No index

(2)    Query: Find the dids of departments that are on the 10th floor and that have a budget of less than $15,000.

(a)    Clustered, dense hash index on the floor field of Dept.

(b)    Unclustered hash index on the floor fields of Dept.

(c)    Clustered, dense B+ tree index on < floor, budget> fields of Dept

(d)    Clustered, sparse B+ tree index on the budget field of Dept

(e)    No index

(3)    Query: Print the average salary for each department.

(a)    Clustered, sparse B+ tree index on the did fields of Emp.

(b)    Clustered, dense B+ tree index on the did fields of Emp.

(c)    Clustered, dense B+ tree index on the <did, sal> fields of Emp.

(d)    Unclusterd hash index on <did, sal> fields of Emp.

(e)    Clustered, dense B+ tree index on the did fields of Dept.

 

8. (10 point) Outline the following algorithms:

(1)    semi naïve evaluation in logic DB.

(2)    Select-Block-Configuration for path expression optimization in OODB

 

9. (15 point) Discussion:

(1)    Characteristics of Semistructured Data.

(2)    XML v.s. Semistructured Data: Similarities and Differences.

(3)    Expressing the query in WebSQL: Find all web pages that contain “database” and are reachable through zero or more local links from any page that contains “computer science”.

(4)    XML storage methods.

 

(中国人民大学信息学院， 此试卷考后收回)