Constraint Query Languages

ConstraintQueryLanguagesParisC.Kanellakis1GabrielM.Kuper2PeterRevesz3TechnicalReportNo.CS-92-50October19921BrownUniversityBox1910,Providence,RI029122IBMT.J.WatsonResearchCenterYorktownHeights,NY3BrownUniversityBox1910,Providence,RI02912CONSTRAINTQUERYLANGUAGESParisC.KanellakisyGabrielM.KuperzPeterZ.ReveszxJuly1992AbstractWeinvestigatetherelationshipbetweenprogrammingwithconstraintsanddatabasequerylanguages.Weshowthatecient,declarativedatabaseprogrammingcanbecombinedwithecientconstraintsolving.Thekeyintuitionisthatthegeneralizationofagroundfact,ortuple,isaconjunctionofconstraintsoverasmallnumberofvariables.WedescribethebasicConstraintQueryLanguagedesignprinciplesandillustratethemwithfourclassesofconstraints:realpolynomialinequalities,denselinearorderinequalities,equalitiesoveraninnitedomain,andbooleanequalities.Fortheanalysis,weusequantiereliminationtechniquesfromlogicandtheconceptofdatacomplexityfromdatabasetheory.Thisframeworkisapplicabletomanagingspatialdataandcanbecombinedwithexistingmulti-dimensionalsearchingalgorithmsanddatastructures.Keywords:databasequeries,spatialdatabases,datacomplexity,quantierelimination,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.Theoperationofrst-ordertermunication,attheforefrontofthissearch,isaspecialformofecientconstraintsolving.Additionalconstraintsolvingincreasesthedepthofthesearchand,thus,theeectivenessoftheapproach.Thedeclarativestyleofdatabasequerylanguagesisanimportantaspectofdatabasesys-tems.Indeed,havingsuchalanguageforad-hocdatabasequeryingisarequirementtoday.Itisrathersurprisingthatconstraintprogramminghasnotreallyinuenceddatabasequerylanguagedesign.Therehasbeensomepreviousresearchonthepowerofconstraintsfortheimplicitspecicationoftemporaldata[12],forextendingrelationalalgebra[21],andformagicsetevaluation[42],butnooveralldesignprinciples.Thebottom-upandset-at-a-timestyleofevaluationemphasizedindatabases,andmorerecentlyinknowledgebases,seemstocontradictthetop-down,depth-rstintuitionbehindConstraintLogicProgramming.Themaincontributionofthispaperistoshowthatitispossibletobridgethegapbetween:bottom-up,ecient,declarativedatabaseprogrammingandecientconstraintsolving.AkeyintuitioncomesfromConstraintLogicProgramming:aconjunctionofconstraintsisthecorrectgeneralizationofthegroundfact.Thetechnicaltoolsforthisintegrationare:datacomplexity[9,57]fromdatabasetheory,andquantiereliminationmethodsfrommathematicallogic.Letusprovidesomemotivationfortheintegrationofdatabaseandconstraintsolvingmeth-ods.Manipulationofspatialdataisanimportantapplicationarea(e.g.,spatialorgeographicdatabases)thatrequiresbothrelationalquerylanguagetechniquesandarithmeticcalculations.Indexesforrangesearchingandmodelingofcomplexstructureshavebeenusedtobridgethegapbetweendeclarativeaccessingoflargevolumesofspatialdataandperformingcommoncomputationalgeometrytasks.However,evenwiththeseextensionsarithmeticcalculationshavenotbeengivenrst-classcitizenstatusinthevariousquerylanguagesused,andtheinte-grationoflanguageandapplicationhasbeen\loose.Foranexampleof\tightintegrationofapplication,languageparadigm,andimplementation,letusreviewtherelationaldatamodel.Intherelationaldatamodel,[13],animportantapplicationarea(dataprocessing)isde-scribedinadeclarativestyle(relationalcalculus)sothatitcanbeautomaticallyandecientlytranslatedintoproceduralstyle(relationalalgebra).Programevaluationisbottom-upandset-at-a-timeasopposedtotop-downandtuple-at-a-time,becausetheapplicationsinvolvemassiveamountsofstructureddata.Thisevaluationmaybeoptimized,e.g.,viaalgebraictransforma-tions,selectionpropagationetc.Itmaybeperformedin-coreinPTIME,becauseofthelowcomplexityofthecalculationsexpressed.Mostimportantly,itmaybeimplementedecientlywithlargeamountsofdatainsecondarystorageviaindexingandhashing.Ourclaiminthispaperisthatbygeneralizingrelationalformalismstoconstraintfor-malismsitis,inprinciple,possibletogeneralizeallthekeyfeaturesoftherelationaldatamodel.(1)Thelanguageframeworkthatweproposepreservesthedeclarativestyleandtheeciencyofrelationaldatabaselanguages.(2)Thepossibleapplicationso