| Attributes | Values |
|---|
| type
| |
| Thesis advisor
| |
| Author
| |
| alternative label
| - Database systems, random allocations, some performance analysis studies
|
| dc:subject
| - Thèses et écrits académiques
- Algorithmes
- Probabilités
- Fonctions génératrices
- Bases de données relationnelles
- Analyse d'algorithmes et de structures de données
- Arbres de données relationnelles
- Loi de probabilité limite
- Tailles de relations dérivées
|
| preferred label
| - Bases de données, allocations aléatoires, quelques analyses de performances
|
| Language
| |
| Subject
| |
| dc:title
| - Bases de données, allocations aléatoires, quelques analyses de performances
|
| Degree granting institution
| |
| note
| - This thesis is devoted to the analysis of some parameters of interest for estimating the performance of computer systems, most notably database systems. The unifying features are the description of the phenomena to be studied in terms of random allocations and the systematic use of methods from the average-case analysis of algorithms. We associate a generating function with each parameter of interest, which we use to derive an asymptotic expression of this parameter.The main problem studied in this work is the estimation of the sizes of derived relations in a relational database framework. We show that this is closely related to the so-called \"occupancy problem\" in urn models, a classical tool of discrete probability theory. We characterize the conditional distribution of the size of a relation derived from relations whose sizes are known, and give conditions which ensure the a.symptotic normality of the limiting distribution. We next study the implementation of \"logical\" relations by multi-attribute or doubly chained trees, for which we give results on the complexity of a random orthogonal range query. Finally, we study some \"dynamic\" random allocation phenomena, such as the birthday problem, which models the occurrence of collisions in hashing, and a model of the Least Recently Used cache memory algorithm.
- Cette thèse est consacrée à l'étude de divers paramètres des tiques, entre autres des bases de données, qui ont pour point commun de se prêter naturellement à une modélisation en termes de phénomènes d'allocation aléatoire. Leur étude utilise les techniques classiques de l'analyse en moyenne des algorithmes, à savoir les séries génératrices et l'approximation asymptotique de leurs cœfficients. Le problème initialement posé concerne l'étude des tailles de relations dérivées dans l’algèbre relationnelle. Il admet une modélisation en termes de problèmes probabilistes d’allocation aléatoire, du type \"modèles d'urnes\". Nous donnons des résultats sur les lois de probabilité conditionnelles des tailles de relations obtenues par application des opérateurs de projection et jointure à une ou plusieurs relations de taille connue. En particulier, nous obtenons divers théorèmes sur les distributions limites de ces tailles, et montrons que, sous des hypothèses assez peu contraignantes, ces distributions limites sont fréquemment normales. Une extension naturelle est ensuite de regarder comment implémenter les relations \"logiques\", définies à un niveau abstrait ; nous étudions ici les arbres multi-attributs ou doublement chaînés.Les mêmes méthodes permettent enfin de traiter certains phénomènes d'allocation aléatoire de caractère plus dynamique, par exemple le classique \"paradoxe des anniversaires\" (qui modélise la fréquence d'apparition des collisions dans une table de hachage) ou l'algorithme de gestion mémoire \"Least Recently Used\".
|
| dc:type
| |
| http://iflastandar...bd/elements/P1001
| |
| rdaw:P10219
| |
| has content type
| |
| is primary topic
of | |
| is rdam:P30135
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
