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

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

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

Заметим, что в литературе иногда термин «концептуальный» связывают с конкретной СУБД и под концептуальной схемой понимают представление данных хоть и самого высокого уровня, но для каждой конкретной СУБД. Соответственно и под концептуальной моделью данных понимают выразительные средства, имеющиеся в распоряжении конкретной системы, даже если эти средства не обладают достаточными возможностями для выражения семантики предметной области.

На наш взгляд, слово «концептуальный» по своей сути соответствует содержательному пониманию предметов и явлений действительности, и будет использоваться в данной работе для обозначения уровня представления структур данных и ограничений, свойственных реальному миру (вне зависимости от представлений в конкретных системах). Модели данных с такими свойствами называют еще семантическими или инфологическими [3].

Мы будем использовать концептуальную модель данных [4], построенную на основе положений теории информационных объектов [5]. Эта теория была развита в процессе разработки информационной системы для экономических задач, эффективно реализующей сложные структуры данных (СУБД ИНЕС [6]). Принципы этой разработки были в дальнейшем использованы и при создании системы НИКА [7] для персональных ЭВМ.

Выразительные средства теории информационных объектов весьма хорошо соответствуют (и по содержанию и по форме) особенностям экономических задач и их представлению в виде выражений экономико-математических моделей [8].

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

Информационная переменная задается своим наименованием и множеством возможных значений. Переменные разделяются на типы: скалярные – S, если для каждого информационного объекта им соответствует одно значение (типа «текст», «число» и т.п.), множественные – W, если свойство объекта может характеризоваться более, чем одним значением, векторные – V, если переменная именует собой группу связанных по смыслу других информационных переменных (компонентов векторной переменной).

Информационная функция определяется набором аргументов (или ключей, или независимых информационных переменных, обычно идентифицирующих некоторый информационный объект), набором зависимых информационных переменных и графиком функции, т.е. таблицей соответствия значений аргументов и зависимых переменных. Информационные функции могут быть поименованы и так же, как и информационные переменные, разделяются на типы. Они могут быть однозначными – F, если каждому значению аргументов соответствует не более одного значения зависимой переменной, и многозначными – G, если – более одного.

Над информационными функциями определяются специальные операции, выполняемые над графиками функций [5, 9].

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

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

Описание предметной области с помощью выразительных средств указанной концептуальной модели данных состоит из следующих разделов:

• 
  C – классы информационных объектов, свойства которых задаются информационными переменными;
  

• 
  F – взаимосвязи свойств информационных объектов, задаваемых информационными функциями;
  

• 
  L – лингвистический раздел, определяющий, в частности, отношение синонимии между именами информационных переменных;
  
• 
  T – характеристика решаемых задач, представляемых запросами на выборку данных из базы;
  
• 
  R – ограничения целостности и сохранности (безопасности) данных.
  

• 
  переменным и функциям сопоставляются вершины графа;
  
• 
  дуги графа для каждой информационной функции исходят из вершин, которые соответствуют аргументам, и заходят в вершину, представляющую функцию, и далее исходят из вершины, которая представляет функцию, и заходят в вершины, соответствующие зависимым переменным;
  
• 
  векторные переменные в графе представляются как функции, аргументами которых являются векторные переменные, а зависимыми переменными – компоненты векторных переменных.
  

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

Представление концептуальной схемы в виде графа позволяет использовать богатый арсенал методов и алгоритмов теории графов (см., например, [10]) для формализации и решения задач автоматизации проектирования баз данных [9, 11], интеграции систем баз данных [12, 13], создания языка общения высокого уровня с информационной системой и других задач.

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

Для представления запросов концептуального уровня следует ввести в рассмотрение специальные запросные информационные функции – Q. Аргументами такой функции будут переменные, которые задаются в условиях запроса, а зависимыми переменными – те переменные, значения которых надо найти в результате выполнения запроса. Запросные функции могут иметь дополнительные спецификации, определяющие непосредственно условия выполнения запроса и другие характеристики (приоритет запроса, частоту его выполнения и т.п.).

Реализация запроса связана с обращением к одной информационной функции или к нескольким функциям, образующим цепочку (последовательность) функций или в общем случае – некоторую структуру, которую будем называть покрытием запроса.

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

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

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

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

В работе [12] ставилась задача нахождения оптимального покрытия запроса как задача Штейнера [14] на графах, состоящая в определении наикратчайшего дерева, которое «стягивает» («покрывает») заданное подмножество вершин (соответствующее переменным запросной функции) из всего множества вершин, образующих концептуальную схему. Известные методы решения задачи Штейнера неэффективны при большом количестве вершин графа. Поэтому был предложен эвристический подход, обеспечивающий решение реальных задач. Он использует алгоритмы поиска кратчайших путей в графе (например, алгоритмы Форда, Дейкстры [10, 15]) и алгоритмы построения оптимального остова графа (например, алгоритм Прима [16]).

В данной работе рассматриваются дальнейшие этапы реализации запроса:

