WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 


«В.С. Рублев Оптимизация SQL-запроса по трудоемкости и времени выполнения Рассмотрим задачу построения следующего запроса для таблиц определенных в примере ...»

В.С. Рублев

Оптимизация SQL-запроса по трудоемкости и времени выполнения

Рассмотрим задачу построения следующего запроса для таблиц определенных в

примере методических указаний «Проектирование реляционной базы данных и

интерфейса»:

Список грузов, которые везут наиболее нагруженные

корабли и при этом в минимальное число портов.

1. Один SQL-запрос

Сначала приведем уже построенный запрос.

Select Distinct c.Name

From ( Select Id -- ид. корабля с max грузом и min кол. портов грузов From Ships s, ( Select s.Id, -- выборка: ид.корабля, сумма грузов, кол. портов груз.

( Select Sum (Quantaty) as SumC -- сумма грузов корабля From Ships_Cargoes Where Id_ship=s.Id ), ( Select Count (Id_port_dest) as CountP -- кол.портов груз. кораб.

From ( Select Id_port_dest From Ships_Cargoes Where Id_ship=s.Id Group by Id_port_dest ) ) ) Where SumC = ( Select Max (SummC) -- max сумма грузов корабля From ( Select Sum (Quantaty) as SummC From Ships_Cargoes Where Id_ship=s.Id ) ) And CountP = ( Select Min (CntP) -- min кол.портов грузов корабля From ( Select Count (Id_port_dest) as CntP From ( Select Id_port_dest From Ships_Cargoes Where Id_ship=s.Id Group by Id_port_dest ) ) ), Ships_Cargoes sc, Cargoes c Where sc.Id_ship = Id And c.Id = sc.Id_cargo;

Такой запрос не только трудно написать. Большие затруднения вызывают его анализ и оценивание трудоемкости. К тому же он не оптимален по следующей причине: дважды находятся суммы грузов каждого корабля и количество портов, в которые везутся грузы каждого корабля. Поэтому в первую очередь займемся пошаговым построением этого запроса с одновременным анализом и оцениванием трудоемкости каждого шага.

2. Пошаговое построение запроса с оптимизацией трудоемкости

Для выражения оценки трудоемкости введем параметры:

–  –  –

такой группировки приводит в максимальном случае к дополнительной сортировке за (mlog m) операций, но так как первичный ключ таблицы Ships_Cargoes Id_ship, Id_port_dest, Id_cargo такие операции не нужны (будет не более m просмотров для образования групп и столько же для подсчета числа групп). Поэтому при введении индекса трудоемкость не увеличится.

2) Максимальный груз кораблей.

Select Max (SumC) into MaxSumC From (1);

Здесь (1) – запрос первого этапа. Так как этот запрос представляет таблицу размера n, то оценки трудоемкостей увеличиваются на n, что не изменяет оценок Tmax = (n·(m·p +log(n·m·p))), Tmin = (n·log(n)).

3) Список кораблей с максимальным грузом.

Select Id From (1) Where SumC = MaxSumC;

Здесь (1) – также запрос первого этапа. Полученный запрос имеет такую же трудоемкость, как и запрос второго этапа, и так как запросы эти не вложены, то максимальная и минимальная трудоемкость остаются такими же после этого этапа.

Tmax = (n·(m·p +log(n·m·p))), Tmin = (n·log(n)).

4) Наименьшее количество портов, в которые наиболее нагруженные корабли везут грузы.

Select Min(CountP) into MinCountP From (3);

Здесь (3) – запрос таблицы третьего этапа. Эта таблица в максимальном случае имеет размер n (каждый корабль везет максимальный груз), а в минимальном – 1 (только 1 корабль везет максимальный груз). Поэтому снова трудоемкость увеличивается на n, что не изменяет оценок Tmax = (n·(m·p +log(n·m·p))), Tmin = (n·log(n)).

5) Список наиболее нагруженных кораблей, которые везут грузы в наименьшее число портов.

