Tailles de relations d\'eriv\'ees~: \'Etude dynamique des projections

Dans une base de donn\'ees relationnelle, l'\'evaluation des tailles des relations obtenues par application d'op\'erateurs de l'alg\`ebre relationnelle (ici, projection ou jointure) joue un r\^ole fondamental en optimisation de requ\^etes. Nous consid\'erons la distribution de ces tailles, en supposant connues les tailles des relations initiales, et sous des hypoth\`eses assez larges sur la base de donn\'ees (existence de cl\'es, distributions de d\'epart non uniformes...). Nous nous int\'eressons dans le travail pr\'esent\'e ici \`a l'aspect dynamique du m\^eme probl\`eme, c'est-\`a-dire \`a l'\'evaluation des tailles de relations, initiales ou d\'eriv\'ees, lors d'une suite de requ\^etes (interrogations ou mises \`a jour). Apr\`es un rappel de la mani\`ere de repr\'esenter les relations, initiales et d\'eriv\'ees, par des allocations al\'eatoires de boules dans des urnes, nous pr\'esentons les op\'erations de mise \`a jour sur une relation initiale, et les processus al\'eatoires susceptibles de d\'ecrire sa taille, suivant les op\'erations retenues, le sch\'ema de la relation, et les \'etats de d\'epart et d'arriv\'ee. Nous \'etudions ensuite le cas d'une relation obtenue par une projection. Nous montrons que, sous des hypoth\`eses assez larges, la taille d'une telle relation peut \^etre d\'ecrite par un processus gaussien non markovien.