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

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

Емельченков Е. П., Мунерман В. И.

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

Methods of mathematical modeling of processes for designing the information systems are considered. Designs of functional data complexes and abstract algebraic machines which provide language unity and optimization at all development cycles are offered.

Введение

В [1] утверждается, что разработка любой системы обработки информации представляет собой последовательность действий, каждому из которых соответствует описание на некотором языке. Несогласованность этих описаний, приводит к огромным непроизводительным затратам и существенно тормозит развитие технологии разработки программного обеспечения информационных систем (ИС). Каждое такое описание требует задания абстракций для объектов предметных областей, их специфических свойств (атрибутов) и отношений между ними. При этом, после определения новых абстракций, необходимо найти их место в контексте уже существующих классов и объектов. Не стоит пытаться делать это строго сверху вниз или снизу вверх. В [2] утверждается, что "нет особой необходимости строить иерархию классов, начиная с самого верхнего класса, и потом дополнять ее подклассами. Чаще вы создаете несколько независимых иерархий, осознаете их общие черты и выделяете один или несколько суперклассов. Требуется несколько проходов вверх и вниз по иерархии, чтобы создать программный проект". Это наблюдение, основанное на опыте и подтверждающее тот факт, что проектирование - это процесс последовательных приближений, и именно в нем проявляется искусство проектировщика и программиста. Сходное наблюдение встречается в [3]: "Наиболее частые реорганизации в иерархии классов - это сведение совпадающих частей двух классов в один и разделение класса на два новых". Интересно, что впервые подобный подход к проблеме проектирования ИС был сделан на заре вычислительной техники и программирования [4].

В [5, 6] была предложена методика проектирования так называемых функциональных моделей данных. Несущественное изменение этой методики позволяет проектировать модели данных со сложной структурой, в том числе и объектно-ориентированные модели. В [1, 7] были рассмотрены особые виды объектов, задаваемых в языках программирования и обеспечивающих естественную связь упомянутых моделей данных со сложной структурой и современных технологий программирования. Дальнейшее изложение посвящено объединению этих двух подходов и их совместному развитию в общую теорию и технологию проектирования информационных систем.

Предлагаемые в статье решения позволят ответить на актуальные вопросы, сформулированные в [8], поскольку:

- предоставляет отчетливую спецификацию объектно-ориентированных баз данных;

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

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

1. Функциональные комплексы данных

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

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

Примером функции Id на некотором предприятии может служить код изделия (узла, детали).

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

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

Примерами атрибутов объектов являются такие характеристики как: Цвет, Вес, Дата изготовления, Возраст, Пол, Фамилия, Внешний вид, Голос.

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

Пример 1. Описание атрибута Цвет:

Dom(Цвет) = {красный, оранжевый, желтый, зеленый, голубой, синий, фиолетовый}.

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

(Цвет, желтый), первой компонентой которого служит имя атрибута, а второй - его значение, или в виде таблицы

Пример 2. Описание атрибута Вес: Dom(Вес) = Real.

Ограничения: Вес 0.

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

Пример 3. Описание атрибута Внешний вид:

Операции над значениями атрибута:

Контрастность(имя файла, t),

Яркость(имя файла, t),

Размер(имя файла, t),

где параметр, позволяющий увеличить (+) или уменьшить () соответственно контрастность, яркость или размер фотографии с именем имя файла.

Значениями атрибута Внешний вид являются файлы с расширением jpg, в которых хранятся фотографии объектов из предметной области.

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

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

Пример 4. Описание атрибута Голос:

Операции над значениями атрибута:

Громче(имя файла),

Тише(имя файла),

позволяющие регулировать громкость звучания файла с именем имя файла.

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

Таким образом, определяемый в примере тип Голос представляет собой алгебраическую систему с двумя унарными операциями

V = <Голос; Громче, Тише>.

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

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

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

Пример 5. Описание трехместной функции данных Жильцы:

Жильцы: Улица, Дом, Квартира Список жильцов.

В этом описании предполагается, что типы данных Улица, Дом, Квартира, Список жильцов определены как char(25), byte, byte и set of char(20) (символьный, числовые и множественный) соответственно. В отличие от остальных атрибутов значением атрибута Список жильцов является сложный тип данных - множество.

Конкретные значения функции Жильцы в информационной системе могут храниться как запись (кортеж)

((Улица, Варяжская), (Дом, 62), (Квартира, 15),

(Список жильцов, {Иванов И.И., Иванов В.И., Сидорова Т.А.}))

или в виде таблицы:

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

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

Получаемые в результате такого проектирования конструкции называются функциональными комплексами данных или сокращенно ФКД.

В ФКД конструкторы типов применимы к любым типам данных. Это соответствует требованию ортогональности, выдвинутому в [9], что позволяет строить таблицы подобные приведенной на рисунке 1, где в роли элементов кортежей (полей таблицы) могут выступать кортежи и таблицы.

В реляционной же модели конструкторы не ортогональны, потому что конструкция множества может быть применена только к кортежам, а конструкция кортежа - только к атомарным значениям. Частичным решением проблемы ортогональности может быть использование реляционных моделей в не первой нормальной форме (non-first normal form или NFNF), в которых конструкцией верхнего уровня всегда должно быть отношение [10].

Рис. 1. Модель данных в не первой нормальной форме

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

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

< D; R; A >, где

D - заданное множество (носитель структуры);

R - конечный набор отношений, в которых находятся элементы множества (типовая характеристика структуры);

A - ограничительные условия, накладываемые на отношения (аксиомы структуры).

Таким образом, ФКД - это аксиоматическая теория [11]. Следовательно, на основе ФКД может быть построен формальный язык манипулирования данными для первичного описания предметной области [12], и ФКД служит основой для дальнейшей формализации в рамках современных технологий программирования, о чем пойдет речь в следующем разделе.

2. Абстрактные алгебраические машины

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