查询分解是把分布演算查询映射到一个全局关系的代数查询上。从代数优化看，使用直接分步骤的算法可以获得一个“好的”结果，但是，进一步看未必是最佳的。换句话说，每次选最好的，不见得最终结果是最佳的。就像有一筐苹果，每天选一个质量最好的苹果吃，不见得是最好的吃法。数据定位决定查询涉及哪些数据片，并将分布查询转化成分片查询。......
2023-10-28
分布式数据库本地化-分布式数据库技术
【摘要】：查询优化的本地化分层聚焦于将查询转换成本地数据。一个全局关系可以通过应用重构规则来重构，从而导出一个关系代数程序，其操作数是数据片，这个程序称为本地化程序。将分布查询分配到节点上的自然办法是生成查询，让每个全局关系使用本地化程序来代替。这可以看成是在一棵分布查询的算符树上将叶子用与本地化程序对应的子树来替代。数据水平分片关系的连接也可以简化。
查询优化的本地化分层聚焦于将查询转换成本地数据。本地化分层负责将代数查询翻译成面向物理数据片的形态，将使用存放在分片模式里的信息。
数据片是按照分片规则定义的，可以表达为关系查询。一个全局关系可以通过应用重构规则来重构，从而导出一个关系代数程序，其操作数是数据片，这个程序称为本地化程序。为了简化，我们假设这里的数据片无副本。
将分布查询分配到节点上的自然办法是生成查询，让每个全局关系使用本地化程序来代替。这可以看成是在一棵分布查询的算符树上将叶子用与本地化程序对应的子树来替代。
这个过程不复杂，但前提是这棵算符树已经很好地被约简。下面先讨论分片查询的正则表示问题。
1.限定关系代数和正则表达式
什么是限定关系？限定关系是将一个关系通过限定条件加以扩展，记作［R：qR］。其中：R是一个关系，称为限定关系的主体；qR是一个谓词，称为限定谓词。
显然，也可以将关系R本身看成是一个限定关系，其限定条件为true，即R=［R：true］。
考虑限定关系时的关系代数，称为限定关系代数。我们用一些规则来描述。
限定关系代数规则1：σF［R：qR］⇒［σF R：F∧q R］。
证明略。
这个规则的含义是，如果对一个限定条件为qR的关系数据片实施选择运算，且选择谓词是F，则可看成是对一个同时满足F和qR的关系实施选择。
其意义在于，对那些限定条件F∧qR为假（false）的关系片，可以不必实施真正的选择操作，直接用空集（∅）代入即可。
限定关系代数规则2：∏A：［R：qR］⇒［∏A R：qR］。
证明略。
这个规则反映了一种不变性。
限定关系代数规则3：［R：q R］×［S：qS］⇒［R×S：q R∧qS］。
证明略。
限定关系代数规则4：［R：q R］-［S：qS］⇒［R-S：q R］。
证明略。
这个规则的意义在于两个限定关系的差可以用这两个关系的差表示，且必须满足被减数的限定条件。
限定关系代数规则5：［R：qR］∪［S：qS］⇒［R∪S：qR∨qS］。
证明略。
限定关系代数规则6：［R：q R］∞F［S：qS］⇒［R∞F S：qR∧qS∧F］。
证明：
［R：q R］∞F［S：qS］⇒
σF（［R：qR］×［S：qS］）⇒
σF［R×S：q R∧qS］⇒
［σF（R×S）：qR∧qS∧F］⇒
［R∞F S：qR∧qS F］
限定关系代数规则7：［R：q R］∝F［S：qS］⇒［R∝F S：qR∧qS∧F］
证明：
［R：q R］∝F［S：qS］⇒
∏Attr（R）（［R：qR］∞F［S：qS］）⇒
∏Attr（R）［R∞FS：q R∧qS∧F］⇒
［∏Attr（R）（R∞FS）：qR∧qS∧F］⇒
［R∝F S：qR∧qS∧F］
这个规则的优点是，如果限定条件为矛盾，对应的集合为空，则可以不执行该操作。
下面是可以进一步约简的公式（∅表示空集）。
●σF（∅）↔∅；
●∏A（∅）↔∅；
●R×∅↔∅；
●R∪∅↔R；
●R-∅↔R；
●∅-R↔∅；
●R∞F∅↔∅；
●R∝F∅↔∅；
●∅∝F R↔∅。
2.约简
1）基本水平分片的约简
如前所述，基于选择谓词的关系水平分片负责定义关系的分布。
【例7.9】 假设关系EMP（eno，ename，title）可以水平分成三个数据片，即EMP1、EMP2和EMP3，其定义如下：
EMP1=σeno≤″E3″（EMP）
EMP2=σ″E3″＜eno≤″E6″（EMP）
EMP3=σeno＞″E6″（EMP）
水平分片关系的本地化重构程序是该关系所有数据片的并，即
EMP=EMP1∪EMP2∪EMP3
这样一种水平分片关系可以简化选择运算和连接运算。
（1）使用选择运算来约简。
如果数据片的选择运算谓词与其定义分片限定谓词相矛盾，则其结果为一个空关系。假设关系R水平分片为R1，R2，…，Rw，其中Rj=σpj（R），则相应的规则可以描述如下：
其中：pi和pj为选择谓词；x表示元组；p（x）表示x满足谓词p。
如果选择的限定谓词和数据片的分片谓词相矛盾，则结果为空集。
优化规则3：尽可能地将选择运算往算符树的叶子方向下推，然后使用限定关系代数，如果发现归并后的限定条件有矛盾，则用空集代入。
【例7.10】 假设查询为σdeptno=1 DEPT，则它可以用图7.10表示。
利用优化规则2，使用交换律，将选择运算下推到并运算下面，结果如图7.11所示。
对其中参与并运算的三棵子树分别使用优化规则3，结果如下：
σdeptno=1［DEPT1：deptno≤10］⇒［DEPT：deptno=1∧deptno≤10］
σdeptno=1［DEPT2：10＜deptno≤20］⇒［DEPT：deptno=1∧10＜deptno≤20］=∅
σdeptno=1［DEPT3：deptno＞20］⇒［DEPT：deptno=1∧deptno＞20］=∅
所以例7.10可以简化成如图7.12所示。
图7.10 例7.10的图示
(www.chuimin.cn)
图7.11 将选择运算下推到并运算下面的算符树
图7.12 例7.10的演变
显然，结果让这个查询大大简化了。
（2）水平分片关系连接运算的简化。
数据水平分片关系的连接也可以简化。一个分片关系（如R）可以通过并运算来重构，所以两个关系R和S的连接可以表述为：
（R1∪R2）∞F S=（R1∞F S）∪（R2∞F S）
其中：Ri（i=1，2）是R的数据片，S是另外一个关系。
利用限定关系谓词和连接运算谓词的“与”操作，判定结果是否为“假”来简化连接运算。
先来看一个规则：Ri∞FSj=∅if∀x in Ri，∀y in Sj：（pi（x）∧pj（y）∧F）
这个规则是显然的，证明略。
因此，可以获得两个新的优化规则。
优化规则4：使用限定关系代数对连接运算进行估算，如果发现限定条件有矛盾，则用空集代入。
优化规则5：为了处理分布连接，全局关系中出现的并运算（表示数据片的重组）必须往树的根部移动，并移到希望实施分布连接的运算上面。
【例7.11】 假设有查询σsnum（SUPPLY∞SUPPLIER），那么该查询可以用图7.13所示的算符树来表示。
图7.13 例7.11查询的算符树
这个查询可以用一个简单连接图表示，因为SUPPLY是SUPPIER的导出水平分布。因此，这个连接可以分解为两个连接：
SUPPLIER1∞SUPPLY 1
SUPPLIER2∞SUPPLY2
结果如图7.14所示。
图7.14 优化后的查询的算符树
2）垂直分片上的约简
垂直分片是基于投影操作实现的。垂直分片关系的重构是通过连接运算实现的。我们来看一个例子。
【例7.12】 假设关系EMP是一个垂直分片关系，分片情况如下：
EMP1=Πeno，ename（EMP）
EMP2=Πeno，title（EMP）
其重构为：EMP=EMP1∞eno EMP2。
类似于水平分布，垂直分片上的查询可以通过找出无用的中间关系和删除产生的子树来约简。如果在垂直数据分片上的投影属性和分片限定属性间（除键属性外）没有公共交集，则为无效。
【例7.13】 假设有如下查询：
Select ename
from EMP
图7.15 垂直分片的约简
图7.15（a）表示为在EMP1和EMP2上的等价查询。将投影运算和连接运算交换（即投影在eno、ename上），可以发现EMP2上的投影是无用的，因为EMP2中没有ename属性，结果如图7.15（b）所示。
3）导出分片的约简
关系R是一个从关系S中导出的水平分割关系，它们之间的连接如果按导出连接属性实施，就构成一个简单连接图，形成一个一一对应的关系。
【例7.14】 下面的EMP_PROJ是一个从EMP导出的水平分割关系，其关系模式是EMP_PROJ（eno，pno，resp，dur）：
EMP_PROJ1=EMP_PROJ∞eno EMP1
EMP_PROJ2=EMP_PROJ∞eno EMP2
而EMP的分片情况如下：
EMP1=σtitle=Programmerc（EMP）
EMP2=σtitle≠Programmer（EMP）
显然：EMP_PROJ=EMP_PROJ1∪EMP_PROJ2。
这样，EMP_PROJ1∞EMP2是矛盾的，故无用。同理，EMP_PROJ2∞EMP1是矛盾的，故无用。因此，两个关系在eno上的连接是一个简单连接图。
4）混合分片的约简
【例7.15】 关系EMP的混合分片如下：
EMP1=σeno≤4（∏eno，ename（EMP））
EMP2=σeno＞4（∏eno，ename（EMP））
EMP3=∏eno，title（EMP）
关系的重构就变成：
EMP=（EMP1∪EMP2）∞eno EMP3
混合分片可以使用水平分片、垂直分片和导出分片约简。使用规则小结如下。
①除水平分片限定条件和选择条件矛盾的部分，还可用空关系代入。
②去除垂直分片投影上无用的部分。
③将并运算移到连接运算之后，用和空关系运算的规则进行约简。
【例7.16】 SQL语句如下：
Select ename
from EMP
where eno=5
混合分片的约简如图7.16所示。
图7.16 混合分片的约简
图7.15（a）的下部表示这个混合分片关系的重构：通过并运算将水平分割的EMP1和EMP2重构成一个临时数据片，然后通过连接运算和EMP3一起重构成全局关系。从图中可以看出，目标是投影到雇员姓名上，因此这与EMP1和EMP2有关。
按照限定关系谓词，可以小结规则如下：
①σeno=5［EMP1：eno≤4］⇒
σeno=5［EMP：eno≤4∧eno=5］⇒∅
②σeno=5［EMP1：eno＞4］⇒
σeno=5［EMP：eno＞4∧eno=5］
这里，eno＞4∧eno=5为真，故运算可继续进行。
有关分布式数据库技术的文章
- 详细阅读
-
分布式数据库技术-分布式数据库技术详细阅读
Oracle公司的OPS环境比一般的（单实例）Oracle环境复杂得多。不同结构下的OPS的实施略有不同。图14.23OPS体系结构为了利用这些特性，需要专业人员合适的设计以及恰当的手工配置。下面对有些关键问题进行简单讨论，讨论中会涉及一些Oracle系统专用的术语，读者可参阅Oracle公司的相关文档。DLM与Oracle进程一起工作并相互通信。DLM相关的初始化参数在每个实例的SGA[12]中分配必要的结构以处理消息机制、封锁与实例相关的Cache管理，这样就为各种Oracle进程操纵提供了基础。......
2023-10-28
-
保障数据安全：分布式数据库技术详细阅读
与数据库安全系统打交道的人员可以分为两类：数据库管理员和普通用户。DBA要对安全负责，所以他（们）要创建授权规则，定义谁可以使用哪部分数据，以及如何使用。图13.1数据库安全系统由图13.1可知，数据库安全系统里存放着授权规则，在每次数据库存取时强制满足其规则。从完整性方面考虑，数据库安全可以包含以下两方面。1）设计阶段的数据库安全在设计阶段必须关注数据库的安全性。DBA负责处理整个数据库系统里的用户账号和口令。......
2023-10-28
-
分布式数据库设计技术详细阅读
图3.1软件开发过程数据库设计的过程与软件开发的过程类似。下面先来看一下集中式数据库设计的情况。在分布式数据库系统中，集中式数据库设计的问题依然存在，且有以下两个新的问题需要考虑。这个过程就是确定如何将全局关系划分成水平、垂直或者混合的数据片。数据片的分配，即决定数据片如何映射到物理镜像上，决定如何复制数据片。数据片的分配问题则研究已久，当然，过去研究的则是“文件分配”问题。......
2023-10-28
-
分布式数据库技术之CORBA详细阅读
自1995年以来，基于CORBA软件的企业级应用发展迅猛。CORBA是OMG随着硬件和软件产品的快速增长，针对互操作性的需要而提出的。CORBA 2.0于1994年12月被提出，它定义了不同供应商的ORB怎样才能实现真正的互操作性。图12.4OMA体系结构OMA体系结构主要包括以下几部分。ORB用于发现与该请求对应的对象实现，对所要求的所有机制做出响应，准备好对象实现以响应请求，并完成请求所需要的数据通信。由图12.5可知，客户端通过ORB向对象实现发送请求。......
2023-10-28
-
OracleRAC分布式数据库技术详细阅读
前面提及的OPS是Oracle 6.0中引入的，RAC源自OPS，但作为新的产品推出。一个4节点的集群结构如图14.24所示。图14.24一个4节点的集群结构RAC起源于OPS，在Oracle 6.0.35版本中引入。最初只适用于Digital VAX/VMS集群使用Oracle开发的分布式封锁管理器。从Oracle 9.0.1开始，OPS重新改为RAC可选项。在商业上，RAC已是一个完整的新产品。然而在技术上，OPS和RAC的一个重要区别是超高速缓存相关性。OPS里，实例间的块协调由PCM处理。Oracle 8i引入了Cache Fusion PhaseⅠ，部分淘汰了磁盘ping。......
2023-10-28
-
分布式数据库技术：MapReduc详细阅读
Map Reduce是一个编程模型，用于对数据敏感的通用目标实现并行处理。更重要的是，Map Reduce程序本质上是并行运行的，其优势在于能处理大规模数据集。表18.1关系型数据库和Map Reduce的比较Map Reduce和关系型数据库的一个区别在于，它们所操作的数据集的结构化程度不同。换句话说，Map Reduce输入的键和值并不是数据固有的属性，而是由分析数据的人员来选择的。但是在不久的将来，关系型数据库系统和Map Reduce系统之间的差异很可能变得模糊。......
2023-10-28
-
IPv6：分布式数据库技术详细阅读
图20.1TCP/IP协议的分层与OSI模型的对比及层次传递的对象图20.1展示了TCP/IP与OSI模型的层次对应关系和各层传递的对象，并列出了TCP/IP的主要协议及其依赖关系。因此，IP协议在TCP/IP协议组中处于核心地位。表20.1五类IPv4地址还有一些特殊的IP地址如下。......
2023-10-28
相关推荐