XML代价估计方法研究综述课件

XML代价估计方法研究综述

XMLGroup

Outline研究代价估计的必要性xml中代价估计研究的难点背景知识介绍现有方法分类研究代价估计的必要性查询优化的基础不同分支对查询目标的选择率不同，如果选择性低的分支先于选择性高的分支执行，就会有效的减少中间结果从而提供查询效率结构连接在XML中是一个很重要的操作，连接的顺序的选择需要计算不同连接顺序的代价及早给用户提供反馈信息xml中代价估计研究的难点XML数据的不规则性是对传统统计信息方法的重要挑战，具体表现在以下几个方面：路径依赖性，如同为name结点，在person下和在city下出现意义就完全不同结构相关性嵌套在不同祖先下面的同类结点的个数差别可能很大，如book结点下的author个数是不确定的值相关性//purchase/Item[type=‘book’][price>100]XML的有序性制约了转换规则的灵活性所有这些问题，都使得在xml中采用传统的代价估计方法不切实际，会带来很大的误差。针对xml数据的特点，我们应该寻求一种新的代价估计方法。BackgroundKnowledgeXMLDataModelAlarge,node-labeledtreeT(V,E)d0a1a2a3p4p5n6t14k15y131999y16t17k18k19n7b9p8y20t21k22y24t25k26n10b12p9t23t26200220012000ExampleXMLDocumentTreeBackgroundKnowledgeXMLDataModelAlarge,node-labeledtreeT(V,E)d0a1a2a3p4p5n6t14k15y131999y16t17k18k19n7b9p8y20t21k22y24t25k26n10b12p9t23t26200220012000ExampleXMLDocumentBackgroundKnowledgeXMLQueryModelAnode-labeledquerytreeTQEachnodeofTQislabeledwithavariablenameqiinQEachedge(qi,qj)ofTQisannotatedwithanXPathexpressionpath(qi,qj)thatdescribesthespecificstructuralconstraintsspecifiedinQQueryFragment：for$bindoc(“bib.xml”)/bib/book$ain$b/author$tin$b/titlebibbookauthortitleroot$b$a$tTwigQueryModel现有估计方法的分类路径选择性计算Twig匹配个数统计值谓词选择率估计结构连接代价估计Overviewdatatreedifferentsummarizationmethodsbasedon:pathallm-lengthpathF/B-stabilityLore[McHughetal,VLDB99]pruningPathTree,MarkovTable[Aboulnagaetal,VLDB01]XSketch[Polyzotisetal,VLDB02]typeXSketches[Polyzotisetal,SIGMOD02]+value+twigXSketches[Polyzotisetal,SIGMOD04]RegionCode2DModel1DModelStatiX[Freireetal,SIGMOD02]PHHistogram[WuY]EDBT2002Interva&PositionModel[H.Lu]SIGMOD2003路径选择性计算问题描述/a/b[c/d//e][g//e/f]//*/*/e/fPathTree&MarkovTableAshrafAboulnaga,AlaaR.Alameldeen,andJeffryF.Naughton.EstimatingtheselectivityofXMLpathexpressionsforInternetscaleapplications.VLDB2001PathTreeConstructionStartfromanoriginalpathtreeCountofnodesinabsolutepathsAggregatethetreetofitinthelimitedspaceSibling-*EstimationMatchthequeryagainstthepathtree,matching*asthelastresort.Needtodecidewhethertousetotalcountoraveragecount.AnXMLdocumentanditspathtree<A><B></B><B><D></D></B><C><D></D><E></E><E></E><E></E></C></A>A1B2C1D1D1E3Estimation:count(A/B/D)=1count(A/C/D)=1AggregatePathTreeA1C9B13G10F15H6K12E5D7K11J4I2AggregatePathTreeA1C9B13G10F15H6K12E5D7K11J4I2红色结点表示那些不频繁出现的结点，需要删除，从而保证path树能够放入内存Sibling-*SummarizationA1C9B13*F15*K*f=23n=2683把查询和path树匹配需要决定用总数还是平均数估计方法Estimation:count(//C/H/K)=11count(//C/*/K)=23MarkovTable构造一个表，存储长度<=m的不同路径出现的次数，其中m>=2。当查询路径长度<=m时，可以直接从表中读出结果，否则，用公式计算。例如，m＝3，查询为//A/B/C/D，则当表不能装入内存的时候，进行剪枝操作。f(B/C/D)f(B/C)f(A/B/C/D)≈f(A/B/C)MarkovTable::Exampleabbcddeeefda1a/b2b2a/c1c1b/d2d3c/d1e3c/e3f1c/f1abdde12213cf11m=2b2c/e3d3*3/3e3c/*2/2a/b2*/*1/1b/d2suffix-*Q1:a/c/eTwig匹配个数统计问题描述TwigQuery(basicbuildingblockofdeclarativequerylanguagesforXML)FOR$fINdocument(“person.xml”)//department/facultyFOR$rin$f/RA,FOR$tin$f/TADepartmentFacultyRATA$f$r$tXSketch方法

