分布式数据库系统部分课后题答案

分布式数据库系统部分课后习题答案-1-分布式数据库系统部分课后题答案（by谢龙）第五章5.1p1:TITLE“Programmer”andp2:TITLE“Programmer”.(a)根据{p1,p2}对关系EMP进行水平分片：EMP1=σTITLE”Programmer”(EMP);EMP2=σTITLE”Programmer”(EMP)；分片结果为：(b)分片结果(EMP1,EMP2)不满足分片的正确性规则，项“E4,J.Miller,Programmer”不在任何一个分片中，其原因是：谓词{p1,p2}对关系EMP的划分并不完全。(c)可以这样修改p1和p2使其对EMP的划分符合分片的正确性规则：p1:TITLE“Programmer”andp2:TITLE≥“Programmer”根据新的谓词得到如图5.1.2的分片结果。从图5.1.2可以看出关系EMP中的每一项都属于且仅属于EMP1或EMP2中的一个，因此这个分片满足完整性（Completeness）和互斥性（Disjointness）；又关系EMP=EMP1∪ASGENOPNORESPDURE1P1Manager12E2P1Analyst24E2P2Analyst6E3P3Consultant10E3P4Engineer48E4P2Programmer18E5P2Manager24E6P4Manager48E7P3Engineer36E8P3Manager40PROJPNOPNAMEBUDGETLOCP1Instrumentation150000MontrealP2DatabaseDevelop.135000NewYorkP3CAD/CAM250000NewYorkP4Maintenance310000ParisPAYTITLESALElect.Eng.40000Syst.Anal.34000Mech.Eng.27000Programmer24000EMPENOENAMETITLEE1J.DoeElect.EngE2M.SmithSyst.Anal.E3A.LeeMech.Eng.E4J.MillerProgrammerE5B.CaseySyst.Anal.E6L.ChuElect.Eng.E7R.DavisMech.EngE8J.JonesSyst.Anal.Figure5.3.ModifiedExampleDatabaseEMP2ENOENAMETITLEE2M.SmithSyst.Anal.E5B.CaseySyst.Anal.E8J.JonesSyst.Anal.EMP1ENOENAMETITLEE1J.DoeElect.EngE3A.LeeMech.Eng.E6L.ChuElect.Eng.E7R.DavisMech.Eng图5.1.1.分布式数据库系统部分课后习题答案-2-EMP2，因此这个分片满足重构性（Reconstruction）。因此这个分片满足分片的正确性规则。5.2根据题目可以得到如下信息：1.根据第一个应用，可以得到5个谓词：p1:RESP=“Manager”;p2:RESP=“Consultant”;p3:RESP=“Engineer”;p4:RESP=“Programmer”;p5:RESP=“Analyst”2.根据第二个应用，可以得到2个谓词：p6:DUR20;p7:DUR≥20;根据得到的谓词，我们对其取小项。共可得到5×2=10个不同的小项：小项表小项号谓词组合谓词组合详细信息m1p1∧p6RESP=“Manager”DUR20∧m2p1∧p7RESP=“Manager”DUR∧≥20m3p2∧p6RESP=“Consultant”DUR20∧m4p2∧p7RESP=“Consultant”DUR∧≥20m5p3∧p6RESP=“Engineer”DUR20∧m6p3∧p7RESP=“Engineer”DUR∧≥20m7p4∧p6RESP=“Programmer”DUR20∧m8p4∧p7RESP=“Programmer”DUR∧≥20m9p5∧p6RESP=“Analyst”DUR20∧m10p5∧p7RESP=“Analyst”DUR∧≥20我们根据以上这10个小项对ASG表进行水平分片，共得到10个分片，但其中根据小项m4,m5和m8得到的分片为空，故没有写出。EMP2ENOENAMETITLEE2M.SmithSyst.Anal.E4J.MillerProgrammerE5B.CaseySyst.Anal.E8J.JonesSyst.Anal.EMP1ENOENAMETITLEE1J.DoeElect.EngE3A.LeeMech.Eng.E6L.ChuElect.Eng.E7R.DavisMech.Eng图5.1.2ASG7ENOPNORESPDURE4P2Programmer18ASG2ENOPNORESPDURE5P2Manager24E6P4Manager48E8P3Manager40ASG6ENOPNORESPDURE3P4Engineer48E7P3Engineer36ASG1ENOPNORESPDURE1P1Manager12ASG3ENOPNORESPDURE3P3Consultant10分布式数据库系统部分课后习题答案-3-5.3EMPTITLEPAY的连接图如下：这个图显然不是一个简单图。我们可以通过将PAY关系根据EMP关系的分片进行诱导分片，即PAY1=PAYEMP1;PAY2=PAYEMP2;PAY3=PAYEMP3;PAY4=PAYEMP4;或将EMP关系根据PAY关系的分片进行诱导分片（推荐此方案），即EMP1=EMPPAY1;EMP2=EMPPAY2;两种新的分片方案的连接图如下（推荐第二个方案）：ASG9ENOPNORESPDURE2P2Analyst6ASG10ENOPNORESPDURE2P1Analyst24TITLESALPAY1TITLESALPAY2EMP1ENOENAMETITLEEMP2ENOENAMETITLEEMP3ENOENAMETITLEEMP4ENOENAMETITLEEMP1ENOENAMETITLEEMP2ENOENAMETITLEEMP3ENOENAMETITLEEMP4ENOENAMETITLETITLESALPAY1TITLESALPAY2TITLESALPAY3TITLESALPAY4根据如下关系代数表达式进行分片后的EMPTITLEPAY连接图：EMP1=σTITLE=”Elect.Eng.”(EMP);EMP2=σTITLE=”Syst.Anal.”(EMP);EMP3=σTITLE=”Mech.Eng..”(EMP);EMP4=σTITLE=”Programmer”(EMP);PAY1=PAYEMP1;PAY2=PAYEMP2;PAY3=PAYEMP3;PAY4=PAYEMP4;图5.3.1分布式数据库系统部分课后习题答案-4-我们可以看出根据新的分片方案，我们得到的EMPTITLEPAY的连接图5.4.1和图5.4.2都是简单图。5.5p1:SAL30000andp2:SAL≥30000；根据谓词p1和p2对PAY进行水平分片的关系代数表达式为：PAY1=σSAL30000(PAY);PAY2=σSAL≥30000(PAY);得到的分片结果为：再根据对PAY的分片结果PAY1和PAY2，对EMP进行诱导水平分片，其关系代数表达式为：EMP1=EMPPAY1;EMP2=EMPPAY2得到的分片结果为：完整性说明：对于EMP的诱导水平分片，根据引用完整性，member关系（EMP）的任一个元组中的外键(TITLE)一定在owner（PAY）关系中存在。按外键(TITLE)相等的条件连接时，一定不会丢失member（EMP）关系中的元组。互斥性说明：对于诱导水平分片，如果连接图是简单的，则诱导水平分片满足互斥性。1.PAY1,PAY2的交集为空。TITLESALPAY1TITLESALPAY2EMP1ENOENAMETITLEEMP2ENOENAMETITLE图5.3.2根据如下关系代数表达式分片后得到的EMPTITTLEPAY连接图：PAY1=σSAL≥30000(PAY);PAY2=σSAL30000(PAY);EMP1=EMPPAY1;EMP2=EMPPAY2PAY1TITLESALMech.Eng.27000Programmer24000PAY2TITLESALElect.Eng.40000Syst.Anal.34000图5.5.1EMP1ENOENAMETITLEE3A.LeeMech.Eng.E4J.MillerProgrammerE7R.DavisMech.EngEMP2ENOENAMETITLEE1J.DoeElect.EngE2M.SmithSyst.Anal.E5B.CaseySyst.Anal.E6L.ChuElect.Eng.E8J.JonesSyst.Anal.图5.5.2分布式数据库系统部分课后习题答案-5-2.每个雇员仅有一个TITLE。3.每个TITLE仅有一个SAL。此时EMP的分片是互斥的。假设一个雇员可以有多个TITLE，一个TITLE有多个SAL，则可能出现不满足Disjointness的情况。重构性说明：关系EMP=EMP1∪EMP25.6查询集12345{,,,,}Qqqqqq=属性集12345{,,,,}AAAAAA=站点集123{,,}SSSS=()1ikrefq=1234512345()0110111101100110010011100AAAAAqqqqqa45123123102005010035501000150()SSSqqqqqb根据公式|(,)1(,)1(,)()()lijlklkkuseqkAiuseqkAjsiteaffAArefqaccq=∧=∀=∑∑311123223332512,3,531212322512,531312322512,5(,)()()()()()()70(,)()()()()30(,)()()()()30lklklklklklkaffAAaccqaccqaccqaccqaccqaccqaffAAaccqaccqaccqaccqaffAAaccqaccqaccqaccq========++++===++===++=∑∑∑∑∑∑35423331333551121311232233311(,)()()()40(,)()()()()()()()()85lklklkklaffAAaccqaccqaccqaffAAaccqaccqaccqaccqaccqaccqaccqaccq======+===++++++=∑∑∑∑⋮从而得到了本题的AA矩阵：123451234570303040553060600453060700454000400554545085AAAAAAAAAA应用BEA算法由现有的AA矩阵，计算CA矩阵，过程如下：1.首先，从AA矩阵中任选两列放入CA矩阵中，这里我们选第一列和第二列，得到初始CA矩阵如图5.6.1(a)所示。2.将第Ak列，根据BEQ算法插入到CA矩阵中。插入方法为：对每个可插入的位置根据公式：分布式数据库系统部分课后习题答案-6-(,,)2(,)2(,)2(,)ikjikkjijcontAAAbondAAbondAAbondAA=+-(1.1)1(,)(,)(,)nxyzxzyzbondAAaffAAaffAA==∑(1.2)计算其()cont函数值，选择其中最大的为插入点。3.插入所有列后，对得到的CA矩阵的行序参照其列序进行调整，最终得到CA矩阵。现以将A3列插入到CA中来说明第二步的计算过程。顺序（0-3-1）031033101010331(,,)2(,)2(,)2