Query Translation from XPath to SQL in the Presenc

QueryTranslationfromXPathtoSQLinthePresenceofRecursiveDTDsAbstractWestudytheproblemofevaluatingxpathqueriesoverxmldatathatisstoredinanrdbmsviaschema-basedshredding.Theinteractionbetweenrecursioninxpathqueriesandrecursionindtdsmakesitchallengingtoanswerxpathqueriesusingrdbms.Wepresentanewapproachtotranslatingxpathqueriesintosqlqueriesbasedonanotionofregularxpathexpressionsandasimpleleastfixpoint(lfp)operator.Regularxpathexpressionsareamildextensionofxpath,andthelfpoperatortakesasingleinputrelationandisalreadysupportedbymostcommercialrdbms.Weshowthatregularxpathexpressionsarecapableofcapturingbothdtdrecursionandxpathqueriesinauniformframework.Furthermore,theycanbetranslatedintoanequivalentsequenceofsqlquerieswiththelfpoperator.Wepresentalgorithmsforrewritingxpathqueriesintoregularxpathexpressionsandfortranslatingregularxpathexpressionstosqlqueries.Wealsoprovideoptimizationtechniquesforminimizingtheuseofthelfpoperator.Thenoveltyofourapproachconsistsinitscapabilitytoansweralargeclassofxpathqueriesbymeansofonlylow-endrdbmsfeaturesalreadyavailableinmostrdbms,aswellasitsflexibilitytoaccommodateexistingrelationalqueryoptimizationtechniques.Ourexperimentalresultsverifytheeffectivenessofourtechniques.1IntroductionItisincreasinglycommontofindxmldatastoredinarelationaldatabasesystem(rdbms),typicallybasedondtd/schema-basedshreddingintorelations[34]asfoundinmanycommercialproducts(e.g.,[17,26,29]).Withthiscomestheneedforansweringxmlqueriesusingrdbms,bytranslatingxmlqueriestosql.Thequerytranslationproblemcanbestatedasfollows.Consideramappingτd,definedintermsofdtd-basedshredding,fromxmldocumentsconformingtoadtdDtorelationsofaschemaR.GivenanxmlqueryQ,wewanttofind(asequenceof)equivalentsqlqueriesQ′suchthatforanyxmldocumentTconformingtoD,QoverTcanbeansweredbyQ′overtheinstanceτd(T)ofRthatrepresentsT,i.e.,Q(T)=Q′(τd(T)).HereweallowdtdsDtoberecursiveandconsiderqueriesQinxpath[9],whichisessentialforotherxmlquerylanguagessuchasXQueryandXSLT.Thequerytranslationproblemis,however,nontrivial:dtds(orxmlSchema)foundinpracticeareoftenrecursive[7]andcomplex.Thisisparticularlyevidentinreal-lifeapplications(see,e.g.,BIOML[6]andGedML[15],which,whenrepresentedasgraphs,containsanumberofnestedandoverlappingcycles).Theinteractionbetweenrecursioninadtdandrecursioninanxmlquerycomplicatesthetranslation.WhenthedtdhasatreeorDAGstructure,anaturalapproach[18]isbasedonenumeratingallmatchingpathsoftheinputxpathqueryinadtd,sharingasinglerepresentationofcommonsub-paths,rewritingthesepathsintosqlqueries,and1takingaunionofthesequeries.However,thisapproachnolongerworksonrecursivedtdssinceitmayleadtoinfinitelymanypathswhendealingwithdescendants‘//’inxpath.Anotherapproachisbymeansofarichintermediatelanguageandmiddlewareasproposedin[32]:firstexpressinputxmlqueriesintheintermediatelanguage,andthenevaluatethetranslatedqueriesleveragingthecomputingpowerofthemiddlewareandtheunderlyingrdbms.However,aspointedoutbyarecentsurvey[22],thisapproachrequiresimplementationofthemiddlewareontopofrdbms,andintroducescommunicationoverheadbetweenthemiddlewareandtherdbms,amongotherthings.Itismoreconvenientandpossiblymoreefficienttotranslatexpathqueriestosqlandpushthework(sqlqueries)totheunderlyingrdbms,capitalizingontherdbmstoevaluateandoptimizethequeries.This,however,callsforanextensionofsqltosupportcertainrecursiveoperator.Asobservedby[22],althoughtherehasbeenahostofworkonstoringandqueryingxmlusinganrdbms[10,14,18,21,25,32,33],theproblemoftranslatingrecursivexmlqueriesintosqlinthepresenceofrecursivedtdshasnotbeenwellstudied,anditwassingledoutasthemostimportantopenproblemin[22].Recentlyanelegantapproachwasproposedin[21]totranslatingpathqueriestosqlwiththelinear-recursionconstructwith...recursiveofsql’99.Thealgorithmof[21]iscapableoftranslatingpathquerieswith//andlimitedqualifiersto(asequenceof)sqlquerieswiththesql’99recursionoperator.Unfortunately,thisapproachhasseverallimitations.Thefirstweaknessisthatitreliesonthesql’99recursionfunctionality,whichisnotcurrentlysupportedbymanycommercialproductsincludingOracleandMicrosoftsqlserver.Onewantsaneffectivequerytranslationapproachthatworkswithawidevarietyofproductssupportinglow-endrecursionfunctionality,ratherthanrequiringanadvanceddbmsfeatureofonlythemostsophisticatedsystems.Second,thesqlquerieswiththesql’99recursionproducedbythetranslationalgorithmof[21]aretypicallylargeandcomplex.Asaresult,theymaynotbeeffectivelyoptimizedbyallplatformssupportingsql’99recursionforthesamereasonsthatnotallrdbmsplatformscaneffectivelyoptimizemildlycomplexnon-recursivequeries[13].Worsestill,asthewith...recursiveoperatoristreatedasablackbox,theusercandolittletooptimizeit.Athirdproblemisthattheclassofpathqueryhandledbythealgorithmof[21]istoorestrictedtoexpressxpathqueriescommonlyfoundinpractice.Inlightofthisweproposeanewapproachtotranslatingaclassofxpathqueriestosql,basedonanotionofregularxpathexpressionsandasimpleleastfixpoint(lfp)operator.OurregularxpathexpressionsextendxpathbysupportinggeneralKleeneclosureE∗insteadof//.ThelfpoperatorΦ(R)takesasingleinputrelationRinsteadofm