Étude des opérateurs relationnels et application à la gestion des bases de données / François Bancilhon

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

ISBN : 2-7261-0461-4

Bases de données -- Gestion

Structures de données (informatique)

Bases de données relationnelles

Université Paris-Sud (1970-2019) (Organisme de soutenance / degree-grantor)

Université de Paris-Sud. Faculté des sciences d'Orsay (Essonne) (Autre partenaire associé à la thèse / thesis associated third party)

Relation : Etude des opérateurs relationnels et application à la gestion des bases de données / François Bancilhon ; [sous la direction de Claude Delobel] / [Lieu de publication inconnu] : [éditeur inconnu] , 1981

Résumé / Abstract : Une base de données est constituée par une collection de relations. Chaque relation est représentée par un descripteur R, prenant des valeurs Rt qui sont des tableaux finis de n-uplets. L'ensemble des descripteurs de relations forment le descripteur de la base ℝ un ensemble de valeurs des relations de ℝ constitue une valeur de la base ℝt. Les contraintes d'intégrité ℂ auxquelles doivent satisfaire les valeurs de la base définissent un schéma < ℝ│ℂ >. On note S l'ensemble des valeurs de ℝ satisfaisant ℂ. On étudie ici les opérateurs relationnels c'est-à-dire les fonctions f : S → f(S) définies sur S. On montre tout d'abord que la notion d'opérateur recouvre des situations multiples : requêtes, traduction de base, vue usager sur une base, répartition de données dans un système distribué etc. Le reste de la thèse est structuré en deux parties : 1) l'étude de la structure de l'ensemble des opérateurs ; 2) l'application de cette étude à la résolution de problèmes concrets. Structure de l’ensemble des opérateurs. Sur l'ensemble des opérateurs relationnels outre l'opération classique de composition (f o g) on définit l'opération de juxtaposition f x g telle que f x g(x) = (f(x),g(x)). On définit ensuite une relation d'ordre partiel la dominance. On dit que f domine g (f ≥ g) ssi f(x) = f(y) → g(x) = g(y), (Intuitivement connaître la valeur de f c'est connaître celle de g). Deux opérateurs particuliers lS (l'identité sur S) et OS (la fonction constante sur S) sont définis et l'on a : V f, OS ≤ f ≤ lS. La notion d'équivalence (f ≡ g) découlant de la dominance est ensuite introduite (f ≡ g ssi f ≥ g et g ≥ f). On montre enfin que tout couple d'opérateurs f et g a une borne supérieure (f v g) et une borne inférieure (f Λ g) uniques (à une équivalence près). Il est montré que f v g ≡ f x g. Enfin, on dit que g est complément de f ssi f x g = lS, et l'on montre que l'ensemble des compléments de f a une borne inférieure complément de f ssi f ≡ OS ou f ≡ lS. Notion d’indépendance entre opérateurs. On dit que f et g sont indépendants (f ∼ g) ssi f x g(S) = f(S) x g(S), cela correspond au fait que la connaissance de f ne nous apporte aucune information sur g. Après avoir montré que ce cas était assez rare, on définit l'indépendance conditionnelle comme suit f et g sont indépendants modulo h (f ∼ g mod h) ssi f x g(B) = f(B) x g(B) pour tout B ℇ S/h. Ce qui signifie que f et g sont indépendants sur les parties de S où h est constant. Il sera montré plus loin que dans le cas où S est fini et où toutes les valeurs de ℝ sont équiprobables ces définitions se ramènent à celles de l'indépendance des variables aléatoires. On montre enfin que f Λ g est un minorant de l'ensemble Mod(f, g) = {h│f ∼ g mod h}. Dans le cas optimal où f Λ g ℇ Mod(f, g) on dit que f et g sont faiblement indépendants. Application à l’étude de la décomposition. Une décomposition est définie comme un couple d'opérateurs (f, g) généralisant ainsi le cas de la décomposition par projection à des opérateurs quelconques. Une décomposition est sans perte d'information (SPI) si f x g = lS. Des conditions de décomposition SPI sont données dans des cas particuliers. On étudie ensuite la caractérisation des "bonnes" décompositions. Il est d'abord montré que dans le cas où f et g sont indépendants les parties f(R) et g(R) peuvent être gérées indépendamment. Pour faire une analyse plus fine on définit admissible (ℝ₁│ℝ₂) l'ensemble des mises à jour qui peuvent être faites sur ℝ₁ = f(ℝ) sans modifier g(ℝ) = ℝ₂. Les parties f(ℝ) et g(ℝ) peuvent être mises à jour de façon autonome ssi l'ensemble admissible (ℝ₁│ℝ₂) ne dépend pas de ℝ₂. Il e ensuite montré que cette condition est réalisée ssi f et g sont faiblement indépendants. […]