Базы данных оптимизация реляционной алгебры - PullRequest
Новая
       13

Базы данных оптимизация реляционной алгебры

1 голос
/ 27 ноября 2010

Я пытаюсь оптимизировать запрос; перевод SQL-запроса в реляционную алгебру и его оптимизация.

Мои схемы таблиц БД следующие: 

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

Где может быть много столбцов в Бегунах и Холмах.

Мой SQL-запрос: 

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

Итак, я мог бы начать делать: 

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

Или что-то вроде этого, а затем оптимизировать его с хорошим выбором объединений, но я не уверен, с чего начать

1 Ответ

3 голосов
/ 27 ноября 2010

Вы можете начать с использования нотации SQL-соединения: 

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

Затем вы можете заметить, что условие WHERE применяется только к Hills, поэтому вы можете опустить критерий поиска: 

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

Это стандартная оптимизация, которую оптимизатор SQL выполняет автоматически.На самом деле, вероятно, не стоит много переписывать первый показанный запрос, потому что оптимизатор может с ним справиться.Другая оптимизация, которую я вижу как возможную, - это продвижение операции DISTINCT на уровень: 

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

. При этом промежуточный набор результатов будет как можно меньше: R1 содержит список значений ID для людей, которые выполнялипо крайней мере один 1200-метровый (или это 1200-футовый?) холм, и его можно объединить 1: 1 с деталями в таблице «Бегуны».Было бы интересно посмотреть, сможет ли оптимизатор вывести нажатие DISTINCT для себя.

Конечно, в реляционной алгебре операция DISTINCT выполняется «автоматически» - каждый результат и промежуточный результатвсегда является отношением без дубликатов.

С учетом оригинальной нотации «реляционной алгебры»:

  • π Имя, Возраст (σ Высота> 1200 (Холмы × Бегуны × Беги))

Это соответствует первой приведенной выше инструкции SQL.

Тогда вторая инструкция SQL соответствует (более или менее):

  • π Имя, Возраст ((π MId (σ Высота> 1200 (холмы))) × Бегуны × Беги)

Тогда третьему оператору SQL соответствует (более или менее):

  • π Имя, Возраст ((π HId ((π MId (σ Высота> 1200 (холмы))) × Беги)) × Бегуны)

Где я предполагаю, что скобки заставляют реляционныеалгебра для оценки выражений по порядку.Я не уверен, что у меня там минимально возможное количество скобок, но те, которые есть, не оставляют много места для сомнений.

...