N.Polyzotis,M.Garofalakis.StatisticalSynopsesforGraph-StructuredXMLDatabases,InProc.ofACMSIGMODConf.2002N.PolyzotisandM.Garofalakis.Structureandvaluesynopsesforxmldatagraphs.InProceedingsof28thVLDBConf.,2002.

N.Polyzotis,M.Garofalakis,andYannisIosnnidis.SelectivityEstimationforXMLTwigs.InProc.ofthe20thIntl.Conf.onDataEngineering,2004N.PolyzotisandM.GarofalakisandY.Ioannidis.ApproximateXMLQueryAnswers.InProc.ACMSIGMOD2004d0a1a2a3p4p5n6t14k15y131999y16t17k18k19n7b9p8y20t21k22y24t25k26n10b12p9t23t26200220012000D(1)A(3)N(3)P(4)B(2)Y(4)K(6)T(6)H(Y)B/FB/FB/FB/FBB/FFFXSketch方法B/Fstability

Definition：LetU,VbesetsofelementsinanXMLdataTreeT.WesaythatVisbackward-stable(B-stale)withrespecttoU,iffforeachv∈Vthereexistsau∈Usuchthatedge(u,v)isinT.Similarly,Uissaidtobeforward-stable(F-stable)withrespecttoV,iffforeachu∈Uthereexistsav∈Vsuchthattheedge(u,v)isinG.D(1)A(3)N(3)P(4)B(2)Y(4)K(6)T(6)H(Y)B/FB/FB/FB/FBB/FFFXSketch方法HowtoestimatethecardinalityofxpathquerysuchasA/P/KorA/[p]?Utilizingedgestability,Wecangiveanaccuratematchnumber:Count(A/P/K)=6Count(A/[p])=3ButwhataboutA/P/Twhichdoesn’tconformtobackwardstability?2assumptions

Pathindependence

Backward-edgeuniformityCount(A/P/T)=f(A/P/T)*count(T)f(A/P/T)=f(A/P)*f(P/T|A/P)=f(P/T|A/P)=f(P/T)≈count(P)/(count(B)+count(P))XSketch方法(处理值谓词)v1v3v5v2v4BBFFSTN(v5)Dep(v5)={v1,v4}v1v4Histogramatv5H(σ1,σ4)=count(v1{σ1}[v2]/v3[v4{σ4}]/v5)v3v5count(v1{σ1}[v2]/v3{σ3}[v4{σ4}]/v5)=H(σ1,σ4)*count(v3{σ3})/count(v3)A1[Edge-ValueIndependenceAcrossNon-SatbleEdges]f(u/v|v{σ})≈f(u/v)A2[Value-IndependenceOutsideCorrelationScope]XSkecth方法（处理twig）ProblemwiththeformermodelLetusseeasimpleexamplefort0inA,t1int0/B,t2int0/Cra1a2b1c1b2c2ra1a2b1c1b2c2100×10×10010100×10010×10RA(2)B(110)C(110)B/FB/FB/F(a)(b)(c)StructuralXSketch2000bindingtuplesonthefirstdocument10100tuplesontheseconddocumentXSkecth方法（处理twig）Singe-pathXSketchmodeldosenotstoredetailedenoughinformationtocapturethecorrelationpatternsbetweenmultiplepathexpressions.IfnodeArecordsatwo-dimensionaldistributionfA(b,c)forthefractionofelementsinAthathavebchildreninBandcchildreninC.CBCCElementsfp10010a10.510100a20.52×(0.5×100×10＋0.5×10×100)CBCCElementsfp100100a10.51010a20.52×(0.5×100×100＋0.5×10×10)XSkecth方法（处理twig）CKCYElementsfp21p40.25P54×(0.25×2×1×10＋0.25×1×1＋0.5×1)＝5CPCN21210.2521110.511p8，p9AnotherExampleEdge-distribution:fP(CY,CK,CP，CN)PYPKAPANStatix方法

