分布式数据库习题.docx

资源描述

分布式数据库习题.docx

《分布式数据库习题.docx》由会员分享，可在线阅读，更多相关《分布式数据库习题.docx（33页珍藏版）》请在冰点文库上搜索。

分布式数据库习题.docx

分布式数据库习题

第一章

1.1请用自己的语言定义下列分布式数据库系统中的术语：

全局/局部数据

全局数据是指参与全局应用，可被多个站点上的应用访问的数据；

局部数据是指只提供本站点的局部应用所需要的数据。

全局/局部用户（应用）

在分布式数据库系统中，一个用户或一个应用如果只访问他注册的那个站点上的数据称为局部用户（应用）。

如果访问涉及两个或两个以上站点中的数据，称为全局用户（应用）。

全局/局部DBMS

全局数据库系统是协调全局事务的，协调各局部DBMS以完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复功能的数据库管理系统。

局部数据库管理系统位于局部场地上，是为建立和管理局部数据库，提供场地自治能力，执行局部应用及全局查询的子查询的数据库管理系统。

全局/局部DB

全局数据库（GDB）是指从整个系统角度出发，由全局数据库管理系统进行管理的数据库，它由各个局部数据库逻辑组合而成；

局部数据库（LDB）是指从各个站点的角度出发，由局部数据库管理系统进行管理的数据库，它由全局数据库的某种逻辑分割而成。

全局外模式

是全局应用的用户视图，是全局概念模式的子集，也称全局视图。

全局概念模式

描述分布式数据库中全局数据的逻辑结构和数据特性，是分布式数据库的全局概念视图。

分片模式

描述全局数据的逻辑划分。

每一个全局关系可以分为若干不相交的部分，每一部分称为一个片段，分片模式定义片段以及全局关系到片段的映像。

分配模式

分配模式定义片段的存放结点。

根据选定的数据分布策略，定义各片段的物理存放站点，即定义片段映像的类型，确定分布式数据库是冗余的还是非冗余的，以及冗余的程度。

局部概念模式

是全局概念模式的子集，对每个站点来说，在该站点上全部物理映像的集合就称为该站点上的局部概念模式。

1.2采用分布式数据库系统的主要原因是什么？

分布式数据库系统适合于单位分散的部门，允许各个部门将其常用的数据存储在本地，实施就地存放本地使用，从而提高响应速度，降低通信费用。

采用分布式数据库的原因主要有两方面：

（1）集中式数据库系统的不足：

数据按实际需要已经在网络上分布存储，如果再采用集中式处理，势必造成附加成本和通信开销；应用程序集中在一台计算机上运行，一旦该计算机发生故障，将会影响整个系统的运行，可靠性不高；集中式处理导致系统的规模和配置都不够灵活，系统的可扩展性较差。

（2）分布式数据库系统的优点：

具有灵活的体系结构；适应分布式的管理和控制机构；经济性能优越；系统的可靠性高、可用性好；局部应用的响应速度快；可扩展性好，易于集成现有系统。

1.3分布式数据库系统可分为那些类？

（1）按局部数据库数据管理系统的数据模型分类：

同构型DDBS（包括两种：

同构同质型。

同构异质型），异构型DDBS

（2）按分布式数据库系统的全局控制系统类型分类：

全局控制集中型DDBS，全局控制分散型DDBS，全局控制可变型DDBS

1.5分布式DBMS具有哪些集中式DBMS不具备的功能？

（1）物理分布性：

分布式数据库中的数据不是存储在一个站点上，而是分散存储在由计算机网络联结起来的多个站点上。

（2）逻辑整体性：

分布式数据库中的数据物理上是分散在各个站点中的，但这些分散的数据逻辑上却是一个整体。

（3）站点自治性：

站点自治性也称场地自治性，各站点上的数据由本地的DBMS管理，具有资质处理能力，完成本站点的应用（本地应用）。

（4）集中与自治相结合的控制机制：

同一站点上的用户可共享本站点上局部数据库中的数据，以完成局部应用；分布式数据库系统上的用户都可共享在分布式数据库系统的各个站点上存储的数据，以完成全局应用。

（5）适当增加数据冗余度：

在集中式数据库中，尽量减少冗余度是系统目标之一。

而在分布式系统中却通过冗余数据提高系统的可靠性、可用性和改善系统性能。

（6）事务管理的分布性：

数据的分布性必然造成事务执行和管理的分布性。

