2. Взгляд на реляционную алгебру

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

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

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

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

Заметим, что хотя в реляционной модели данных имя схемы отношения совпадает с именем экземпляра отношения (это очень похоже на то, как в ООБД имя класса часто пытаются использовать одновременно как имя типа объекта и имя множества объектов), неявно возникает понятие типа отношения, которое не обязательно именовать по причине простоты определения эквивалентных (однотипных) схем отношений.

3. Основные определения и формулировка алгебры классов

Не будем приводить полный набор концепций и определений. В основном мы следуем принятым представлениям об ООБД со множественным наследованием. Затронем только те понятия, которые существенны для дальнейшего изложения.

Будем опираться на следующее: ООБД представляется как ациклический граф с корнем (АГК), все вершины которого представляют собой классы объектов, а дуги соответствуют отношению наследования (будем называть этот АГК статическим АГК ООБД). Каждый объект ООБД обладает типом и непосредственно принадлежит некоторому классу, принадлежа при этом каждому суперклассу этого класса. Все объекты одного класса обладают общим типом и поэтому можно говорить о типе класса. Тип суперкласса является супертипом типа класса (в частности, тем же самым типом). Непосредственным типом объекта называется тип класса, которому непосредственно принадлежит этот объект. Допускается также наличие в статической решетке классов ООБД нескольких классов, не связанных отношением класс-суперкласс, с одним типом. Тип объекта (класса) в нашей трактовке является не только синтаксической, но и семантической характеристикой. В частности, если два класса объектов обладают одним и тем же типом, то осмысленны теоретико-множественные операции объединения и пересечения для этих классов.

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

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

Разделение понятий класса и типа приводит к тому, что для ООБД одновременно поддерживаются вообще говоря разные АГК классов и АГК типов. Разная структура этих графов обуславливается, во-первых, тем, что допускается существование однотипных классов, не связанных отношением наследования, и во-вторых, тем, что подкласс класса не обязательно обладает другим типом.

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

Объединение классов.

Операция объединения классов является двуместной и естественным условием ее применения является однотипность обоих классов.

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

Пересечение классов.

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

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

Декартово произведение классов.

Операция декартова произведения классов является двуместной и применима к любым двум классам решетки классов (статической или динамической).

Сигнатура типа результирующего класса производится путем объединения сигнатур типов классов-операндов. Возможные коллизии имен функций разрешаются подобно тому, как это делается в реляционной алгебре для имен атрибутов. Результирующий класс C, полученный путем декартова произведения класса A на класс B, включает множество объектов, полученных путем попарного "склеивания" объектов классов A и B. Объекты класса C являются вновь созданными временными объектами ООБД и обладают новыми идентификаторами. Тип класса C является подтипом типов классов A и B, но класс C не является подклассом ни A, ни B. В динамической решетке классов его можно считать подклассом только корневого суперкласса статической решетки.

Заметим, что даже если в статической решетке классов у классов A и B имеется общий подкласс с тем же типом, что и у C, нельзя считать, что это и есть класс C, потому что объекты этого класса могли порождаться совсем другим образом.

Селекция класса.

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

Результирующий класс C обладает тем же типом, что и класс A, является его подклассом в динамической решетке классов и непосредственно включает все объекты класса A, для которых значение логического выражения F есть true.

Проекция класса.

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

Тип результирующего класса C является супертипом типа класса A с сигнатурой, полученной путем удаления из сигнатуры типа класса A функций, указанных в S. Объекты класса C являются вновь создаваемыми объектами ООБД и обладают новыми идентификаторами. Хотя тип класса C является супертипом типа класса A, класс С не является суперклассом класса A. В динамической решетке классов его можно считать только подклассом корневого класса динамической решетки классов.

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

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

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

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