ОПТИМИЗАЦИЯ АЛЬТЕРНАТИВНЫХ СОЕДИНЕНИЙ В ЗАПРОСАХ РЕЛЯЦИОННЫХ СИСТЕМ

Авторы
Файлы

Погодаев А.К. Муравейко А.Ю. Дятчина Д.В. Статья в формате PDF 112 KB Существующие подходы оптимизации запросов предполагают инвариантную схему соединения таблиц [1]. Однако, в базах данных (БД) сложных структур при динамичном изменении объема таблиц ранее запланированные варианты операций соединения с течением времени могут оказаться не оптимальными в плане скорости их выполнения.

Время выполнения запроса можно представить в виде формулы:

, где =1, если i-ая таблица, принадлежит запросу; 0 - иначе; n-количество таблиц; - объем блока; - объем i-й таблицы; - время открытия i-й таблицы; - время закрытия i-й таблицы; - время чтения блока; - общее время выполнения операций соединения.

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

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

(1)

где , - нагрузка на i-ю вершину; = 1, если i-ая вершина, принадлежит подграфу, 0 - иначе; n - количество вершин; y_j= 1, если j-ая дуга принадлежит подграфу, 0 - иначе; m - количество дуг; - нагрузка на j-ю дугу.

Для задачи (1) существуют методы решения (например [2]), но они ограниченны определенной предметной областью и специфической структурой графа. Поэтому для случая, когда граф имеет произвольную структуру, разработан следующий алгоритм оптимизации на графе.

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

Выводы: разработаны методика выбора оптимального маршрута соединения таблиц в БД, имеющих сложную структуру организации данных; алгоритм поиска оптимального маршрута соединения отмеченных вершин на графе, имеющем циклы, с нагруженными вершинами и дугами.

СПИСОК ЛИТЕРАТУРЫ

Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. Пер. с англ.- М.: Издательский дом «Вильямс», 2003 - 1088 с.
Погодаев А.К., Анненков А.В. Метод оптимизации графов с нагруженными вершинами /Вестник ЛГТУ - ЛЕГИ 2001 №1(7) - 37-39с.

ИНТЕНСИВНОСТЬ ДЕЗАГРЕГАЦИИ ТРОМБОЦИТОВ У ЛИЦ ПОЖИЛОГО И СТАРЧЕСКОГО ВОЗРАСТА С ФИЗИОЛОГИЧЕСКИМ И ПАТОЛОГИЧЕСКИМ ТИПОМ СТАРЕНИЯ

Статья в формате PDF 162 KB...

11 10 2026 5:14:29

ИЗУЧЕНИЕ АНТРОПОГЕННОЙ НАГРУЗКИ ПРОМЫШЛЕННОГО РАЙОНА ГОРОДА СТАВРОПОЛЯ МЕТОДОМ ЛИХЕНОИНДИКАЦИИ

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

10 10 2026 23:57:27

ДИНАМИКА АДАПТАЦИОННОГО ПРОЦЕССА КАРДИО-РЕСПИРАТОРНОЙ СИСТЕМЫ К НОРМОБАРИЧЕСКОЙ ГИПОКСИЧЕСКОЙ ГИПОКСИИ

Статья в формате PDF 106 KB...

09 10 2026 22:18:41

ЭТИОЛОГИЧЕСКАЯ СТРУКТУРА ОНИХОМИКОЗОВ У БОЛЬНЫХ ПСОРИАЗОМ

Статья в формате PDF 174 KB...

08 10 2026 4:57:31

ЭКОЛОГИЧЕСКОЕ РЕГУЛИРОВАНИЕ ЧИСЛЕННОСТИ ПОПУЛЯЦИЙ МЕЛКИХ МЛЕКОПИТАЮЩИХ

На основании многолетних наблюдений за комплексом внешних условий и состоянием популяций мелких млекопитающих количественно оценено распределение влияний внутрипопуляционных и внешних факторов на динамику их численности и структуры. Показано, что основное влияние на демографические процессы полевок на протяжении всего сезона размножения оказывают плотностно-зависимые механизмы регуляции (эндогенные факторы). Экзогенные (хищники, кормовые и погодные) факторы выступают в качестве воздействий, ограничивающих рост населения популяции, и наиболее эффективны в переходные осеннее-зимний и зимне-весенний периоды. ...