Bases de données Optimisation de l'algèbre relationnelle

Question

J'essaie d'optimiser les requêtes; prendre une requête SQL en algèbre relationnelle et l'optimiser.

Mes db schémas tables sont les suivantes:

Hills(MId, Mname, Long, Lat, Height, Rating,...) 
Runners(HId, HName, Age, Skill,...) 
Runs(MId, CId, Date, Duration) 

où il peut y avoir de colonnes dans les coureurs et les collines.

Ma requête SQL est:

SELECT DISTINCT Runners.HName, Runners.Age 
FROM Hills, Runners, Runs 
WHERE Runners.HId = Runs.HId AND Runs.MID = Hills.MId AND Height > 1200 

donc je pourrais commencer par faire:

π Name, Age(σ Height > 1200 (Hills × Runners × Runs)) 

Ou quelque chose comme ça et l'optimisation avec un bon choix de jointures, mais je ne suis pas sûr où commencer

Answer 1

Vous pouvez commencer par utiliser la notation SQL JOIN:

SELECT DISTINCT P.HName, P.Age 
    FROM Hills AS H 
    JOIN Runs AS R ON H.MId = R.MId 
    JOIN Runners AS P ON P.HId = R.HId 
WHERE H.Height > 1200 

Vous pouvez ensuite observer que la condition WHERE applique uniquement aux collines, de sorte que vous pouvez appuyer sur le critère de recherche:

SELECT DISTINCT P.HName, P.Age 
    FROM (SELECT MId FROM Hills WHERE Height > 1200) AS H 
    JOIN Runs AS R ON H.MId = R.MId 
    JOIN Runners AS P ON P.HId = R.HId 

C'est une optimisation standard - et qui l'optimiseur SQL fera automatiquement. En fait, cela ne vaut probablement pas la peine de faire beaucoup de réécriture de la première requête affichée car l'optimiseur peut s'en occuper. L'autre optimisation que je vois que possible pousse l'opération DISTINCT bas niveau:

SELECT P.HName, P.Age 
    FROM (SELECT DISTINCT R.HId 
      FROM (SELECT MId FROM Hills WHERE Height > 1200) AS H 
      JOIN Runs AS R ON H.MId = R.MId 
     ) AS R1 
    JOIN Runners AS P ON P.HId = R1.HId 

Cela permet de maintenir le résultat intermédiaire aussi petit que possible: R1 contient une liste d'ID-valeurs pour les personnes qui ont couru au moins une colline de 1200 mètres (ou est-ce 1200 pieds?), et peut être jointe 1: 1 avec les détails dans le tableau des coureurs. Il serait intéressant de voir si un optimiseur est capable de déduire le push-down du DISTINCT pour lui-même.

Bien sûr, en algèbre relationnelle, l'opération DISTINCT est faite 'automatiquement' - chaque résultat et résultat intermédiaire est toujours une relation sans doublon.

---

Compte tenu de la notation 'algèbre relationnelle' originale:

• Nom, âge (σ Hauteur> 1200 (Hills × Runners × Runs))

Cela correspond à la première Instruction SQL ci-dessus.

La deuxième instruction SQL correspond alors (plus ou moins) à:

• π Nom, âge ((π MId (σ Hauteur> 1200 (Hills))) × Coureurs × Runs)

La troisième instruction SQL correspond alors (plus ou moins) à:

• Nom, âge ((π Hid ((π MId (σ Hauteur> 1200 (Hills))) × Runs)) × coureurs)

Où je suppose que les parenthèses forcent l'algèbre relationnelle pour évaluer les expressions dans l'ordre. Je ne suis pas sûr d'avoir le nombre minimum de parenthèses, mais ceux qui sont là ne laissent pas beaucoup de place à l'ambiguïté.