Материал: Алгебра_кортежей

формулируется так:

SELECT X, V FROM P, R WHERE Z = a AND P.Y = R.Y.

Ясно, что в АК схема отношения запроса соответствует схеме отношения АК-объекта, полученного в результате соединения P и R. Тогда запрос выражается как C-кортеж Q2[Z] = [{a}] или Q2[XYZVW] = [ {a} ], а ответ на запрос будет получен в атрибутах X и V после вычисления по формуле

(P[XYZ] R[YVW]) G Q2[Z] = (P[XYZ] G R[YVW]) [ {a} ].

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

(P[XYZ] [ {a}]) R[YVW] = (P[XYZ] [ {a}]) G R[YVW].

Здесь вначале элиминировались из Q2 фиктивные атрибуты V и W. Ту же схему вычислений можно использовать в запросе типа

SELECT X, V FROM P, R WHERE Z = a AND W = b AND P.Y = R.Y,

в котором дополнительно задано фиксированное значение для атрибута W. Тогда запросом будет C-кортеж Q2[ZW] = [{a} {b}], а ответ на запрос

получим в результате следующих вычислений

(P[XYZ] G Q2[Z]) (R[YVW] G Q2[W])

или (P[XYZ] G Q2[Z]) G (R[YVW] G Q2[W]).

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

Теперь опишем обработку запросов в структурах АК.

185

5.2.2. Анализ незапланированных запросов (реляционные СУБД)

К главным достоинствам реляционных СУБД, помимо поддержки ссылочной целостности данных и многопользовательского режима доступа на основе клиент-серверной технологии, относится также возможность реализовывать незапланированные запросы (ad hос запросы [Дейт, 1999]), т.е. запросы, формируемые во время исполнения клиентского приложения с учетом оперативных изменений схемы и содержимого базы данных. В реальных задачах часто возникает необходимость априорно (без привлечения данных из таблиц, кроме сведений о доменах атрибутов) проверять согласованность частей запроса или корректность незапланированных запросов с точки зрения ограничений моделируемой предметной области [Зуенко, 2008 c]. Такой анализ позволяет существенно снизить нагрузку на сервер БД, однако реляционные СУБД не обладают адекватными средствами для выполнения подобного рода проверок. Сами SQL-запросы (их селекторы) и большинство упомянутых ограничений представимы в виде логических формул над элементарными одно- и двуместными предикатами [Зуенко, 2008 a; 2010 a]. Такие формулы моделируются с помощью многоместных отношений, а значит, для их анализа могут быть применены методы АК.

До настоящего момента мы рассматривали самый простой случай, когда в качестве компонент АК-объектов выступают обычные множества (или интервалы), соответствующие одноместным предикатам. Чтобы значениями атрибутов АК-объектов могли быть многоместные отношения, моделирующие n-арные предикаты, требуется дополнить базовые определения и операции АК.

Далее описывается одна из возможных модификаций АК – алгебра условных кортежей (АУК), позволяющая использовать бинарные отношения при задании компонент и служащая для моделирования логических формул с элементарными двуместными предикатами [Зуенко, 2009; 2010 c].

Пусть A = {A1, A2, …, An} – простые атрибуты, чьими доменами являются обычные множества, а С = {A1, A2, …, An, A1×A2, A1×A3, …} – множество, состоящее из простых атрибутов и их всевозможных попарных декартовых произведений (сложных атрибутов).

Алгебра условных кортежей задается следующим образом:

Λ = < {RKi[Qi]}, , , +Atr, -Atr, Pr, ↔Atr, $ >, где: RKi[Qi] – некоторый

АУК-объект (условный С-кортеж или условная С-система); Qi – схема

186

отношения, представляющая собой некоторое множество простых и сложных атрибутов; $ – операция наполнения АУК-объектов, остальные операции (+Atr

– добавление атрибутов, -Atr – элиминация атрибутов, Pr – взятие проекции, ↔Atr – перестановка атрибутов) аналогичны операциям АК.

