Статья: Алгебраический подход к объектно-ориентированным базам данных

Пусть A - некоторое непустое множество. Частично определенная функция , называется n-арной частичной операцией на A. Если функция всюду определена, говорят просто об n-арной операции.

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

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

Пусть даны две однотипные универсальные алгебры и с основными множествами A и B.

Отображение : A B называется гомоморфным отображением алгебры в алгебру , если для любых элементов и произвольной n-арной операции F выполняется соотношение

, где и .

Алгебры и называются гомоморфными.

Пусть - n-местный предикат, - сигнатура предикатов. Система U_A=< A; ; > называется универсальной алгебраической системой.

Пример 6. Для трех задач из различных предметных областей: Разузлование (управление производством), Поиск кратчайшего пути в графе из заданной точки до остальных и Определение доступности заданного множества точек из фиксированной точки в графе (традиционные задачи исследования операций) может быть построен единый функциональный комплекс данных. В этом ФКД в роли носителя выступает множество ориентированных нагруженных графов G, подобных графу, приведенному на рисунке 2. Пусть T ¹ - подмножество G, состоящее из графов, подобных графу, приведенному на рисунке 3. Для преобразования произвольного графа в граф, принадлежащий T¹, задается операция . Можно потребовать выполнения аксиомы :

- всюду определенная функция.

Рис. 2. Граф не принадлежащий T ¹

Рассмотренный ФКД является структурой типа < G; ; >. Ему соответствует универсальная алгебра U_G=< G, { }>. Операция может быть реализована известным алгоритмом Дейкстры [13], приведенном на листинге 1. Этот алгоритм не зависит от типа весов графа. Однако в его реализациях используются операции над этими типами, определяемые свойствами объектов предметной области.

Рис. 3. Граф принадлежащий T ¹

При решении задачи Разузлование веса ребер - это неотрицательные действительные числа с обычными операциями сложение и умножение. В задаче Поиск кратчайшего пути в графе из заданной точки до остальных это также неотрицательные действительные числа с операциями минимум и сложение в качестве аддитивной и мультипликативной. И, наконец, в задаче Определение доступности заданного множества точек из фиксированной точки в графе - это логические величины 0 и 1 и операции дизъюнкция и конъюнкция.

Листинг 1. Алгоритм Дейкстры

S:={1};

for i:=2 to n do

D[i]:=C[1,i];

for i:=1 to n-1 do

begin

выбрать из множества V \ S вершину w и добавить ее к S; (*)

for каждой вершины v из множества V \ S do

D[v]:= D[v] D[w] C[w,v]; (**)

end;

Здесь V - множество вершин графа, S - множество пройденных вершин, C - двумерный массив весов, а D - одномерный массив, содержащий текущие "расстояния" от каждой вершины до источника. В первой задаче "расстояние" - это количество узлов или деталей в изделии, во - второй длина кратчайшего пути, а третьей - доступность вершины. Операции в строках (*) и (**) также зависят от решаемой задачи.

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

Система U_M =< M; >, состоящая из семейства основных множеств M={A} ( = 1, 2, …) и сигнатуры операций, определенных на семействе M так, что каждая n-арная операция из является отображением декартова произведения n множеств из семейства M в множество из того же семейства называется многоосновной алгеброй.

Система U_M=< M; ; >, где - сигнатура n-местных предикатов , называется многоосновной алгебраической системой.

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

Пример 7. Пусть M=< S, Z₀; ; > - система, состоящая из множества строк S и множества неотрицательных целых чисел Z₀. Сигнатура состоит из операций:

В сигнатуру предикатов можно включить предикаты р₁ - "Cтрока s - пустая" и р₂ - "Cтрока s₁ предшествует строке s₂". Таким образом, строковый тип в языках программирования есть ни что иное, как двухосновная универсальная алгебраическая система.

Очевидно, что системы числовых матриц, нагруженных графов также можно рассматривать как многоосновные алгебраические системы.

На многоосновных алгебраических системах базируется современное теоретическое и практическое программирования. Абстрактные типы данных (они же объекты или классы), сокращенно АТД, определяются как многоосновные алгебраические системы.

Среди множества произвольных абстрактных типов данных выделяется один специфический вид. Эти АТД представляют собой двухосновные алгебраические системы вида E=<S, T; ; >. Основу S назовем структурой, а T - типом.

Важная особенность этих АТД состоит в том, что суть операций над элементами структуры S, не изменяется при изменении сути операций над элементами типа T.

Так в примере 6 суть операции не изменялась, оставаясь все тем же алгоритмом Дейкстры при изменении строк (*) и (**).

Такие АТД будем называть абстрактными алгебраическими машинами (ААМ).

