资源描述：
《厦门大学数据库实验室-李雨倩-MapReduce-连接优化（续）ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、厦门大学数据库实验室MapReduce连接优化报告人：李雨倩导师：林子雨2014.08.12基于传统MapReduce的连接这类算法主要通过实现map函数、reduce函数及之间的数据流传递，来完成数据连接运算。对于这方面的研究主要集中于两表等值连接、两表非等值连接（又称θ连接）、两表相似度连接、多表等值连接（星型连接、链式连接）、多表非等值连接等问题。相似度连接多表连接相似度连接举例Forexample,inmaster-data-managementapplications,asystemhastoidentifythatnames“JohnW.Smith”,“Smit
2、h,John”,and“JohnWilliamSmith”arepotentiallyreferringtothesameperson.Asanotherexample,whenminingsocialnetworkingsiteswhereusers’preferencesarestoredasbitvectors(wherea“1”bitmeansinterestinacertaindomain),applicationswanttousethefactthatauserwithpreferencebitvector“[1,0,0,1,1,0,1,0,0,1]”poss
3、iblyhassimilarintereststoauserwithpreferences“[1,0,0,0,1,0,1,0,1,1]”.相似度连接算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法简介该算法首先利用两个MapReduce作业进行数据统计与全局词项排序。接着利用一个MapReduce作业，通过前缀过滤的方法减少需要参加相似连接运算的数据，并生成连接结果的键值对。最后通过一个MapReduce作业，根据前一步生成的键值对生成最后的相似性连接结果。该算法充分利用了
4、相似性连接的特点，过滤掉不可能成为最终结果的数据，提高了查询效率，但应用范围只限于文本字符串的相似性连接。相似度连接算法数据统计与全局词项排序b的第二阶段用tear-downfunction在内存中排序相似度连接算法前缀过滤A属于X组，B、G属于Y组，C、D属于Z组相似度计算函数Forexample,thestring“Iwillcallback”canbetokenizedintothewordset[I,will,call,back].Inordertomeasurethesimilaritybetweenstrings,weuseasetsimilarityfunct
5、ionsuchasJaccardorTanimotocoefficient,cosinecoefficient,etc.1.Forexample,theJaccardsimilarityfunctionfortwosetsxandyisdefinedas:jaccard(x,y)=.Thus,theJaccardsimilaritybetweenstrings“Iwillcallback”and“Iwillcallyousoon”is3/6=0.5.相似度连接算法前缀过滤A属于X组，B、G属于Y组，C、D属于Z组根据前一步生成的键值对生成最后的相似性连接结果把第一阶段产生的
6、结果广播给每个map相似度连接多表连接多表连接在数据库应用领域中，经常需要对多个表进行连接操作，比较有代表性的是星型连接与链式连接。星型连接：在数据仓库应用中,星型模式是最常用的数据表示模型,包括一个事实表和多个维表.链式连接：星型连接事实表LINEORDER和4个维表CUSTOMER、SUPPLIER、PART和DATE.在基于星型模式的OLAP查询中,涉及最多的操作就是维表和事实表的连接,又被称为星型连接.星型连接返回连接的全部结果,是OLAP查询中代价最高的操作之一.例1.SELECT*FROMLineorderF,CustomerC,SupplierS,PartP,
7、DateDWHEREF.custkey=C.custkeyandF.suppkey=S.suppkeyandF.partkey=P.partkeyandF.orderdate=D.datekeyORDERBYF.squantity+C.scredit+S.saddress+P.sbrand1+D.stimeSTOPAFTERk;多表等值连接算法LetusconsiderjoiningthreerelationsWecouldimplementthisjoinbyasequenceoftwotwo-wayjoins,
