您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 信息化管理 > Constraint Query Languages
ConstraintQueryLanguagesParisC.Kanellakis1GabrielM.Kuper2PeterRevesz3TechnicalReportNo.CS-92-50October19921BrownUniversityBox1910,Providence,RI029122IBMT.J.WatsonResearchCenterYorktownHeights,NY3BrownUniversityBox1910,Providence,RI02912CONSTRAINTQUERYLANGUAGES ParisC.KanellakisyGabrielM.KuperzPeterZ.ReveszxJuly1992AbstractWeinvestigatetherelationshipbetweenprogrammingwithconstraintsanddatabasequerylanguages.Weshowthate cient,declarativedatabaseprogrammingcanbecombinedwithe cientconstraintsolving.Thekeyintuitionisthatthegeneralizationofagroundfact,ortuple,isaconjunctionofconstraintsoverasmallnumberofvariables.WedescribethebasicConstraintQueryLanguagedesignprinciplesandillustratethemwithfourclassesofconstraints:realpolynomialinequalities,denselinearorderinequalities,equalitiesoveranin nitedomain,andbooleanequalities.Fortheanalysis,weusequanti ereliminationtechniquesfromlogicandtheconceptofdatacomplexityfromdatabasetheory.Thisframeworkisapplicabletomanagingspatialdataandcanbecombinedwithexistingmulti-dimensionalsearchingalgorithmsanddatastructures.Keywords:databasequeries,spatialdatabases,datacomplexity,quanti erelimination,constraintlogicprogramming,relationalcalculus,Datalog.1Introduction1.1MotivationandFrameworkQ:What’sinatuple?A:Constraints.Constraintprogrammingparadigmsareinherently\declarative,sincetheydescribecompu-tationsbyspecifyinghowthesecomputationsareconstrained[7,34,50].Amajorrecentdevelopmentinlogicprogrammingsystemsistheintegrationoflogicandconstraintparadigms, Apreliminaryversionoftheresultsinthispaperappearedin[28].Thisisalsoarevision,withadditionalmaterial,ofBrownUniversitytechnicalreportCS-90-31.yBrownUniversity,Providence,RI.ResearchwassupportedbyIBM,byanAlfredP.SloanFellowship,andbyONRgrantsN00014-83-K-0146ARPAOrderNo.4786andN00014-91-J-4052ARPAOrderNo.8225.zIBMT.J.WatsonResearchCenter,YorktownHeights,NY.xBrownUniversity,Providence,RI.ResearchwassupportedbyNSFgrantIRI-8617344andbyNSF-INRIAgrantINT-8817874.1e.g.,inCLP[25],inPrologIII[15],andinCHIP[17],forarecentsurveysee[14].Oneintu-itivereasonforthissuccessfulintegrationisasfollows.AstrengthofPrologisitstop-down,depth- rstsearchstrategy.Theoperationof rst-ordertermuni cation,attheforefrontofthissearch,isaspecialformofe cientconstraintsolving.Additionalconstraintsolvingincreasesthedepthofthesearchand,thus,thee ectivenessoftheapproach.Thedeclarativestyleofdatabasequerylanguagesisanimportantaspectofdatabasesys-tems.Indeed,havingsuchalanguageforad-hocdatabasequeryingisarequirementtoday.Itisrathersurprisingthatconstraintprogramminghasnotreallyin uenceddatabasequerylanguagedesign.Therehasbeensomepreviousresearchonthepowerofconstraintsfortheimplicitspeci cationoftemporaldata[12],forextendingrelationalalgebra[21],andformagicsetevaluation[42],butnooveralldesignprinciples.Thebottom-upandset-at-a-timestyleofevaluationemphasizedindatabases,andmorerecentlyinknowledgebases,seemstocontradictthetop-down,depth- rstintuitionbehindConstraintLogicProgramming.Themaincontributionofthispaperistoshowthatitispossibletobridgethegapbetween:bottom-up,e cient,declarativedatabaseprogrammingande cientconstraintsolving.AkeyintuitioncomesfromConstraintLogicProgramming:aconjunctionofconstraintsisthecorrectgeneralizationofthegroundfact.Thetechnicaltoolsforthisintegrationare:datacomplexity[9,57]fromdatabasetheory,andquanti ereliminationmethodsfrommathematicallogic.Letusprovidesomemotivationfortheintegrationofdatabaseandconstraintsolvingmeth-ods.Manipulationofspatialdataisanimportantapplicationarea(e.g.,spatialorgeographicdatabases)thatrequiresbothrelationalquerylanguagetechniquesandarithmeticcalculations.Indexesforrangesearchingandmodelingofcomplexstructureshavebeenusedtobridgethegapbetweendeclarativeaccessingoflargevolumesofspatialdataandperformingcommoncomputationalgeometrytasks.However,evenwiththeseextensionsarithmeticcalculationshavenotbeengiven rst-classcitizenstatusinthevariousquerylanguagesused,andtheinte-grationoflanguageandapplicationhasbeen\loose.Foranexampleof\tightintegrationofapplication,languageparadigm,andimplementation,letusreviewtherelationaldatamodel.Intherelationaldatamodel,[13],animportantapplicationarea(dataprocessing)isde-scribedinadeclarativestyle(relationalcalculus)sothatitcanbeautomaticallyande cientlytranslatedintoproceduralstyle(relationalalgebra).Programevaluationisbottom-upandset-at-a-timeasopposedtotop-downandtuple-at-a-time,becausetheapplicationsinvolvemassiveamountsofstructureddata.Thisevaluationmaybeoptimized,e.g.,viaalgebraictransforma-tions,selectionpropagationetc.Itmaybeperformedin-coreinPTIME,becauseofthelowcomplexityofthecalculationsexpressed.Mostimportantly,itmaybeimplementede cientlywithlargeamountsofdatainsecondarystorageviaindexingandhashing.Ourclaiminthispaperisthatbygeneralizingrelationalformalismstoconstraintfor-malismsitis,inprinciple,possibletogeneralizeallthekeyfeaturesoftherelationaldatamodel.(1)Thelanguageframeworkthatweproposepreservesthedeclarativestyleandthee ciencyofrelationaldatabaselanguages.(2)Thepossibleapplicationso
本文标题:Constraint Query Languages
链接地址:https://www.777doc.com/doc-6310908 .html