Résumé: L'intérêt  du traitement parallèle devient
 très fort dans les applications qui exigent des performances de plus en plus
 élevées et en particulier dans les applications de bases de données,
 des entrepôts de données et  d'aide à la décision. Le parallélisme peut
 considérablement augmenter les performances de telles applications. Toutefois
 il n'est utile qu'en présence d'algorithmes réalisant des requêtes complexes
 sur des données dynamiques, irrégulières et distribuées. De tels algorithmes
 doivent être conçus pour répartir de manière équitable la charge des
 différents processeurs tout en réduisant au minimum les coûts des calculs 
 locaux  et de communication inhérents aux machines multi-processeurs.

 Les recherches ont montré que l'opération de jointure ne peut être
 parallélisable avec une accéléra-tion linéaire sur des architectures Shared
 Nothing que sous des conditions idéales d'équilibre des données. Le
 déséquilibre des données  peut avoir un effet dévastateur sur la performance.
 
  Dans le cadre de cette thèse, nous nous intéressons au problème d'équilibrage
  de charge pour le traitement de la jointure et de la multi-jointure sur des
  architecture Shared Nothing. Dans ce contexte, avons proposé une variété
  d'algorithmes pour le traitement de la jointure et la multi-jointure
  permettant de réduire les coûts de redistribution (et donc les coûts de
  communication) tout en traitant de manière très efficace les problèmes de
  déséquilibre des valeurs de l'attribut de jointure et des résultats de
  jointures. Nous avons étendu notre étude aux applications d'entrepôts de
  données par la proposition d'un algorithme efficace pour la maintenance des
  vues matérialisées dans un environnement Shared Nothing.
    
  L'analyse de complexité des différents algorithmes, a été réalisée en
  utilisant le modèle de coût BSP (Bulk synchronous parallelism). Ce modèle
  prévoit une accélération presque linéaire pour nos algorithmes. Les tests ont
  confirmé la validité de cette prévision et montré l'insensibilité des
  algorithmes aux données.
    
 
  Mots clés: Systèmes de gestion de bases de données parallèles,
  Parallélisme intra-transaction, Jointures parallèles, Multi-jointures,
  Déséquilibre des données, Déséquilibre des résultats de jointures,
  Équilibrage dynamique de charges,
  Data-warehouse.



 Abstract: The appeal of parallel processing becomes very strong in
 applications which require ever higher performance and particularly in
 database, data-warehousing and decision support applications. Parallelism 
 can greatly increase processing power in such
 applications. However parallelism can only maintain acceptable performance
 through efficient algorithms realizing complex queries on dynamic, irregular
 and distributed data. Such algorithms must be designed to fully exploit the
 processing power of multi-processor machines and the ability to evenly divide
 load among processors while minimizing local computation and communication
 costs inherent to multi-processors machines.


 Research has shown that the join operation is parallelizable with near-linear
 speedup on Shared Nothing machines only under ideal balancing conditions.
 Data skew can have a disastrous effect on performance.
 In this thesis, we consider the problem of handling data skew in parallel join
 operations on Shared Nothing machines.  To this end we have introduced
 many parallel join algorithms. They offer deterministic and near-perfect
 balancing properties. Their predictably low join-product and attribute-value
 skews make them suitable for repeated use in multi-join operations.  Their
 tradeoff between balancing overhead and speedup are analyzed using the
 BSP (Bulk synchronous parallel) cost model which
 predicts a negligible join product skew and a near-linear speedup for our
 algorithms. This prediction is confirmed by a series of tests.

 Related to data warehousing applications, we have introduced an efficient
 parallel algorithm for incremental view maintenance allowing to reduce the
 number of partial multi-joins involved in the incremental evaluation of
 materialized views. The analysis of its complexity shows that this algorithm
 has near perfect balancing properties.

 Key words :  Parallel Database Management Systems,
 Intra-transaction parallelism, Parallel joins, Multi-joins,
 Data skew, Join product skew, Dynamic load balancing, Data warehouse.