Constraint programming and database query language

ConstraintProgrammingandDatabaseQueryLanguagesParisCKanellakis?andDinaQGoldin?BrownUniversity,Providence,RI02192,USAAbstract.ThedeclarativeprogrammingparadigmsusedinconstraintlanguagescanleadtopowerfulextensionsofCodd’srelationaldatamodel.Thedevelopmentofconstraintdatabasequerylanguagesfromlogicaldatabasequerylanguageshasmanysimilaritieswiththedevelop-mentofconstraintlogicprogrammingfromlogicprogramming,butwiththeadditionalrequirementsofdataecient,set-at-a-time,andbottom-upevaluation.Inthisoverviewofconstraintquerylanguages(CQLs)werstpresenttheframeworkof[41].Theprincipalideaisthat:\thek-tuple(orrecord)datatypecanbegeneralizedbyaconjunctionofquantier-freeconstraintsoverkvariables.Thegeneralizationmustpre-servevariouslanguagepropertiesoftherelationaldatamodel,e.g.,thecalculus/algebraequivalence,andhavetimecomplexitypolynomialinthesizeofthedata.Wenextpresentanalgebrafordenseordercon-straintsthatissimplertoevaluatethanthecalculusdescribedin[41],andwesharpensomeoftherelateddatacomplexitybounds.WenotethatCQLsareapplicabletospatialdatabases.Thisisbecausetheselanguageshave\spatialpointsetasthesemanticsoftheirrecorddatatypeandbecauseexistingmulti-dimensionalsearchingdatastructurescansupportI/Oecientaccesstosetsofrecords.Finally,weobservethatCQLscanbeaugmentedwithcomplexobjectdatatypes,aggregateoperations,andnull-values,justliketherelationaldatamodel.1FromConstraintProgrammingtoDatabaseQuerying1.1DeclarativeProgrammingwithConstraintsConstraintprogrammingparadigmsareinherentlydeclarative,sincetheyim-plicitlydescribecomputationsbyspecifyinghowthesecomputationsarecon-strained.Programmingwithconstraintsasprimitives(orconstraintprogram-ming)isappealingbecauseconstraintsarethenormallanguageofdiscourseformanyhigh-levelapplications.Pioneeringworkinconstraintprogramminggoesbacktotheearly1960’s,e.g.,Sutherland’sSKETCHPAD[67].Thethemehasbeeninvestigatedsincethe1970’s,e.g.,inarticialintelligence[31,54,55,66],ingraphical-interfaces[10],andinlogicprogramminglanguages[37,22,27].Therelevantliteratureandcontributionsaretoolargetoattemptasurvey.Insteadwewilllimitourexpositiontorecentapplicationsindatabases.?ResearchwassupportedbyONRgrantN00014-91-J-4052ARPAOrderNo.8225.Perhapsoneofthemostimportantadvancesinconstraintprogramminginthe1980’shasbeenthedevelopmentofConstraintLogicProgramming(CLP)asageneral-purposeframeworkforcomputations,e.g.,inCLP()[37],inPrologIII[22],andinCHIP[27,72].FormoreinformationonCLPseethesurveysin[21,51],theproceedingsoflogicprogrammingconferencesandofrecentworkshopsonthesubject,e.g.,[42].Inparticular,theadvancesinCLPareveryrelevantfordatabaseapplications(whichbringsustothesubjectofthispaper).Onereasonisthemanyconnectionsbetweendatabasesandlogicprogramming.StartingwiththeJapanese5thGenerationProject,theseconnectionswereexploredindepthduringthelastdecade.Thedeclarativestyleofdatabasequerylanguagesisanimportantaspectofdatabasesystems,thathasbeenatthecoreoftherelationaldatamodelsinceCodd’spioneeringwork[20].Indeed,havingsuchalanguageforad-hocdatabasequeryingisarequirementintoday’scommercialrelationaltechnology.QueryinginCodd’srelationalcalculusisaformoflimited(butverysuccessful)constraintprogramming.Itisrathersurprisingthatotheradvancesinconstraintprogramminghavenotyetinuenceddatabasequerylanguagedesign.However,webelievethatthiswillsoonchangeandtherewillbe(inthe1990’s)integrationofconstraintprogramminganddatabases.OneintuitivereasonforthesuccessofCLPisasfollows.Astrengthofatypicallogicprogramminglanguage(e.g.,Prolog)isitstop-down,depth-rstsearchstrategy.Theoperationofrst-ordertermunication,attheforefrontofthissearch,isaspecialformofecientconstraintsolving.Additionalcon-straintsolvingincreasesthedepthofthesearchand,thus,theeectivenessoftheapproach.Unfortunately,thebottom-upandset-at-a-timestyleofevalua-tionemphasizedinrelationaldatabases,andmorerecentlyinknowledgebases,seemstocontradictthetop-down,depth-rstintuitionbehindCLP.ThemaincontributionoftheConstraintQueryLanguage(CQL)frameworkin[41]wastodemonstratethatitispossibletobridgethegapbetween:bottom-up,ecient,declarativedatabaseprogrammingandecientconstraintsolving.OnekeyintuitioncamefromCLP:aconjunctionofquantier-freeconstraintsoverkvariables,wherekdependsonthedatabaseschemaandnottheinstance,isthecorrectgeneralizationofthek-tupleorrecordorgroundfact.Thetechnicaltoolsforthisintegrationwere:datacomplexity[17,73]fromdatabasetheory,andquantiereliminationmethodsfrommathematicallogic[28,29,68,23,8,48,60].Morespecically,niterelationsaregeneralizedtonitelyrepresentablere-lationsandappropriatealgebrasfortheirdatamanipulationcanbedevelopedinthisframework.Inmanycases,thealgebrashavepolynomialtimedatacom-plexity.Thisuseofdatacomplexity(acommontoolforstudyingexpressibilityinnitemodeltheory)distinguishestheCQLframeworkfromarbitrary(andinherentlyexponential)theoremproving[30,9,15].Example1.Letusillustratedatabasequeryingandintroducesomeofitsno-tation.Themeaninganduseis(orrathershouldbe)intuitivelyobvious.Forformaldenitionswereferthereaderto[40,69].Toseetha