FreireJ,JayantR,RamanathM,RoyPandSimeonJ.StatiX:MakingXMLCount.In:Proc.ofACMSIGMOD2002,USA.Statix方法Constructioneveryinstancenodeisassignedauniqueid(typeid+sequentialnodeid)duringparsingandvalidation,meanwhilegatheringstatisticsConstructingthehistogramsHistogramBuildhistogramforeachtypeMightcontainhistogramdescribingthedistributionoftheparentsofatypeValuehistogramcanbebuiltfortypesthataredefinedintermsofbasetypes(eg.integer)EstimationConvertthequeryintoSQL(i.e.,relationaljoinonIDs)UsestandardhistogrammultiplicationStatiX::ExampleFOR$sindocument(“imdb.xml”)/show,

$rin$s/reviewWHERE$s/year<1992RETURN$s/title,$rSELECTtitle,reviewFROMShow,ReviewWHEREShow.year<1992AND

Show.ID=Review.ParIDSTATShow{CARD:5ID:1—6}STATShow_Year{VALUE:1990—2001BUCKET_NUM:2BUCKETS:{[1990,1994):3;[1994,2001):2}}STATReview{CARD:8ID:30—38

PARENTHISTOGRAMShow{BUCKET_NUM:3BUCKETS:{[1,2):4;[2,3):1;[3,5):3}}}

STATAka{CARD:6ID:6-12PARENTHISTOGRAMShow_Episode{BUCKET_NUM:3BUCKETS:{[1,2):1;[2,6):0;[6,12):7}}3×1/2×8/5=2.4SummaryQuery//*BranchValueCorrelationSchemaStatiXSimpleTwig+ValueNYYYNYPathTreeSimplePathNYNNNNMarkovTableSimplePathNYNNNNXSketchSimpleTwigNNYNNNXSketchesSimpleTwig+ValueNNYYY(mDmethods)N结构连接代价估计问题描述给定任意的祖先节点集合A和后代节点集合D，计算A//D结果集合的大小，估计匹配的祖先－后代的结果个数当同一祖先有多个后代，或者同一后代有多个祖先时，节点对个数可能远远大于祖先或后代的个数。应用连接顺序的选择结构连接代价估计Existedwork2Dmodel:pHhistogram[WuY,PatelJandJagadishH.V.EstimatingAnswerSizesforXMLQueries.In:Proc.oftheEDBT2002.]IntervalandPositionalmodel[W.Wang,H.Jiang,H.Lu,andJ.F.Xu.ContainmentjoinSizeEstimation:ModelsandMethods.In:Proc.OfACMSIGMOD2003]AbsoluteRegionCode(start,end)<contact><name>blah</name><phone><office>1234</office><home>5678</home><mobile>0000</mobile></phone></contact>contactnamephoneblahofficehomemobile123456780000(1,16)(2,4)(3,3)(5,15)(6,8)(7,7)(9,11)(10,10)(12,14)(13,13)234a.start<d.startandd.end<a.endpHHistogramForbiddenRegionsForanodeR1和R2是结点A的ForbiddenRegion两个结点的(start,end)满足：（1）nooverlap（2）nested不可能有部分重叠的(partiallyoverlap)情况pHHistogramEstP[A]=HistP1[A]×{1/4×HistP2[A]+HistP2[B]+HistP2[C]+HistP2[E]+1/2(HistP2[D]+HistP2[F])}Ancestor-basedJoinEstimationEstP[A]=HistP2[A]×{1/4×HistP1[A]+HistP1[F]+HistP2[G]+HistP1[H]}Descendant-basedJoinEstimationpHHistogram355137102120300000000est=3*(12+1+2+0.25*5)=48.75AGIHstartendstartstartendendForoff-diagonalcells:pHforApHforDInterval&PositionModelsMapintonewproblemsunder2newlyproposedmodels.IntervalmodelandPositionmodelHistogrambasedmethodthatisadaptivetothedata:PLhistogramAssumption:1DuniformofthedescendantsetEstimationisrobustwhencorrelationislowSamplingbasedmethodthatcapturesthecorrelation:IMSamplingandPMSamplingAssumption:HeightoftheXMLdatatreeisasmallco