即，一个全局事务的执行可分解为在若干个站点上子事务（局部事务）的执行。

“什么时候需要进行数据分片和数据复制”。

数据分片：

全局数据库是由各个局部数据库逻辑组合而成，数据库中的一个关系描述了某些数据之间的逻辑相关性，但不同站点的用户需要该关系中的元组可能不同。

这就需要对这个关系进行分割，并将分割后的片段存放在相应的站点上。

数据复制：

当一个分布式数据库中用户数量较大，地理分布较广，而且需要实时地访问相同数据时可以采用数据复制技术，它通过将这些共享数据复制到位于不同地点的多个数据库中，从而实现数据的本地访问，减少了网络符合，并提高了数据访问的性能，而且通过对数据库中的数据定期同步的更新，从而确保了所有的用户使用同样的、最新的数据。

1.7在分布式数据库系统中，为什么要对数据进行分片？

什么是关系的片段？

关系的片段有哪些主要类型？

对数据分片的目的是产生一个对全局数据合适的划分方案，使用这种方案得到的片段作为分布式数据库中数据的分配和存储单位时，不但能够减少应用中的操作量，而且能够对于应用具有最大可能的本地性，即使得各片段位于其使用最多的站点。

关系的片段：

对数据库管理系统中的关系进行分割，将分割后得到的各部分元组，就称为该关系的逻辑片段。

关系的片段主要类型有:

（1）水平片段：

按一定的条件把全局关系的所有元组划分成若干不相交的子集，每个子集为关系的一个片段。

也是通过对一全局对象的实例（或元组）进行选择得到的子集构。

（2）垂直片段：

把一个全局关系的属性集分成若干子集，并在这些子集上做投影运算，每个投影为垂直分片。

也是通过将全局对象在其属性子集上进行投影得到的。

（3）混合分片：

将水平分片与垂直分片方式综合使用则为混合分片。

第二章

2.1概述分布式数据库系统的创建方法、方法特点和适用范围。

分布式数据库系统的创建方法即分布式数据库系统的实现方法，大致可分为两种：

组合法和重构法。

（1）采用组合法创建分布式数据库系统

组合法也称集成法，这是一种自底向上（bottom—up）的创建方法。

它是利用现有的计算机网络和独立存在于各个站点上的现存数据库系统，通过建立一个分布式协调管理系统，将它们集成为一个统一的分布式数据库系统。

特点：

这种方法由于是利用现存的网络和现存的数据库系统，仅仅需要建立一个分布式协调管理系统。

因此，相对来说，如果该系统不是很大的话，其工作量可能会比较小，实现的周期会短些，花费的人力、物力会少些，用户也比较容易接受，因为它有利于保护现有的投资。

适用范围：

采用组合法的分布式数据库系统往往是异构或同构异质的分布式数据库系统。

（2）采用重构法创建分布式数据库系统

重构法是根据系统的实现环境和用户需求，按分布式数据库系统的设计思想和方法，采用统一的观点，从总体设计做起，包括各站点上的数据库系统，重新建立一个分布式数据库系统。

特点：

这种方法的优点在于，可以按照统一的思想来考虑分布式数据库系统中的各种问题，有效地解决分布式数据库系统的数据一致性、完整性和可靠性。

但是花费的人力、物力会比较多，研制周期也比较长，系统建设的代价会比较大。

在实际应用中，究竟应该采用哪种方法，要根据具体情况做具体分析后决定。

适用范围：

采用重构法创建的分布式数据库系统，通常是同构异质，甚至是同构同质的分布式数据库系统。

设计的主要目标是什么？

分布式数据库设计的目标除包括集中式数据库设计中的目标外，还要包括以下几点：

（1）分布式数据库的本地性或近地性

分布式数据库系统中最重要的目标（至少在使用广域网的情况下，以及某些使用局域网的情况下）是尽量减少对网络的利用，即尽可能减少站点之间的通信次数和通信量。

所以，分布式数据库设计中的一个主要原则是使数据和应用实现最大程度的本地性。

本地性的优点不仅仅减少了远程访问的次数，而且简化了对该应用执行的控制。

（2）控制数据的适当冗余

控制数据的适当冗余是分布式数据库系统设计的又一个目标。

分布式系统在可用性和可靠性方面优于非分布式系统，其原因之一是因为分布式数据库系统中存在数据的适当冗余。