• 
  анализ покрытия с целью установления корректности (правильности) запроса,
  

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

Поясним некоторые переменные и сокращения:

Все имена в нижней строке заголовка таблицы являются именами скалярных информационных переменных. Значения этих переменных даются в нижней части таблицы (для переменной Ректор значения не заданы).

Анализируя таблицу, можно выделить три класса информационных объектов: Сотрудники (с идентифицирующей переменной Личн), Вузы (идентификатор – Вуз) и Предприятия (Предпр). Очевидно, последние два класса могут пересекаться, т.е. переменные Вуз и Предпр являются совместимыми. Также совместимыми являются переменные А_вуза и Город.

В результате анализа значений переменных и их связей можно определить следующие информационные функции (и описать типы значений переменных):

ИФ1: Пол = F (Личн) = S (TEXT);

ИФ2: А_вуза, Ректор = F (Вуз) = S (TEXT);

ИФ3: Город = F (Предпр) = S (TEXT);

ИФ4: Дата окончания = F (Личн, Вуз);

ИФ5: Должн = G (Личн, Предпр) = S (TEXT);

ИФ6: Дата окончания = V (Год, Число, Мес);

Функции ИФ1 – ИФ4 – однозначные, функция ИФ5 – многозначная, ИФ6 представляет фактически описание векторной информационной переменной. В нижней строке описаны идентифицирующие переменные.

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

В
данном примере граф состоит из одной компоненты связности. Однако, если бы в описании отсутствовала функция ИФ3 и не было переменной А_вуза, но была функция Численность населения = F (Город), то тогда концептуальная схема состояла бы из двух компонент связности.

Рассмотрим запрос: найти должности, которые занимают в некотором известном городе сотрудники (личности), окончившие некоторый известный вуз. Этот запрос можно представить следующим образом в виде запросной функции:
Личн, Должн = Q (Город, Вуз).
Ч
тобы выполнить запрос, надо вначале найти его покрытие (например, с помощью метода, описанного в [12]). На рис. 2 дано покрытие этого запроса, представляющее некоторый фрагмент графа, показанного на рис. 1. В покрытии неиспользуемые переменные функций изображены пунктиром.

Дальнейшие шаги выполнения запроса связаны с анализом полученного покрытия.

Некоторые возможные варианты изображены на рис. 3. На нем через обозначены аргументы запросов, через – искомые переменные, через – некоторая произвольная переменная; стрелки условно изображают путь, существующий в покрытии между переменными; вертикальная пунктирная прямая условно разделяет разные компоненты связности.

Рассмотрим варианты, изображенные на рис. 3.

Некорректный запрос.

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

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

Исходные запросы могут находиться в разных компонентах связности или в одной. Первый случай показан на рис. 3, г). Во втором случае возможны два варианта:

1) объединены запросы с разными аргументами и разными искомыми переменными, причем между аргументами разных запросов имеется функциональная связь – рис. 3, д);

2) объединены запросы с разными аргументами и одной и той же искомой переменной, что обнаруживается наличием в покрытии переменной (может быть, искомой), в которой сходятся пути от разных аргументов –рис. 3, е).

Приведем простые примеры запросов, иллюстрирующих некоторые рассмотренные случаи.

В запросе Пол = Q (Личн, Вуз) аргумент Вуз является лишним. Если в концептуальной схеме имеется функция, связывающая Вуз и Личн (например, Дата окончания = F (Личн, Вуз) или Вуз = F (Личн)), то этот запрос соответствует рис. 3, в). Если такой функции нет, то запрос иллюстрирует рис. 3, б).

Запрос Пол, А_вуза = Q (Личн, Вуз) является объединением двух логически правильных запросов Пол = Q (Личн) и А_вуза = Q (Вуз).

Если в концептуальной схеме есть функция, связывающая Вуз и Личн, то запрос Пол, А_вуза = Q (Личн, Вуз) соответствует рис. 3, д), если нет – рис. 3, г).

Запрос Ректор = Q (Личн, А_вуза) соответствует рис. 3, е). В этом случае роль переменной играет переменная Вуз, роль и – соответственно переменные Личн и А_вуза, при этом функция ИФ4 соответствует и проходится от аргумента Личн к аргументу Вуз, а функция ИФ2 соответствует и проходится в обратном направлении – от зависимой переменной А_вуза к аргументу Вуз.

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

Во всех вариантах, кроме случая на рис. 3, а), может быть обеспечено исправление и выполнение запроса.
4. Распараллеливание процесса выполнения запроса
Для решения поставленной задачи удобно использовать методы анализа сетей Петри (см., например, [17]).

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

Для анализа выполнимости сети Петри и определения последовательности прохождения (запуска) переходов используется метод маркировки сети, который состоит в присвоении позициям фишек.

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

Так как выходные позиции одного перехода являются входными для некоторого другого (или некоторых других переходов), то при этом может выполняться условие запуска другого перехода (или других переходов) и т.д. Если условие запуска выполняется одновременно для нескольких переходов, то они могут запускаться параллельно.

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

