Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних
The principles of relation queries processing and ways of their realization are considered. As the basic operation, influencing the efficiency of search performance, the operation of connection is allocated. Operation number minimization method in relation connection sequence search is offered. The...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/174120 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1867334384153001984 |
|---|---|
| author | Ponomarenko, L. A. Tanyanskiy, S. S. Filatov, V. A. |
| author_facet | Ponomarenko, L. A. Tanyanskiy, S. S. Filatov, V. A. |
| author_institution_txt_mv | [
{
"author": "L. A. Ponomarenko",
"institution": null
},
{
"author": "S. S. Tanyanskiy",
"institution": null
},
{
"author": "V. A. Filatov",
"institution": null
}
] |
| author_sort | Ponomarenko, L. A. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-07-26T17:25:36Z |
| description | The principles of relation queries processing and ways of their realization are considered. As the basic operation, influencing the efficiency of search performance, the operation of connection is allocated. Operation number minimization method in relation connection sequence search is offered. The optimality of such a method is proved. |
| first_indexed | 2025-07-17T10:25:52Z |
| format | Article |
| fulltext |
© Л.А. Пономаренко, С.С. Танянский, В.А. Филатов, 2003
Системні дослідження та інформаційні технології, 2003, № 2 53
TIДC
ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО
ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ ТА
МЕРЕЖІ
УДК 519.2 : 681.3
ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
СОЕДИНЕНИЙ ОТНОШЕНИЙ В ЗАПРОСАХ РЕЛЯЦИОННОЙ
БАЗЫ ДАННЫХ
Л.А. ПОНОМАРЕНКО, С.С. ТАНЯНСКИЙ, В.А. ФИЛАТОВ
Рассматриваются принципы обработки реляционных запросов и способы их
реализации. В качестве основной операции, влияющей на эффективность вы-
полнения запроса, выделена операция соединения отношений. Предложен ме-
тод минимизации числа операций при поиске последовательности соединения.
Доказана оптимальность такого метода.
ВВЕДЕНИЕ
Цель выполнения процедуры обработки запросов в реляционной базе дан-
ных — преобразование запроса, реализованного на языке высокого уровня,
например SQL, в корректную и эффективную последовательность действий,
представленную на языке низкого уровня в терминах операций реляционной
алгебры [1]. При этом важнейшим аспектом обработки запроса является его
оптимизация. В результате преобразования исходного запроса может быть
получено множество его эквивалентных вариантов.
Основная проблема оптимизации — это оценка сложности выполнения
вычислительных операций с большим количеством отношений. Как прави-
ло, на практике чаще всего выбирается стратегия ближайших оптимальных
решений. Большинство таких стратегий предусматривает эквивалентные
преобразования алгебраических выражений, на которых строится запрос.
Языки манипулирования данными высокого уровня позволяют форми-
ровать сложные запросы для баз данных с большим количеством отноше-
ний. Скорость обработки таких запросов может быть в значительной степе-
ни увеличена, если перед их выполнением модифицировать план
выполнения алгебраических операций. Цель таких модификаций — полу-
чить эквивалентное выражение, но требующее меньше времени и памяти
для его выполнения.
Одним из важных свойств, влияющих на эффективность запроса, явля-
ется последовательность вычисления соединений в цепочке операций реля-
ционной алгебры. Соединение — это определяющая операция, так как время
ее выполнения пропорционально времени выполнения операции объедине-
Л.А. Пономаренко, С.С. Танянский, В.А. Филатов
ISSN 1681–6048 System Research & Information Technologies, 2003, № 2 54
ния отношений. В качестве критерия сложности структуры запроса можно
выбрать оценку количества промежуточных операций соединения и порядок
выполнения коммутирующих и ассоциативных операций.
При подробном рассмотрении операции соединения можно отметить
важность способа ее вычисления. Выбранный способ может определяться
либо тем, как хранится отношение, либо наличием связанных дополнитель-
ных структур. При этом процедура вычисления может проводиться различ-
ными методами, например, последовательным или индексным доступом, с
учетом или без учета дубликатов и т.п.
Для организации эффективной реализации запроса необходимо рас-
смотреть технику управления файлами, взаимосвязь между обращениями к
внешней памяти и операциями реляционной алгебры, а также некоторые
технические характеристики вычислительной техники.
Рассматриваемые в статье способы реализации запроса используют
свойства операций алгебры и теории множеств. Дальнейшие выкладки бу-
дут основываться на свойствах операции соединения и правилах, позво-
ляющих осуществлять алгебраические преобразования [2].
АРХИТЕКТУРА ПЕРЕБОРА
Алгоритм перебора должен выбрать оптимальный план выполнения запроса
на основе исследования пространства поиска. Алгоритмы перебора многих
существующих систем рассчитаны на выбор только оптимального порядка
линейных соединений.
На практике желательно иметь такой алгоритм перебора, который мог бы
легко приспосабливаться к изменениям пространства поиска (добавление но-
вых преобразований, новых физических операций, например, новых реа-
лизаций соединений) и к изменениям методов оценки стоимости. Современ-
ные архитектуры оптимизации построены на основе этой парадигмы и
называются расширяемыми оптимизаторами [3].
Построение расширяемого оптимизатора — сложная задача, так как необ-
ходимы не только улучшенный алгоритм перебора, но и обеспечение инфра-
структуры для развития техники оптимизации. Однако общность архитектуры
должна быть сбалансирована с потребностью эффективного перебора. Таким
образом, одной из важных составляющих частей оптимизатора является нали-
чие эффективного метода перебора, определяющего последовательность вы-
полнения операций запроса.
МИНИМИЗАЦИЯ СУММЫ ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ
СОЕДИНЕНИЙ ОТНОШЕНИЙ БАЗЫ ДАННЫХ
Одним из критериев повышения эффективности выполнения запроса явля-
ется уменьшение числа кортежей в отношениях при многократном соедине-
нии. При условии, что операция соединения предполагает обращение к каж-
дому кортежу соединяемых отношений, возникает задача отыскания такой
последовательности, которая гарантирует наименьшее суммарное число об-
ращений к кортежам при последовательном соединении.
Построение оптимальной последовательности соединений отношений в запросах …
Системні дослідження та інформаційні технології, 2003, № 2 55
Пусть база данных R содержит шесть отношений { ),(),()( 21 RrRrRr =
})(),(),(),( 6543 RrRrRrRr , и пусть каждое отношение содержит соответст-
венно { }10,20,5,80,50,100)( =Rr кортежей.
Тогда при последовательном соединении, когда выполняется условие
654321 RRRRRRR = ,
суммарное количество просмотренных кортежей будет соответствовать вы-
ражению 54321 rrrrrr ++++= , где 501001 ∗=r ; 8012 ∗= rr ; 523 ∗= rr ;
2034 ∗= rr ; 1045 ∗= rr , т.е. 000405442)( =Rr .
Используя свойства ассоциативности и коммутативности операции со-
единения и изменяя общую последовательность соединения, можно умень-
шить (увеличить) значение )(Rr . Изменим последовательность операций.
Поменяем местами 1R и 6R , тогда отношение R′ будет представлено вы-
ражением
154326 RRRRRRR =′
и, соответственно, 404240500)( =′Rr . Таким образом, для вычисления отно-
шения R при такой последовательности потребуется на 50016438 дисковых
операций меньше. Учитывая, что количество перестановок конечно и соответ-
ствует !n (для данного примера !6 ), всегда можно получить наименьшую сум-
му последовательного произведения.
Пусть NxxxX n ∈= },...,,{ 21 , где N — множество натуральных чисел,
и пусть результаты операций произведения образуют множество
},...,,{ 21 mpppP = , где 211 xxp ∗= , nmm xppxpp ∗=∗= −1312 ,,… . Необ-
ходимо найти такую последовательность mppp ,...,, 21 , при которой
∑
=
→
m
i
ip
1
min .
Теорема о наименьшей сумме промежуточных результатов последова-
тельного произведения. Значение суммы промежуточных результатов ,ip
( mi ,,1…= ), последовательного произведения элементов множества
},...,,{ 21 nxxxX = будет наименьшим, если значения nxxx ,...,, 21 упорядо-
чены по возрастанию, т. е. nxxx <<< ...21 .
Доказательство. Упорядочим значения nxxx ,...,, 21 по возрастанию:
nxxx <<< ...21 . Запишем общий вид суммы промежуточных результатов
последовательных умножений элементов множества X при следующем
упорядочивании:
………… +∗∗∗+∗∗∗++∗ +−− 112112121 iiiii xxxxxxxxxxx
njijiji xxxxxxxxxxxxx ∗∗∗∗∗∗++∗∗∗∗+∗∗∗∗+ − ……………………… 2121121
и обозначим ее 1S .
Л.А. Пономаренко, С.С. Танянский, В.А. Филатов
ISSN 1681–6048 System Research & Information Technologies, 2003, № 2 56
Поменяем местами произвольные элементы ix и jx из множества X и
найдем сумму 2S промежуточных результатов последовательных умноже-
ний при такой перестановке:
………… +∗∗∗+∗∗∗++∗ +−− 112112121 ijiji xxxxxxxxxxx
njiijjj xxxxxxxxxxxxx ∗∗∗∗∗∗++∗∗∗∗+∗∗∗∗+ − ……………………… 2121121 .
Вычислим разность 12 SS −=∆ . С учетом коммутативности операции
умножения получаем
−∗∗∗∗++∗∗∗+∗∗∗=∆ −+−− )( 1211121121 jjijiji xxxxxxxxxxxxx ……………
=∗∗∗∗++∗∗∗+∗∗∗− −+−− )( 1211121121 jiiiiii xxxxxxxxxxxxx ……………
0)()( 1211121121 >∗∗++∗∗∗+∗∗∗−= −+−− jijiiij xxxxxxxxxxxxx ………… .
Таким образом, при последовательном перемножении некоторых зна-
чений Xxxx n ∈,...,, 21 сумма промежуточных результатов будет наи-
меньшей, если рассматриваемые значения упорядочены по возрастанию
nxxx <<< ...21 .
Из теоремы о наименьшей сумме промежуточных результатов последо-
вательного произведения следует, что при изменении порядка перемноже-
ния сумма результатов также изменится.
Поскольку операция соединения является коммутативной, последова-
тельность ее выполнения необязательно должна быть линейной. В частно-
сти, запрос для БД R может быть алгебраически представлен как
)()()( 654321 RRRRRRR = .
При такой последовательности значение )(Rr будет равно 000000400 ,
что значительно меньше предыдущих значений, полученных последова-
тельным выполнением операции соединения. В дальнейшем такую последо-
вательность будем называть парной.
За конечное число шагов можно найти такую последовательность пар
произведений, при которой сумма промежуточных результатов будет мини-
мальной. Отличие парного соединения от последовательного заключается в
том, что общая сумма промежуточных результатов достигается нескольки-
ми независимыми шагами. Сначала суммируются произведения произволь-
ных пар, после чего результаты перемножаются парами в произвольном по-
рядке, пока не будут перемножены все возможные варианты.
Теоретически не исключен вариант смешанного произведения, когда
часть операций выполняется линейно, а часть попарно [1]. Формулу та-
кого произведения можно представить как последовательность
)()()( 654321 RRRRRRR = .
Сравним результаты соединения, полученные различными способа-
ми. Для линейной, упорядоченной по значениям последовательности
Построение оптимальной последовательности соединений отношений в запросах …
Системні дослідження та інформаційні технології, 2003, № 2 57
132564 RRRRRRR = результат будет соответствовать зна-
чению 000000400)( =Rr . Для произвольного парного соединения вида
)()()( 536241 RRRRRRR = результат будет 00000040)( =Rr .
При произвольном смешанном способе соединения )( 21 RRR =
)()( 6543 RRRR результат будет 00000020)( =Rr .
Анализируя результаты, полученные различными способами, в контек-
сте рассматриваемой задачи необходимо сформулировать и решить задачу
поиска минимальной суммы промежуточных результатов на каждом шаге
выбора пары соединения. В общем случае задачу можно представить как
подбор таких значений из некоторого множества целых чисел, произведение
которых даст минимальную сумму промежуточных результатов.
Будем утверждать, что минимальная сумма произвольных пар произве-
дений достигается при перемножении наименьших и наибольших значений
заданного множества. Для доказательства этого факта рассмотрим теорему.
Теорема о наименьшей сумме промежуточных результатов парного
произведения. Пусть задано множество NxxxX n ∈= },...,,{ 21 , тогда ми-
нимум суммы парных произведений ( ) min
1,
→∑
=
n
ji
ji xx достигается при
{ }ni xxxx ,...,,min 21= и { }nj xxxx ,...,,max 21= .
Доказательство. Основываясь на том, что количество возможных пар
множества X конечно и зависит от перестановок элементов X(их количество
равно n!) покажем, что всегда можно найти такие пары элементов, которые
определят наименьшую сумму при перемножении.
Пусть Xxxxx lkji ∈,,, и пусть lkji xxxx <<< . Рассмотрим произве-
дение пар ki xxp ∗=1 , lj xxp ∗=2 , li xxp ∗=3 и kj xxp ∗=4 . Покажем, что
)()( 4321 pppp +>+ .
Представим комбинацию парных произведений элементов ,, ji xx
lk xx , как произведение разностей )()( klij xxxx −∗− . Очевидно, что
0)( >− ij xx и 0)( >− kl xx . Таким образом 0)()( >−∗− klij xxxx . Рас-
крыв скобки, получим неравенство 0>+−− kikjlilj xxxxxxxx . Сгруппи-
ровав отрицательные и положительные пары произведений, получим
kjlikilj xxxxxxxx +>+ , т. е. )()( 4312 pppp +>+ .
Применяя это свойство ко всем элементам множества X , всегда можно
получить наименьшую сумму промежуточных результатов, в среднем за
!2n возможных перестановок. Таким образом, начиная с любой пары за ко-
нечное число шагов можно найти последовательность, соответствующую
минимальной сумме произведений элементов множества X .
Из теоремы о минимальной сумме парных произведений следует, что
для упорядоченной последовательности элементов алгоритм составления
пар произведений должен выбирать крайние элементы (минимальный и
максимальный) и перемещаться к середине множества, пока не cтанут рав-
ны индексы сдвига справа и слева.
Л.А. Пономаренко, С.С. Танянский, В.А. Филатов
ISSN 1681–6048 System Research & Information Technologies, 2003, № 2 58
ОБОБЩЕННАЯ ЗАДАЧА ПОСТРОЕНИЯ ПЛАНА ВЫПОЛНЕНИЯ
ЗАПРОСА
Во многих системах последовательность операций соединения синтаксиче-
ски ограничена. Как было показано выше, парная последовательность со-
единений требует вычислительных затрат на создание промежуточных от-
ношений. Хотя такая последовательность приводит к более эффективному
плану выполнения запроса, она значительно увеличивает вычислительные
затраты на перебор пространства поиска. С другой стороны, более сущест-
венна не стоимость генерации синтаксических порядков соединений, а про-
цедура выбора физических операций и оценка каждого возможного плана.
Для каждой таблицы статистическая информация содержит число кортежей
в структуре потока данных и соответствующие требования к буферам опе-
ративной памяти. Важно различать статистические свойства выполнения
запроса и вычислительные затраты, связанные с построением плана [4].
ЗАКЛЮЧЕНИЕ
Полученные в статье результаты позволяют формализовать алгоритм вы-
полнения операций соединения отношений в запросе и при этом минимизи-
ровать число кортежей на промежуточных итерациях. Общая задача по-
строения плана выполнения запроса сводится к оценке вычислительных
затрат по заданным критериям. Разработанные преобразования запросов
позволяют в значительной степени увеличить скорость их обработки путем
модификации плана выполнения алгебраических операций.
ЛИТЕРАТУРА
1. Коннолли Т., Бегг К., Страчан А. Базы данных: проектирование, реализация и
сопровождение. Теория и практика. 2-е изд. / Пер. с англ.: Учеб. пособие. —
М.: Издательский дом «Вильямс», 2000. — 1120 с.
2. Ульман Дж. Основы систем баз данных / Пер. с англ. М.Р. Когаловского и
В.В. Когутовского. Под ред. М.Р. Когаловского. — М.: Финансы и стати-
стика, 1983. — 334 с.
3. Чаудхари С. Методы оптимизации запросов в реляционных системах // Систе-
мы управления базами данных. — 1998. — № 3.— С. 22–27.
4. Пономаренко Л.А., Філатов В.О. Програмні агентні технології в адмініструванні
баз даних // Вісник Київського торговельно-економічного університету.
Вип. 3. — 2001. — С. 68–73.
Поступила 05.03.2003
|
| id | journaliasakpiua-article-174120 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:25:52Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/75/82cfe8de1bac4415b03415ef498ef975.pdf |
| spelling | journaliasakpiua-article-1741202019-07-26T17:25:36Z Construction of optimal relation connection sequence in database queries Построение оптимальной последовательности соединений отнрошений в запросах реляционной базы данных Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних Ponomarenko, L. A. Tanyanskiy, S. S. Filatov, V. A. The principles of relation queries processing and ways of their realization are considered. As the basic operation, influencing the efficiency of search performance, the operation of connection is allocated. Operation number minimization method in relation connection sequence search is offered. The optimality of such a method is proved. Рассматриваются принципы обработки реляционных запросов и способы их реализации. В качестве основной операции, влияющей на эффективность выполнения запроса, выделена операция соединения отношений. Предложен метод минимизации числа операций при поиске последовательности соединения. Доказана оптимальность такого метода. Розглядаються принципи обробки реляційних запитів і способи їхньої реалізації. Як основну операцію, що впливає на ефективність виконання запиту, виділено операцію з’єднання відношень. Запропоновано метод мінімізації кількості операцій під час пошуку послідовності з’єднань. Доведено оптимальність такого методу. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-07-26 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/174120 System research and information technologies; No. 2 (2003); 53-58 Системные исследования и информационные технологии; № 2 (2003); 53-58 Системні дослідження та інформаційні технології; № 2 (2003); 53-58 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/174120/174081 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Ponomarenko, L. A. Tanyanskiy, S. S. Filatov, V. A. Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних |
| title | Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних |
| title_alt | Construction of optimal relation connection sequence in database queries Построение оптимальной последовательности соединений отнрошений в запросах реляционной базы данных |
| title_full | Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних |
| title_fullStr | Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних |
| title_full_unstemmed | Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних |
| title_short | Побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних |
| title_sort | побудова оптимальної послідовності з’єднань відношень у запитах реляційної бази даних |
| url | https://journal.iasa.kpi.ua/article/view/174120 |
| work_keys_str_mv | AT ponomarenkola constructionofoptimalrelationconnectionsequenceindatabasequeries AT tanyanskiyss constructionofoptimalrelationconnectionsequenceindatabasequeries AT filatovva constructionofoptimalrelationconnectionsequenceindatabasequeries AT ponomarenkola postroenieoptimalʹnojposledovatelʹnostisoedinenijotnrošenijvzaprosahrelâcionnojbazydannyh AT tanyanskiyss postroenieoptimalʹnojposledovatelʹnostisoedinenijotnrošenijvzaprosahrelâcionnojbazydannyh AT filatovva postroenieoptimalʹnojposledovatelʹnostisoedinenijotnrošenijvzaprosahrelâcionnojbazydannyh AT ponomarenkola pobudovaoptimalʹnoíposlídovnostízêdnanʹvídnošenʹuzapitahrelâcíjnoíbazidanih AT tanyanskiyss pobudovaoptimalʹnoíposlídovnostízêdnanʹvídnošenʹuzapitahrelâcíjnoíbazidanih AT filatovva pobudovaoptimalʹnoíposlídovnostízêdnanʹvídnošenʹuzapitahrelâcíjnoíbazidanih |