（3）工作负荷分布

分布式计算机系统的一个重要特征是把工作负荷分布在网络中的各个站点上。

分布工作负荷的目的是充分利用每个站点计算机的能力和资源，以提高应用执行的平行程度，从而提高系统的性能。

（4）存储的能力和费用

数据库的分布会受到各站点的存储能力的影响。

在网络中可以有专门用于存储数据的站点，也可以有完全不支持大容量存储的站点。

上述的设计目标都要达到是非常困难的，因为这会使优化模型变得非常复杂。

因此，可以将上面的某些特征考虑为约束条件而不是目标。

2.3概述分布式数据库设计的关键问题及其解决方法。

作为数据库系统设计的核心部分是数据库设计，数据库设计的主要问题是模式（也称概念模式，描述数据库应用所使用的全部数据）和内模式（也称物理模式，描述概念模式映射到存储区域，并确定合适的存取方法）的设计。

这两个问题在分布式数据库中变为全局模式设计和每个站点的局部数据库设计的问题，其中的关键是数据库的全局模式应如何划分：

并映射到合适站点上。

这就产生了分布数据库设计所特有的两个新问题：

数据的分片设计和片段的位置分配设计。

分布式数据库的分布设计要求确定数据的分片和片段的分配。

分片是指把一全局对象（实体或关系）细分成若干逻辑片段的过程；分配是指把各片段映射到一个或多个站点的过程，片段是最合适的数据分配单位。

2.6数据分片应遵守哪些基本原则？

数据分片有哪些基本类型和方法？

分片方法，必须遵守如下规则：

若R={R1，R2，…，Rn}满足：

1）完整性（completeness）条件：

如果a∈R，则必有a∈Ri，i=l，2，…，n

2）可重构（reconstructed）条件：

R=∪Ri，（水平分片）或R=∞Ri，（垂直分片）

3）不相交（disjoint）条件：

Ri∩Rj=φ，i≠j，i，j：

=1，2，…，n（水平分片）

Ri∩Rj=主键属性，i，j=1，2，…，n（垂直分片）

有两种基本的数据分片方法：

（1）使用水平分片方法得到水平片段，水平片段是通过对一全局对象的实例（或元组）进行选择得到的子集构成。

水平分片是对全局关系执行“选择”操作，把具有相同性质的元组进行分组，构成若干个不相交的子集。

水平分片的方法可归为初级分片（primaryfragmentation）和导出分片（derivationfragmentation）两类。

（2）使用垂直分片方法得到垂直片段，垂直片段是通过将全局对象在其属性子集上进行投影得到的。

一个全局关系的垂直分片是通过“投影”操作把它的属性分成若干组。

确定一全局关系R的垂直分片需要根据应用以“同样方式”（例如具有相同的使用频率）访问的属性来进行分组。

这里把垂直分片问题和垂直群集（vetticalclustering）问题区分开来，垂直分片的组必须只焦基个键属性上重叠，其他属性不可重叠，而垂直群集的组在其他属性上也可以重叠。

通过交替水平分片与垂直分片，可以产生混合分片。

2.7为什么说在关系型分布式数据库中使用导出式水平分片，使关系之间的连接变得更加容易？

试举一例。

全局关系的导出式水平分片不是以其自身的属性性质为基础，而是从另一个关系的属性性质或水平片段推导出来的。

采用导出分片可使片段与片段之间的“连接”（join）变得更容易。

例：

设全局关系SC（S#．C#，SCORE）

S（S#，SNAME，AGE，SEX）

若要将SC划分为男生的各门课成绩和女生的各门课成绩。

这就不可能从SC本身的属性性质来执行选择，必须从关系S的属性性质或水平片段来导出。

definefragmentSC1as

selectSC．S#，C#，SCOREfromSC，S

whereSC．S#=S.S#andSEX=’M’

definefragmentSC2as

selectSC.S#，C#，SCOREfromSC，S

whereSC.S#=S.S#andSEX=’F’

如果S已经进行水平分片，分为SF、和SM，分别为男生全体和女生全体，则上述的片段定义可以基于片段SF和SM导出：

definefragmentSC1as

select*fromSCwhereS#in（selectSF.S#fromSF）

definefragmentSC2as

Select*fromSCwhereS#in（selectSM.S#fromSM）

由此可见，使用导出式水平分片，使关系之间的连接变得更加容易。

这是因为可将连接条件代之以子查询，从而使它变为一般的判别条件。

