Abstract FR:

Nous introduisons un raffinement de la resolution sld, la resolution sldal-scindee ensembliste qui permet de suivre la propagation des liaisons et surtout de rendre compte du traitement ensembliste des requetes et des reponses, specifique aux bases de donnees. Nous construisons un modele algebrique de calcul de la methode d'evaluation requete-sousrequete par abstraction a partir d'un type particulier d'arbres sldal-scindes ensemblistes. Dans notre modele, construit pour les programmes simplement lineaires (au plus un atome intensionnel dans le corps), les ensembles de substitutions sont manipules par des operateurs algebriques et les pre-ordres de powerdomains utilises permettent de simuler la technique al (tabulation). Ceci permet d'integrer dans un cadre unique les principes de tabulation et de resolution et la gestion des substitutions. Nous montrons que les deux suites convergentes de notre espace d'evaluation expriment egalement la semantique de la methode des ensembles magiques. Ce qui nous permet de demontrer l'equivalence entre cette methode et la methode requete-sousrequete pour la classe des programmes simplement lineaires. Nous indiquons egalement comment etendre notre modele a des programmes datalog quelconques (sans negation)