При таком определении ААМ основы сами должны быть универсальными алгебрами или алгебраическими системами. Причем в качестве основы T не используется конкретный тип данных. Задается только набор и характер его операций, а также их свойства, определяемые требованиями заданных на S операций.

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

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

- для Разузлования: неотрицательные действительные числа с обычными операциями сложение и умножение;

- для Поиска кратчайших путей между вершинами в графе: неотрицательные действительные числа с аддитивной операцией минимум и мультипликативной операцией сложение;

- для Определения связности вершин в графе: {0,1} с операциями дизъюнкция и конъюнкция.

Абстрактная матричная машина представлена на листинге 2. Для реализации операций над матрицами необходимы переменные, заданные типами процедур (функций), реализующих операции над элементами матриц в моделях. В операции сложения матриц используется только процедура сложения элементов EAdd, а в операции умножения матриц используются операции обнуления элементов ENull и EMult для вычисления элементов по формуле c_ik= c_ik a_ij b_jk. Переменные Ri, Rj и Rk (регистры индексов матриц) используются операциями над элементами для синхронизации вычислений в процессе выполнения операций над матрицами и их элементами. Процедура Init настраивает операции над элементами матриц. Процедуры MatAdd и MatMult реализуют операции сложения и умножения матриц.

Листинг 2. Абстрактная матричная машина

type

{Типы процедур обработки элементов матриц}

TNull = procedure of object ; {Обнуление}

TAdd = procedure of object ; {Сложение}

TMult = procedure of object ; {Умножение}

{АТД - абстрактная матричная машина}

TAbstractMatrixMachine = class(TObject)

Ri, Rj, Rk : word; {Регистры индексов}

{Указатели на процедуры, реализующие операции над элементами типа}

EAdd : TAdd;

EMult : TMult;

ENull : TNull;

{Инициализация операций над элементами типа}

procedure Init(_EAdd : TAdd; _EMult : TMult; _ENull : TNull);

{Операции над абстрактными матрицами}

procedure MatAdd; {Сложение}

procedure MatMult; {Умножение}

end;

procedure TAbstractMatrixMachine.Init(_EAdd : TAdd; _EMult : TMult; _ENull : TNull);

begin

ENull := _ENull;

EAdd := _EAdd;

EMult := _EMult;

end;

procedure TAbstractMatrixMachine.MatAdd;

var

i, j : word;

begin

for i := 1 to N do

for j := 1 to N do

begin

Ri := i; {Установка регистров индексов}

Rj := j;

EAdd;

end;

end;

procedure TAbstractMatrixMachine.MatMult;

var

i, j,k : word;

begin

for i :=1 to N do

for k :=1 to N do

begin

Ri := i; {Установка регистров индексов}

Rk := k;

ENull;

for j :=1 to N do

begin

Rj := j;

EMult;

end;

end;

end;

Булевская модель матричной машины для решения задачи Определение связности вершин в графе представлена на листинге 3. Она начинается с объявления булевской матрицы (*) как двумерного массива логических значений. АТД TBooleanMatrixMachine строится как наследник АТД TAbstractMatrixMachine. Для вычислений используются переменные RMA, RMB и RMC (матрицы-регистры). Процедуры Zero, Add и Mult реализуют операции над элементами. Процедура ConstructModel настраивает адреса операций над элементами.

Листинг 3. Булевская модель матричной машины

TBMat=array[1..N, 1..N] of boolean; {Тип булевской матрицы} (*)

TBooleanMatrixMachine = class(TAbstractMatrixMachine)

RMA, RMB, RMC : TBMat; {Регистры матриц}

procedure Zero;

procedure Add; {Сложение элементов}

procedure Mult; {Умножение элементов}

procedure ConstructModel; {Инициализация модели}

end;

procedure TBooleanMatrixMachine.Zero;

begin

RMC[Ri,Rk] := false; (**)

end;

procedure TBooleanMatrixMachine.Add;

begin

RMC[Ri,Rj] := RMA[Ri,Rj] or RMB[Ri,Rj]; (***)

end;

procedure TBooleanMatrixMachine.Mult;

begin

RMC[Ri,Rk] := RMC[Ri,Rk] or RMA[Ri,Rj] and RMB[Rj,Rk]; (****)

end;

procedure TBooleanMatrixMachine.ConstructModel;

begin

Init(Add,Mult,Zero); {Инициализация операций над элементами}

end;

При реализации моделей, для решения задач Разузлование и Поиска кратчайших путей между вершинами в графе, тип матриц-регистров будет следующим: TRMat=array[1..N, 1..N] of real;, представляя собой двумерный массив действительных переменных. Алгоритмы реализации операций над элементами будут следующими:

Построенные таким образом модели абстрактной матричной машины позволяют решать поставленные задачи.

Заключение

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

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