2.8采用DATAID-D方法的分布式数据库设计与传统的集中式数据库设计在步骤和内容上有什么不同？

DATAID—D是作为集中式数据库设计DATAID一1方法论的扩充而构造的，后者分成四个阶段：

需求分析、概念设计、逻辑设计和物理设计。

DATAID—D要求对其增加两个阶段：

分布要求分析阶段和分布设计阶段

1）分布要求分析阶段：

需要这一阶段是为了收集关于分布的信息，如水平分片的划分谓词，每一应用在各站点激活的频率等。

为了收集关于数据和应用分布的信息，必须从概念设计阶段的某些结果出发来收集关于分布要求。

因此，分布要求分析阶段将位于概念设计阶段之后。

2）分布设计阶段：

这一阶段始于全局数据库模式的规格说明和所收集的分布要求，然后产生全局数据的分片模式和片段的位置分配模式，分配模式描述了分配在各站点上的数据情况。

所示的公司数据库的分片和分布。

假设该公司有三个计算机站点，站点B和C分别属于部门2和3.现在希望在站点B和C上分别频繁访问EMPLOYEE和PROJECT表中有关工作在该部门的雇员和该部门管辖的项目信息。

雇员信息主要是指EMPLOYEE表的NAME，ESSN，SALARY和SUPERSSN属性。

站点A供公司总部（部门1）使用，经常存取为保险目的而记录的DEPENDENT信息外，还定期地存取所有雇员和项目的信息。

根据这些给出的要求，对COMPANY关系数据库中关系进行分片和分布。

EMPLOYEE

FNAME

MINIT

LNAME

ESSN

BDATE

ADDRESS

SEX

SALARY

SUPERSSN

DNO

DEPARTMENT

DNAME

DNO

MGRSSN

MGRSTARTDATE

DEPT_LOCATION

DNO

DLOCATION

PROJECT

PNAME

PNUMER

PLOCATION

DNO

WORKS_ON

ESSN

PNO

HOURS

DEPENDENT

ESSN

DEPENDENTNAME

SEX

BDATE

RELATIONSHIP

图2.12COMPANY关系数据库模式的一个可能的关系数据库状态（主码用下标线标出）

解：

根据给出的要求，图2.12中的整个数据库可以被存储在站点A。