Select Id From (1) Where SumC = MaxSumC and CountP = MinCountP;

Здесь (1) – также запрос первого этапа. Полученный запрос имеет такую же трудоемкость, как и запрос третьего этапа, если не считать трудоемкость четвертого этапа (подсчет MinCountP). Поэтому, выбирая максимальные оценки для этих этапов, получим Tmax = (n·(m·p +log(n·m·p))), Tmin = (n·log(n)).

6) Список грузов, которые везут наиболее нагруженные корабли в наименьшее число портов.

Select Distinct c.Name From (5), Ships_Cargoes sc, Cargoes c Where sc.Id_ship = Id and c.Id = sc.Id_cargo;

Здесь (5) – запрос пятого этапа. Эта таблица в максимальном случае имеет размер n (каждый корабль везет максимальный груз), а в минимальном – 1 (только 1 корабль везет максимальный груз). Трудоемкость без учета предыдущих этапов получается Tmax = (n·(m·p +log(n·m·p)), Tmin = (n·log(n)).

С учетом предыдущих этапов нужно добавить их трудоемкость, т. е. взять их максимум.

Поэтому получается окончательно Tmax = (n·(m·p +log(n·m·p))), Tmin = (n·log(n)).

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

Поэтому, собирая теперь запросы этапов, получим окончательное решение в виде 3 запросов:

Select Max (SumC) into MaxSumC -- максимальная сумма грузов корабля From (Select s.Id, ( Select Sum (Quantaty) as SumC -- сумма грузов корабля From Ships_Cargoes Where Id_ship=s.Id ) From Ships s;

);

Select Min(CountP) into MinCountP -- миним.кол.портов назнач.грузов наиб.нагр.кораблей From (Select s.Id, ( Select Count (Id_port_dest) as CountP -- кол.портов груз. кораб.

From ( Select Id_port_dest From Ships_Cargoes Where Id_ship=s.Id Group by Id_port_dest ) Where ( Select Sum (Quantaty) -- сумма грузов корабля From Ships_Cargoes Where Id_ship=s.Id ) = MaxSumC -- максимальна

–  –  –

/*** подсчет min кол. портов назначений грузов наиболее нагруженных кораблей ***/ For i In LoadShip.First..LoadShip.Last Loop If MinCntP LoadShip (i).CountP Then MinCntP := LoadShip (i).CountP;

End If;

End Loop;

/*** отметка наиболее нагруж.кораблей с наим.кол.портов назнач для грузов ***/ For i In LoadShip.First..LoadShip.Last Loop If MaxSumC = LoadShip(i).SumC and MinCntP = LoadShip (i).CountP Then Update Ships Set Priznak = 1 Where Id = LoadShip (i).Id ;

Else Update Ships Set Priznak = 0 Where Id = LoadShip (i).Id ;

End If;

End Loop;

/*** открытие курсора для грузов наиб.нагруж.кораблей с наим.кол.портов назнач.***/ Open ListCargoes For Select Distinct c.Name From Ships s, Ships_Cargoes sc, Cargoes c Where s.Priznak = 1 and sc.Id_ship = s.Id and c.Id = sc.Id_cargo;

Return ListCargoes;

End MaxLoadShipsWithMinPortDestCargoes;

Оценим теперь трудоемкость этого алгоритма сначала по циклам, а затем в целом.

1) Первый цикл образования вложенной таблицы совершает один проход по таблице

Ships_Cargoes. Поэтому его трудоемкость определяется размерами этой таблицы:

Tmax = (n·m·p), Tmin = (n).

2) Второй цикл подсчета минимального количества портов назначений для наиболее нагруженных кораблей определяется размерами построенной вложенной таблицы

LoadShip, а она равна n. Поэтому его трудоемкость:

Tmax = Tmin = (n).

3) Третий цикл отметки в таблице Ships наиболее нагруженных кораблей определяется размерами этой таблицы. Поэтому его трудоемкость такая же, как и для предыдущего шага.

