Local and global relational consistency

LocalandGlobalRelationalConsistencyRinaDechter1andPetervanBeek21DepartmentofInformationandComputerScienceUniversityofCalifornia,IrvineIrvine,California,[e-mail]2DepartmentofComputingScienceUniversityofAlbertaEdmonton,Alberta,[e-mail]ntobeanimportantconceptinthetheoryandpracticeofconstraintnetworks.Inthispaper,wepresentanewdenitionoflocalconsistency,calledrelationalconsistency.Thenewdenitionisrelation-based,incontrastwiththepreviousdenitionoflocalconsistency,whichwecharacterizeasvariable-based.Weshowtheconceptualpowerofthenewdenitionbyshowinghowituniesknowneliminationoperatorssuchasresolutionintheoremproving,joinsinrela-tionaldatabases,andvariableeliminationforsolvinglinearinequalities.Algorithmsforenforcingvariouslevelsofrelationalconsistencyarein-troducedandanalyzed.Wealsoshowtheusefulnessofthenewdenitionincharacterizingrelationshipsbetweenpropertiesofconstraintnetwork-sandtheleveloflocalconsistencyneededtoensureglobalconsistency.1IntroductionConstraintnetworksareasimplerepresentationandreasoningframework.Aproblemisrepresentedasasetofvariables,adomainofvaluesforeachvariable,andasetofconstraintsbetweenthevariables.Acentralreasoningtaskisthentondaninstantiationofthevariablesthatsatisestheconstraints.Ingeneral,whatmakesconstraintnetworkshardtosolveisthattheycancontainmanylocalinconsistencies.Alocalinconsistencyisaconsistentinstan-tiationofk1ofthevariablesthatcannotbeextendedtoakthvariableandsocannotbepartofanyglobalsolution.Ifweareusingabacktrackingsearchtondasolution,suchaninconsistencycanleadtoadeadendinthesearch.Thisinsighthasledtothedenitionofconditionsthatcharacterizetheleveloflocalconsistencyofanetwork[29,33]andtothedevelopmentofalgorithmsforenforcinglocalconsistencyconditionsbyremovinglocalinconsistencies(e.g.,[33,29,19,12,6]).Inthispaper,wepresentanewdenitionoflocalconsistencycalledrelationalconsistency3.Thevirtueofthenewdenitionoflocalconsistencyisthat,rstly,itremovestheneedforreferencingthearityoftheconstraintswhendiscussing3Apreliminaryversionofthisdenitionappearsin[37].relationshipsbetweenthepropertiesoftheconstraintsandlocalconsistency.Secondly,itisoperational,thusgeneralizingtheconceptofthecompositionoperationdenedforbinaryconstraints,andcanbeincorporatednaturallyinalgorithmsforenforcingdesiredlevelsofrelationalconsistency.Thirdly,ituni-esknownoperatorssuchasresolutionintheoremproving,joinsinrelationaldatabases,andvariableeliminationforsolvingequationsandinequalities,thusallowingtheformulationofaneliminationalgorithmthatgeneralizesalgorithmsappearingineachoftheseareas.Finally,itallowsidentifyingthoseformalismsforwhichconsistencycanbedecidedbyenforcingaboundedlevelofrelationalconsistency,likepropositionaldatabases,linearequalitiesandinequalities,andcrosswordpuzzlesfromgeneraldatabasesrequiringhigherlevelsofrelationalconsistency.Wealsodemonstratetheusefulnessofthenewdenitionincharac-terizingrelationshipsbetweenvariouspropertiesofconstraintnetworks|domainsizeandacyclicity|andtheleveloflocalconsistencyneededtoensureglobalconsistency.Followingdenitionandpreliminaries(section2),relationallocalconsistencyisdenedandalgorithmsforenforcingsuchconditionsareintroduced(section3).Section4showsthatthealgorithmsunifyalgorithmsappearinginpropositionaldatabasesandlinearinequalities.Finally,section5describesnewassociationsbetweenconstraintpropertiesandrelationallocalconsistencyneededforglobalconsistency.Discussionandconclusionsaregiveninsections6and7respectively.2DenitionsandPreliminariesDenition1(constraintnetwork).4AconstraintnetworkRisasetofnvariablesX=fx1;...;xng,adomainDiofpossiblevaluesforeachvariablexi,1in,andasetoftrelationsRS1,...,RSt,whereSiX,1in.AconstraintorrelationRSoverasetofvariablesS=fx1;...;xrgisasubsetoftheproductoftheirdomains(i.e.,RSD1Dr).ThesetofsubsetsfS1;...;StgonwhichconstraintsarespeciediscalledtheschemeofR.Abinaryconstraintnetworkisthespecialcasewhereallconstraintsareoverpairsofvariables.Aconstraintgraphassociateseachvariablewithanodeandconnectsanytwonodeswhosevariablesappearinthesameconstraint.Denition2(solutiontoaconstraintnetwork).Aninstantiationofthevari-ablesinX,denotedXI,isann-tuple(a1;...;an),representinganassignmentofai2Ditoxi,1in.Aconsistentinstantiationofanetworkisaninstan-tiationofthevariablessuchthattheconstraintsbetweenvariablesaresatised.Aconsistentinstantiationisalsocalledasolution.Theorderofthevariablesconstrainedbyarelationisnotimportant;thatis,wefollowtheset-of-mappingsformulationofrelations(see[34]).Thenotionofaconsistentinstantiationofasubsetofthevariablescanbedenedinseveral4Notethatallthedenitionsandalgorithmsareapplicabletorelationswithoutthenitenessassumption;apointwemakeexplicitinsection4.22ways.Weusethefollowingdenition:aninstantiationisconsistentifitsatisesalloftheconstraintsthathavenouninstantiatedvariables.Denition3(consistentinstantiationofsubsetsofvariables).LetYandSbesetsofvariables,andletYIbeaninstantiationofthevariablesinY.Wede-notebyYI