Далее процедура повторяется, пока мы не дойдем до искомых переменных и определим их значения.

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

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

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

Будем различать шесть разновидностей операции над функцией. Рассмотрим их на примере функции с двумя аргументами и и двумя зависимыми переменными и . Схематическое изображение такой функции как перехода сети Петри дано на рис. 4, а). На рис. 4, б) – ж) представлены соответственно 1-я – 6-я разновидности прохождения функции; стрелки направлены от входных переменных к переходу и от перехода к выходным переменным. К входным переменным во всех случаях надо относить все аргументы, если даже они не включены в состав переменных запросной функции (стрелки от таких аргументов показаны пунктиром).

Как видно из рисунков, 1-я разновидность соответствует прохождению функции в прямом направлении – от аргументов к зависимой переменной; 2-я – в обратном направлении; 3-я – от аргумента к аргументу; 4-я – от одной зависимой переменной к другой; 5-я и 6-я – от аргумента и зависимой переменной к другому аргументу (5-я разновидность) или к другой зависимой переменной (6-я).

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

Н
а рис. 5 представлена последовательно-параллельная схема прохождения информационных функций, полученная в результате анализа покрытия рассматриваемого выше запроса (см. рис. 4). Информационные переменные (позиции) изображены на рис. 5 жирной точкой, а функции (переходы) – вертикальной чертой. Нетрудно видеть, что операции над функциями ИФ4 и ИФ3 могут выполняться параллельно, при этом над функцией ИФ4 будет выполняться разновидность операции «от аргумента к аргументу», показанная на рис. 4, г), а над функцией ИФ3 – «от зависимой переменной к аргументу», т.е. функция ИФ3 будет проходиться в обратном направлении, чему соответствует рис. 4, в).
6. Заключение
Мы рассмотрели подход к построению языка запросов высокого уровня, позволяющий организовать интеллектуальный интерфейс между человеком и системой баз данных. Использование языка не связано с заданием навигационных путей к искомым данным. Были рассмотрены также ряд процедур анализа покрытия запроса, обеспечивающие распараллеливание его выполнения и возможность оптимизации процесса трансляции запроса на язык манипулирования данными конкретной СУБД.

ЛИТЕРАТУРА

1. 
   Дейт К. Дж. Введение в системы баз данных. – Киев - Москва: Диалектика, 1998.
   
2. 
   Date C. J., Darwen H. A Guide to the SQL Standard. – Reading, Mass.: Addison-Wesley, 1993.
   
3. 
   Цикритзис Д., Лоховски Ф. Модели данных. – М.: Финансы и статистика, 1985.
   
4. 
   Кочин Ю. Я. Построение концептуальной модели данных и ее использование // Вопросы информационной технологии: Сб. ВНИИСИ. М., 1982. Вып. 1. С. 67 – 72.
   
5. 
   Иванов Ю. Н. Теория информационных объектов: системы управления базами данных. – М.: Наука, 1988.
   
6. 
   Емельянов Н. Е. Введение в СУБД ИНЕС. – М.: Наука, 1988.
   
7. 
   Годунов А. Н., Емельянов Н. Е. И др. Система НИКА // Системы управления базами данных и знаний. М.: Финансы и статистика, 1991. С. 209 – 248.
   
8. 
   Ковальчук Г. Б., Кочин Ю. Я. Методика проектирования баз данных для экономических задач // Теория и практика создания комплексных автоматизированных систем управления: Сб. научн. тр. М.: МЭСИ, 1983. С. 61 – 69.
   
9. 
   Иванов Ю. Н., Кочин Ю. Я., Прошкин С. Д. Языковые и алгоритмические аспекты концептуального описания базы данных: Препринт / ВНИИСИ. – М., 1983. 70с.
   
10. 
    Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
    
11. 
    Kochin Yu. Ya. Object Environment and Database Design // Proc. of the Eleventh Intern. Seminar on Data Base Management Systems, General Statistical Office SZAMALK, Seregelyes (Hungary), 1988, pp. 107 – 116.
    
12. 
    Иванов Ю. Н., Кочин Ю. Я. Представление и реализация запросов в системах баз данных // Автоматика и телемеханика, 1996. С. 178 – 186.
    
13. 
    Kochin Yu. Ya., Lee Jun S. An Approach to Database Integration Problems // Proc. of the IASTED / ISMM Intern. Conf. on Modelling and Simulation, Pittsburg, USA. April 1996, pp. 181 – 183.
    
14. 
    Hakimi S. L. Steiner's Problem in Graphs and its Implications // Networks. 1971. 1, p.113.
    
15. 
    Dijkstra E. W. A Note on Two Problems in Connection with Graphs // Numerische Mathematik. 1959. 1, p.269.
    
16. 
    Prim R. S. Shortest Connection Networks and Some Generalizations // Bell Syst. Tech. J. 1957. 36, p.1389.
    
17. 
    Котов В. Е. Сети Петри. – М.: Наука, 1984.