4) Наконец, результирующий SQL-запрос содержит проход по таблице Ships (для выбора отмеченных кораблей) размера n, выбора в таблице Ships_Cargoes наиболее нагруженного корабля (в максимальном случае (log(n·m)), а в минимальном – (log(n))). Поэтому трудоемкость его выполнения:

Tmax = (n·log(n·m·p)), Tmin = (n·log(n)).

Суммируя трудоемкости, получаем окончательно:

Tmax = (n·(m·p +log(n·m·p))), Tmin = (n·log(n)).

Это в точности соответствует трудоемкости при других способах построения. Отметим, что во всех случаях максимальная трудоемкость Tmax = (n·m·p+n·log(n))) и она почти соответствует полученной ранее оценке снизу (n·m·p). Для того чтобы слагаемое n·log(n) имело существенное значение, необходимо, чтобы log(n) было значительно больше m·p, что практически нереально. Поэтому полученные алгоритмы практически оптимальны по трудоемкости. Но для выбора окончательного решения надо построить для каждого способа функции временной сложности и определить способ, дающий меньшее время

Похожие работы:

«О ТОРГОВОМ СБОРЕ С 1 ИЮЛЯ 2015 ГОДА НА ТЕРРИТОРИИ ГОРОДА МОСКВЫ УСТАНАВЛИВАЕТСЯ ТОРГОВЫЙ СБОР 1. 2| О торговом сборе Кто должен уплачивать торговый сбор Кто должен организации и индивидуальные предпринимауплачивать тели, осуществляющие следующую деятельность торговый на территории города Москвы: сбор:• торговлю чере...»

«XJ9900075 СООБЩЕНИЯ ОБЪЕДИНЕННОГО ИНСТИТУТА ЯДЕРНЫХ ИССЛЕДОВАНИЙ Дубна Р13-98-276 С.Б.Федоренко СТАБИЛИЗИРОВАННЫЙ ИСТОЧНИК ПОСТОЯННОГО ТОКА ДЛЯ ВОЗБУЖДЕНИЯ ЭЛЕКТРОМАШИТА БЕТА-СПЕКТРОМЕТРА Схема управления 3 0 12 ©Объединенный институт ядерных исследований. Дубна, 1998 В...»

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

«НЕОБЫЧНАЯ ГУРУ ЙОГА.ЛЕКЦИЯ 2 Итак, как обычно, вначале породите правильную мотивацию, думая, что мы будем жить в этом мире лишь несколько лет. Мы – лишь временные гости в этом мире и нам не нужно думать о том, как бы обустроиться в этом мире. Настоящее обустройство...»

«Материалы заданий олимпиады "Покори Воробьевы горы!" по обществознанию 2013-2014 гг. Заключительный этап. Задания для учащихся 10-11 классов. Каждый участник олимпиады должен выполнить задание, состоящ...»

«Р.Ш.Джарылгасинова Владимир Андреевич Никонов — выдающийся исследователь ономастики В творчестве выдающегося отечественного ученого (этнографа, географа, лингвиста, литературоведа), поэта, журналиста Владими...»

«Борьба с терроризмом Борьба с терроризмом и и защитазащитачеловека прав прав человека Руководство Руководство БДИПЧ Опубликовано Бюро ОБСЕ по демократическим институтам и правам человека (БДИПЧ) Al. Ujazdowskie 19...»

«13. Понимание Общая характеристика. Едва ли есть более сложный объект для понимания, чем само понимание. Являясь субъективным переживанием, порой очень сильным и внятным, оно тем не менее очень плохо поддается определению. Этимологически "понять" на с...»

«144 Мир России. 2003. № 2 АНАЛИТИЧЕСКИЕ ОБЗОРЫ Мы продолжаем публикацию аналитических обзоров Центра демографии и экологии человека Института народохозяйственного прогнозирования РАН. Журнал "Мир России" на протяжении мно...»







 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.