Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Файлы

Лидовской К.В. Маликов А.В.

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

128 KB

Рисунок 1. Структура реляционных баз данных, нормализованных на основе операций выборки и соединения

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

Рисунок 2. Ориентированный граф связей некоторого подмножества атомарных значений реляционной базы данных

Перерисуем граф связей подмножества значений РБД, в виде ориентированной сети (рисунок 3).

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

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

Рисунок 3. Ориентированная сеть связей некоторого подмножества атомарных значений реляционной базы данных

Формально поисковый путь определяется следующим образом. Выбирается любая вершина v_x уровня 0 (вершина с полустепенью захода, равной 0), из которой достижимы вершины с исходным и требуемым значениями, т.е. определяется подграф, если такой имеется, содержащий вершины с исходным и требуемым значениями. Строится неориентированный граф по следующим правилам:

• в качестве множества вершин выбирается множество вершин ориентированной сети;
• всякая дуга ориентированной сети заменяется ребром неориентированного графа;
• определяется вершина v´_x неориентированного графа, соответствующая v_x.

Из вершины v´_x определяются две простые цепи к исходному и требуемому значениям. Поисковый путь определяется как совокупность найденных двух простых цепей за исключением совпадающих дуг. Согласно данному определению можно показать, что частным случаем является ситуация, когда поисковый путь совпадает с одним из путей сети. Замена ориентированной сети неориентированным графом обусловлена необходимостью выполнения обобщающих и уточняющих переходов между вершинами. Поиск информации на ориентированной сети может быть ускорен в случае внесения дополнений в алгоритм. Для этого необходимо сузить по возможности область поиска искомой информации запроса, при этом

1. Пространство поиска может быть сужено по ширине, путем определения подмножества вершин уровня 0 для исходного множества значений и последующего выделения соответствующего им подграфа значений. Если для исходного множества значений выделено несколько областей, то в качестве результата выбирается их более узкая общая часть.
2. Пространство поиска может быть сужено по высоте, путем определения подмножества уровней ориентированной сети, которым принадлежат требуемые значения. Для реализации данного пункта необходимо в структуре, представленной на рисунке 1, хранить дополнительную информацию, указывающую на то, какие атрибуты ролей принадлежат соответствующему уровню. Хранение дополнительной информации ускоряет процесс поиска информации, но снижает производительность операций добавления, удаления и изменения информации БД.

Представленный алгоритм используется при разработке компилятора языка манипулирования данными к РБД, нормализованных на основе операций выборки и соединения.

Литература

1. Маликов А.В. Проектирование реляционных баз данных на основе операций выборки и соединения. Исследование их свойств. Монография. Под ред. А.Г. Чефранова. Ставрополь: СевКавГТУ, 2002.

Библиографическая ссылка