Conception de BD réparties et requêtes

échanges de messages

• http://www.scribd.com/doc/40225102/Netflix%E2%80%99s-Transition-to-High-Availability-Storage-Systems – fiche de lecture
• Lecture complémentaire :
  • Brewer's 2000 Talk : podc-keynote.pdf
  • Gilbert and Lynch's proof : 10.1.1.20.1495.pdf

Netflix : utilisation de S3 en high availability

• avantage et inconvénients
• application de recommandation

triplet : [utilisateur, filme, note (,date) ]

• matrice de notes filmes x utilisateurs
• histogramme du nombre de notes dans le temps
  • on scinde les notes en deux parties chronologiques : de début jusqu'à 2008, puis 2009 à … et prend la première partie pour définir le modèle de recommandation.
  • On valide la qualité de la recommandation avec la suite des données.
• Ils ont fait un concours (Netflix prize) pour la production d'un algorithme performant.

Oracle ne marchait plus. Ils ont essayé S3.

• Décomposition en BD locales
  • pour la durabilité, confidentialité d'une partie des données (banques, etc.), démarche couteuse qui doit se mériter
• Intégration logique des BD locales existantes
  • services de mash-up, par exemple
  • pas le sujet du jour aujourd'hui

On veut des morceaux fragments disjoints. Puis on les alloue aux différents sites, avec un peu de redondance si utile.

• fragmentation
  • trois types : horizontale, verticale, mixte
  • performances en favorisant les accès locaux
  • équilibrer la charge de travail entre les sites
• Duplication (réplication)
  • favoriser les accès locaux
  • augmenter la disponibilité des données

• Complète : chaque élément de R doit se trouver dans un fragment
• Reconstructible : on doit pouvoir recomposer R à partir de ses fragments
• Disjointe : chaque élément de R ne doit pas être dupliqué

• Round-robin : construire m lots en affectant ligne i à lot j = i mod m + 1. Utile pour des lectures séquentielles parallèles, guère autrement.
• Hashage sur attribut A :
  • t_i∈ R_j avec j = hash(t_i.A)
    • sélection (A=v): select * from R where hashkey = hash(A)
    • équi-jointure (A=B) : si A et B sont traités avec la même fonction de hashage : select * from R,S where R.A = S.B
• Par intervalle :
  • Fragmenter le domaine de l'attribut A en m intervalles
  • Vecteur \left\{a_1,\ldots ,a_{m-1}\right\}
  • t_i∈R_j avec a_{j-1} \leq T_i .A \lt a_j
  • sélection (“A between x and y”) : select * from R where 10 ≤ R.A < 100

On se rapproche à des fragmentation qui ressemble aux requêtes.

create table client1 as select * from client where ville = 'Paris';

create table client2 as select * from client where ville != 'Paris' ;

Une partie où ville = Paris et l'autre avec ville != Paris. On peut reconstituer la table initiale par union

create view client as select * from client1 union select * from client2;

voir slide

Utilisation d'une clè étrangère:

create table cde1 as select cde.* from cde, client1 where cde.client = client1.nclient

create table cde2 as select cde.* from cde, client2 where cde.client = client2.nclient

Propriétés de la fragmentation horizontale dérivée : recopier formules de slide 13

• R : fragmentation horizontale → fragments R_i
• S : fragmentation horizontale dérivée → fragments S_i
• complète
• disjointe
• reconstructible
• ⇒ contrainte d'intégrité référentielle

• exemple : sdss sky server
• Fragments définis par projection
  • cde1 = cde(ncde, nclient)
  • cde2 = cde(ncde, produit, qté)
• Reconstruction

: copier de slide 15

Un moteur de requête analyse la fragmentation par rapport au schéma de fragmentation, et génère des requêtes sur fragments. Puis, il fait une optimisation avec le schéma d'allocation.

voir slide 26

Règle : éliminer l'accès aux fragments inutiles.

Exemple :

• Client1 : Client where ville ='Paris'
• Client2 : Client where ville != 'Paris'
• select * from Client where ville='Lyon'
• ⇒ inutile de consulter Client1 car Lyon n'est jamais Paris

Règle : éliminer l'accès aux relations de base qui n'ont pas d'attributs utiles pour le résultat final

• Cde1 : Cde(ncode, nclient)
• Cde2 : Cde(ncode, produit, qt2)
• select nclient from Cde
• On a besoin des deux attributs de Cde1, et que l'attribut ncde de Cde2 pour la jointure
• Or Pncde(Cde1) = Pncde(Cde2) donc la jointure est inutile

Règle distribuer les jointures par rapport aux unions et appliquer les réduciton pour la fragmentation horizontale

: slides 28-31