Chapitre VII Les bases de données déductives

ChapitreVIILesbasesdedonneesdeductives244ConceptetMotivationL'ideeestdecouplerunebasededonneeaunensemblederegleslogiquesquipermettentd'endeduiredel'information.Celapourraitsefairedanslecontexted'unlangagedeprogrammation,maisonsouhaiteuncouplageplusdirectquipermetdemanipulerlesdonneesauniveaudelabasededonnees.Lesquestionsquiseposentsontlessuivantes.{Quellesestlaformedesreglesquel'onsouhaiteutiliser?Commentlesinterpreter?{Lesrequ^etesexpressiblesenSQLpeuvent-elles^etreexprimeespardesregles?{Lesreglespeuvent-ellesexprimerplus?245DenitionspreliminairesUnebasededonneesdeductive(BDD)estconstituee{d'unensembledepredicats(relations),ditsdebaseouextensionnels,dontl'extensionestconserveeexplicitementdanslabasededonnees:labasededonneesextensionnelle{d'unensembledepredicats(relations),ditsderivesouintentionnels,dontl'extensionestdeniepardesreglesdeductives:labasededonneesintentionnelle246Exemple:Basededonneesextensionnelle:Predicatparenta2arguments(ourelationparenta2attributs)parentannabobbobchrisbobdandanericBasededonneesintentionnelle:Predicatgrandparenta2arguments(ourelationgrandparenta2attributs)grandparent(X,Y) parent(X,Z)ANDparent(Z,Y)247Lelangagedesreglesdeductives:DatalogSyntaxe{Untermeestsoitunevariable,soituneconstante.Exemples:{X,Y,Z, {anna,bob,chris,dan,eric, {Uneformuleatomiqueouunatomeestunsymbolepredicatifappliqueaunelisted'argumentsquisontsoitdesvariables,soitdesconstantes,i.e.,destermes.Unsymbolepredicatifpeut^etre{Unnomdepredicatdebase(extensionnel),{Unpredicatderive(intentionnel),{Unerelationarithmetique(=,, ).248Exemples:{Symbolespredicatifs:parent(extensionnel),grandparent(intentionnel), {Atomes:parent(bob,chris),parent(X,Z),grandparent(X,Y),XY, {Uneregle(deductive)estuneformuledelaformeq(t) [NOT]p1(t1)AND:::AND[NOT]pn(tn)ouq(t)etp1(t1), ,pn(tn)sontdesformulesatomiques.{q(t)estlat^etedelaregle(cequiestdeni){[NOT]p1(t1)AND:::AND[NOT]pn(tn)estlecorpsdelaregle(laconditiondedenition)Exemple:grandparent(X,Y) parent(X,Z)ANDparent(Z,Y)249Restrictionssurlesreglesdeductivesq(t) [NOT]p1(t1)AND:::AND[NOT]pn(tn)1.Lespredicatsapparaissantdanslat^ete(membredegauche)dereglessontuniquementdespredicatsderives(intentionnels).Donc,lesreglesneserventpasadenirdespredicatsextensionnels,maisuniquementdespredicatsintentionnels.2.Conditionsdes^urete:toutevariableutiliseedansuneregledoitappara^tredansaumoinsunatomedontlepredicatrepresenteunerelationetquin'estpaspreceded'unenegation.Las^ureteapourbutdegarantirquel'evaluationdesreglesestpossible.Exemples:{Reglenons^ure:q(X;Y) p(X;Z)ANDNOTr(X;Y;Z)ANDXY{Regles^ure:q(X) p(X)ANDX0250L'interpretationdesreglesdatalogLaquestionestdesavoircommentcalculerl'extensiondespredicatsintentionnelsdenispardesreglesdatalog.Onprocedecommesuit.1.Siunpredicatintentionnelestlat^etedeplusieursregles,sonextensionestl'uniondesextensionsdonneesparlesdierentesregles.2.Pourchaqueregle,onconsideretouslestuplesdesrelationsextensionnellesnonprecedeesd'unenegationgurantdanslecorpsdelaregle.Pourchaquecombinaisondetuples,si{lestuplessontcompatiblesaveclesoccurrencesdespredicatsextensionnels(attributspourlesquelsunevaleurconstanteestdonneeayantcettevaleur),{lespredicatsrelationnelsniesetlespredicatsarithmetiquessontsastait,onajouteletupledeniparlaregle.Las^uretegarantitquel'onaainsiprisencomptetouteslesvaleurspossibles.251L'interpretationdesreglesdatalog:exempleSupposonsquelarelationparentaitl'extensionsuivante:parentannabobbobchrisbobdandanericL'evaluationdelareglegrandparent(X,Y) parent(X,Z)ANDparent(Z,Y)donnelarelationgrandparentannachrisannadanboberic252Del'algegrerelationnelleadatalogLesoperationsdel'algebrerelationnellepeuventaisementsecoderendatalog.r[s:rus(t1) r(t1)rus(t1) s(t1)rs:rms(t1) r(t1)ANDNOTs(t1)rs:rts(t1;t2) r(t1)ANDs(t2)r1s:rjs(t1[t2) r(t1)ANDs(t2)Xr:pr(t1\X) r(t1)Cr:sr(t1) r(t1)ANDC(t1)Pourtraduireuneexpressioncomplexedel'algebrerelationnelle,ondenitunpredicatintensionnelparsous-formuledel'expression.253StructuredesreglesetrecursivitePourunensembledereglesdonne,legraphedesreglesestdenicommesuit.{Ilyaunnuddanslegraphepourchaquesymbolepredicatif.{Ilexisteunarcd'unnudpaunnudqssiilexisteuneregledelaformeq() :::p():::Unensembledereglesestrecursifsisongraphecomporteuncycle.Exemple:ancetre(X,Y) parent(X,Y)ancetre(X,Y) parent(X,Z)ANDancetre(Z,Y)parentancetreSiunensembledereglesestrecursif,onestameneautiliserunpredicatintentionneldansunereglequiledenit.Commentfairepourevaluercepredicat?254L'evaluationdesreglesrecursives{Leprincipeutilisepourevaluerlesreglesrecursivesestdenemettredansl'extensiondespredicatsintentionelsrecursifsquelestuplesquidoiventygurer.{Oncommencedoncavecuneextensionvidepourcespredicats,etl'onappliquelesreglesjusqu'acequel'onobtienneuneextensionstablepourlesregles.C'estcequel'onappelleunpointxe(xpoint).{Cetteapprocheestpossible,pourautantquelespredicatsdenisrecursivementnesoientpasdanslaporteed'unoperateurNOT.255L'evaluationdesreglesrecursives:exempleConsideronslepredicatextensionnelparentdontl'extensionestparentannabobbobchrisbobdandanericetlepredicateintentionnelanc^etredeniparancetre(X,Y) parent(X,Y)ancetre(X,Y) parent(X,Z)ANDancetre(Z,Y)256L'extensioncalculeepouranc^etreserasuccessivementanc^etreannabobbobchrisbobdandanericanc^etreannabobbobchrisbobdandanericannachrisannadanbobericanc^etreannabobbobchrisbobdandanericannachrisannadanbobericannaeric257NegationetrecursionLanegationetlarecursionpeuvent^etreutiliseessimultanement,pourautantqu'ellesn'interagissentpas.{Onimposeunerestriction:lesreglessontstratiees.Siunereglecomporteunenegationq() :::NOTp():::iln'yapasdechemindeqapdanslegraphedesregles.{Legraphedesreglespeutalors^etrestratie(diviseencouches):iln'yapasderecursionentrecouchesetdansuneregledenissantunpredicatd'unecouche,lanegationn'estappliqueequ'adespredicatsdescouchesinferieures.{L'evaluationdel'extensiondespredicatsderivespeutalorssefairecoucheparcouche.258Expressivite{Lespredicatsdenispardesreglesnonrecursivespeuvent^etreexprimesenalgebrerelationnelle.{Lespredicatsdenispardesreglesrecursivesnepeuventpastoujours^etreexprimesenalgebrerelationnelle.Exemple:Lafermeturetransitived'unerelation(tellequelarelationancetre,parexemple).Eneet,lacalculernecessitel'applicationd'unnombred'operationsquidependducontenudelabasededonnees.259