Условным С-кортежем называется заданный в определенной схеме отношения кортеж множеств (компонент), каждое из них представляет собой либо подмножество одного из доменов простых атрибутов, либо подмножество бинарного отношения, заданного на соответствующем сложном атрибуте. В качестве основных бинарных отношений (двуместных предикатов) выступают: «<» (меньше), «>» (больше), «=» (равно), «≠» (не равно). Компоненты простых атрибутов формируются из открытых интервалов вида (а, b) и дискретных значений. В описании компонент сложных атрибутов используются лишь имена бинарных отношений, а конкретные множества значений (элементарных кортежей) формируются в результате операции наполнения.

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

Условной С-системой называется множество однотипных условных С-кортежей, которые записываются в виде матрицы, ограниченной прямыми скобками.

Чтобы отличать АУК-объекты от структур АК, в их именах явно указывается множество сложных атрибутов. Например, RK[M] означает, что K – множество сложных атрибутов. АУК-объекты – это расширение С-систем и С-кортежей, в частности, С-система R[M] есть условная С-система RK[M], где

K = .

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

«<», «>», «=», «≠», представленных в табл. 5.5.

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

187

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

Введем на С-кортежах вида S[X,Y]=[A, B] следующие операторы: операторы взятия диагонали ( ), взятия элементов, лежащих над ( ) и под диагональю ( ). Оператор ([A, B]) возвращает ([A B, A B]) и соответствует отношению «равно», т.е. находит диагональ множества A B (подмножество диагонали универсума X×Y). Операторы и (сопоставляются отношениям «меньше» и «больше») определяют кортежи, которые принадлежат прямоугольнику A×B и лежат соответственно над и под диагональю универсума X×Y. Отношение «не равно» может быть выражено либо как дополнение отношения «равно», либо как объединение отношений «меньше» и «больше». Операторы возвращают пустое множество, если их область определения не содержит необходимых элементов.

Операция наполнения значениями произвольного АУК-объекта (конкретизации всех бинарных отношений внутри АУК-объекта) сводится к последовательности аналогичных операций для условных С-кортежей.

188

Результат операции наполнения АУК-объекта RK[M] обозначается как $RK[M].

Алгоритм 5.1. (наполнение условного С-кортежа значениями):

Не снижая общности, будем полагать, что задан условный C-кортеж RK[F], где компоненты сложных атрибутов принимают только одно из возможных значений: «=», «<», «>», «≠». Если в компонентах встречаются сразу несколько значений, такой C-кортеж всегда можно разложить в набор кортежей указанной структуры.

1.Разбиваем множество простых атрибутов, формирующих сложные атрибуты из K, на непересекающиеся подмножества Li следующим образом: простые атрибуты X и Y включаются в одно множество Li, если в моделируемой логической формуле соответствующие переменные x и y связаны предикатами «=», «<», «>», «≠» либо непосредственно, либо через другие переменные.

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

(см. п. 5.1).

3.Полученный после шагов 1 и 2 условный С-кортеж раскладываем в элементарные. Результат шага – некоторая условная С-система.

4.Элементы «=», «<», «>», «≠» в описании сложных компонент XY

выражаем через операторы ([A, B]), ([A, B]), и ([A, B]), где A X, В Y, а затем вычисляем эти операторы.

5. Конец алгоритма.

Поясним алгоритм на примере. Пусть имеется логическая формула: (x > 3) (x < 4) (y > 2) (y < 7) (z > 5) (z < 6) (y < x) (y > z),

где областью определения всех переменных служит множество вещественных чисел. Требуется установить ее выполнимость.

В АУК этой формуле соответствует условный С-кортеж

PXY,YZ[X,Y,Z,YX,YZ] = {(3,4)},{(2,7)},{(5,6)},{ },{ } ,

а решение задачи выполнимости заключается в наполнении заданного кортежа значениями.

На первом шаге алгоритма 5.1 можно сформировать только одно множество простых атрибутов – {X, Y, Z}, из которых образуются сложные атрибуты YX, YZ. Далее следуют шаги 2 и 3. Для кортежа PXY,YZ[X,Y,Z,YX,YZ] и множества атрибутов {X, Y, Z} множество квантов будет выглядеть так:

(2, 3), (3, 4), (4, 5), (5, 6), (6, 7).

189