为了确定将要复制到站点2和3上的片段，先根据DEPARTMENT表的主码DNO的值进行水平分片，然后基于外码部门号（DNO）将导出的片段应用到关系EMPLOYEE,PROJECT和DEPT_LOCATIONS土，再在刚才得到的EMPLOYEE片段上进行垂直分片，得到只含属性{NAME,ESSN,SALARY*SUPERSSN,DNO）的片段。

图2.13给出了EMPD2和EMPD3的混合分片，它包括了分别满足条件DN0=2和DN0=3的EMPLOYEE元组。

类似地，PROJECT,DEPARTMENT和DEPT-LOCATIONS都按部门编号进行水平分片，这些片段根据其相应的部门号分别存储在站点B和C上，如下图所示。

EMPD5

FNAME

MINIT

LNAME

ESSN

SALARY

SUPERSSN

DNO

John

Simth

123456789

20000

333445555

Franisa

Wong

333445555

10000

888665555

Reminia

Naraya

666884444

15000

333445555

Joyee

English

453453453

20000

333445555

DEP5

DName

DNO

MGRSSN

MGRSTARTDATE

Research

333445555

2003-05-22

DEP5_LOC5

DNO

LOCATION

Bellaire

Sugarlnd

Housten

PROJS55

PNAME

PNUMBER

PLOCAION

DNO

ProductX

Bellaire

ProductY

Sugarlnd

ProductZ

Housten

DEP5_LOCS

ESSN

PNO

HOURS

123456789

666884444

453453453

333445555

〔a）站点B上的对应部门2的关系片段

现在需要对WORKS_ON关系进行分片，并且确定哪些WORKS_ON片段要存储在站点B和C上口这时面临这样一个问题，WORKS_ON中的属性没有一个可以直接指明每个元组所属的部门。

实标上WORKS_ON中的每个元组与雇员e和项日P相联系。

我们既可以以e工作的部门也可以以管辖P的部门d'来分片WORKS_ON表。

如果对表WORKS_ON的所有元组增加一个d_d'的限制，分片就会变得更加容易，即雇员只能为那些他所在部门管辖的项目工作。

然而，在图2.12中的数据库没有给出这样的限制。

所以，对此可以先以雇员工作的部门（用条件C表述）来分片WORKS_ON然后进一步以管辖雇员工作项目的部门来分片，如下图所示。

EMPD4

FNAME

MINIT

LNAME

SSN

SALARY

SUPERSSN

DNO

Ahcia

Zelaya

999887777

25000

987654321

Jennifer

Wallace

987654321

43000

888665555

Ahmad

Jabbar

999887777

25000

987654321

EMPD4

FNAME

MINIT

LNAME

ESSN

SALARY

SUPERSSN

DNO

John

Simth

123456789

20000

333445555

Franisa

Wong

333445555

10000

888665555

Reminia

Naraya

666884444

15000

333445555

Joyee

English

453453453

20000

333445555

DEP4

DName

DNUMBER

MGRSSN

MGRSTARTDATE

Administr

987654321

2003-01-01

DEP4_LOCS

DNUMBER

LOCATION

Statland

DEP4_LOCS

ESSN

PNO

HOURS

333445555

999887777

987987987

987654321

PROJS55

PNAME

PNUMBER

PLOCAION

DNO

Computer

Statland

Newbener

Statland

〔b）站点B上的对应部门4的关系片段

在上图中，片段G1,G2和G3的并集给出了为部门2工作的雇员的所有WORKS_ON元组。

同样地，片段G4,G5和G6的并集给出了为部门3的雇员的所有WORKS_ON元组。

另一方面，片段GI!

LI`I和G7的并集给出了被部门2管辖的项目的所有WORKS_ON元组。

因此，可以把片段G1,G2,G3,G4和G的并集放到站点B上，把片段G5,G5,G6,G2和G8的并集放在站点C上，可以看到片段G2和G4在两个站点上均被复制。

这就清楚地论证了对于大型数据库而言，数据的分片和分配是一个多么复杂的问题。

第三章

3.3概述基于关系代数等价变换的查询优化算法的基本原理和实现步骤。

基本原理：

把查询问题转变为关系代数表达式,分析得到查询树（语法树）,进行从全局到片段的变换得到基于片段的查询树,然后利用关系代数变换规则的优化算法,尽可能先执行选择和投影操作.这样,一方面可以减少其后操作的操作量,另一方面可以减少操作次数.对该查询树进行优化,从而达到查询优化的目的.

实现步骤：

1、将一个查询问题转换成关系代数表达式

2、从关系代数表达式到查询树的变换：

对一个关系代数表达式进行语法分析，可以得到一颗语法书，即树的叶子是已知的关系（或片段）、树的结点是关系操作符、节点是按代数表达式中的操作顺序组成的一组关系操作符。

3、从全局查询到片段查询的变换：

在具有分片透明性的系统中，这个变换的典型方法是：

把基于全局关系的查询树中的全局关系名用其重构该全局关系的各片段名替换，变换成相应在片段上的查询树。

4、利用关系代数等价变换规则的优化算法，对片段上的查询树进行优化处理，最后达到优化查询的目的。

3.4概述基于半连接算法查询优化的基本原理和使用情形。

原理：

经半连接操作，可减少操作关系的数据量，从而减少站点间数据的传输量。

适用情况：

如果只需要一个关系中的一小部分元组参与和另一个关系连接的话，这是一个使数据传输量最小化的非常有效的方案。

此时，T半

3.5概述基于直接连接算法查询优化的基本原理和适用情形。

基本原理：

基于直接连接算法的查询优化处理中的站点依赖算法、分片和复制算法。

站点依赖和数据复制算法，以及Hash划分算法，主要是使得连接操作的数据传送量小（最好是无数据传送）和负载均衡，从而达到优化的目的。

使用情形：

直接连接查询优化的算法有四种，通过比较，站点依赖算法的数据传送量最小（实际上没有），连接数据量最小切利用索引，因而能获得最佳性能。

其次是Hash划分算法，最后是片段和复制算法。

尽管如此，站点依赖算法只有在给出适当的可用语义信息时才使用；Hash划分算法要求相对均匀的数据分布来得到良好的性能，最坏的情况下，两个关系可能被映射到同一个站点，而达不到负载均衡；在某个关系已经复制在包含其他关系片段的站点中，可在本地立即进行无数据传送处理，这种场合下使用分片

展开阅读全文