АБСТРАКЦИИ БАЗ ДАННЫХ: Агрегация и обобщение

Определяются два вида абстракций, имеющих фундаментально важное значение в проектировании и использовании баз данных. Агрегация - это такая абстракция, которая превращает связь между объектами в некоторый агрегированный объект. Обобщение - это абстракция, превращающая класс объектов в родовой объект. Предполагается, что для всех объектов (индивидуальных, агрегатных, родовых) должна даваться унифицированная интерпретация в моделях реального мира. В качестве примитивов для определения таких моделей разработаны новые типы данных, названные родовыми. Определенные с помощью таких примитивов модели структурируются как множество иерархий агрегации, пересекающееся с множеством иерархий обобщения. В точках пересечения появляются абстрактные объекты. Такая структура высокого уровня обеспечивает некоторую дисциплину для организации реляционных баз данных. Она, в частности, дает возможность: а) интегрировать и поддерживать важный класс представлений (view); б) обеспечивать при определенных эволюционных изменениях стабильность данных и программ; в) значительно легче понимать сложные модели и более естественным образом формулировать запросы; г) использовать более семантичный подход к проектированию баз данных; д) осуществлять дополнительную оптимизацию на более низких уровнях реализации. Родовой тип формализуется благодаря некоторому множеству инвариантных свойств. Эти свойства должны удовлетворяться всеми отношениями в базе данных, если абстракции должны сохраняться. Предлагается запускающий механизм для автоматической поддержки таких инвариантов во время операций обновления. Дается простое отображение иерархий агрегации/обобщения на структуры наборов КОДАСИЛ.

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

1. ВВЕДЕНИЕ

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

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

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

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

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

Если придерживаться соответствующей дисциплины структурирования, реляционная схема Кодда может одновременно поддерживать как иерархии абстракций агрегации, так и иерархии абстракций обобщения. В предыдущей статье [4] мы предложили дисциплину структурирования, подходящую для абстракций агрегации. В данной работе предлагается дисциплина структурирования для абстракций обобщения и осуществляется ее интеграция с дисциплиной, ранее предложенной для абстракций агрегации.

Польза от такой дисциплины структурирования заключается в следующем:

В работе [4] мы сопоставляем примитивы для выражения абстракций агрегации, которые обеспечиваются языками программирования, с примитивами, необходимыми в базах данных. Мы показываем, каким образом адаптировать структуру Декартова произведения¹⁾ Хоара [2], чтобы ее можно было использовать для определения реляционных моделей. Такая адаптация приводит к некоторому пониманию роли абстракций агрегации в базе данных. Данная работа может рассматриваться также как попытка адаптации к реляционным моделям структуры размеченного объединения (discriminated union)²⁾ Хоара [2]. Эта адаптация, в свою очередь, приводит к пониманию роли абстракций обобщения в базах данных.

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

В разделе 2 развивается философия представления абстракций обобщения в реляционной схеме Кодда. Эта философия приводит к мощной родовой структуре для определения реляционных моделей. Такая структура описывается в разделе 3. Далее в разделе 4 исследуется, каким образом родовая структура может использоваться для рассмотрения различных ситуаций при моделировании. В разделе 5 обсуждаются пять свойств реляционной модели, которые должны оставаться инвариантными во время операций обновления. Эти инвариантные свойства представляют собой (частично) аксиоматическое определение данной родовой структуры. На основе семантических рассмотрений разработано множество правил для поддержки этих инвариантов. В разделе 6 приводятся заключительные замечания, касающиеся некоторых аспектов родовой структуры, в том числе методов проектирования баз данных, техники реализации и языка доступа.

2. АБСТРАКЦИИ ОБОБЩЕНИЯ

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

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

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

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

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

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

Родовой объект, подобно индивидуальному, может участвовать в связях с другими объектами. Мы можем, например, рассмотреть связь между "Профессиями" и "Обществами", которые объединяют их представителей. Конкретные профессии включают "Водителя грузовика", "Научного работника в области информатики" и "Доктора", и все они являются родовыми объектами. Эта связь, которая называется "Членство", представлена в Таблице 1. Обратим внимание на то обстоятельство, что "Профессия" - это обобщение класса, который включает "Водителя грузовика", "Научного работника в области информатики" и "Доктора".

Таблица I.

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

На Рис. 1 показан конкретный вариант декомпозиции "Транспортного средства" на родовые объекты более низкого уровня. Заметим, что отдельные транспортные средства при этом явно не представляются. Каждый родовой объект должен мыслиться как определение некоторого класса индивидуальных транспортных средств. На рисунке видно, например, что "Грузовик", "Велосипед" и "Повозка" могут быть обобщены понятием "Дорожный транспорт", "Дорожный транспорт" и "Рельсовый транспорт" - понятием "Наземный транспорт", и, наконец, что "Наземный транспорт", "Воздушный транспорт" и "Водный транспорт" могут быть обобщены понятием "Транспорт".

Пусть G - некоторый объект в родовой иерархии. Чтобы представить G как отношение Кодда, мы должны выбрать множество атрибутов, которые являются общими для всех индивидуумов в классе G. Например, в представление "Транспорта" мы можем включить атрибуты "Идентификационный номер", "Изготовитель", "Цена" и "Вес". Эти атрибуты являются общими для всех транспортных средств. В представление "Дорожного транспорта" мы можем включить все предыдущие атрибуты, а также и другие, такие как "Количество колес" и "Давление в шинах". Эти атрибуты являются общими для всех дорожных транспортных средств. Однако последние два атрибута не являются общими для всех транспортных средств. В представление "Грузовика" мы можем включить все предыдущие атрибуты и некоторые другие, например "Мощность двигателя в лошадиных силах" и "Размер кабины". Эти атрибуты являются общими для всех грузовиков, однако два последних атрибута не являются общими для всех дорожных транспортных средств.

Теперь конкретный грузовик будет являться элементом каждого из классов "Транспорт", "Дорожный транспорт" и "Грузовик". Однако множества атрибутов, релевантных этому грузовику, будут различаться от класса к классу. Когда этот грузовик рассматривается как конкретное транспортное средство, любые атрибуты, отличающие грузовики от других транспортных средств, будут нерелевантными. Если же данный грузовик рассматривается как конкретное средство дорожного транспорта, будут релевантны все атрибуты, которые отличают грузовики от других средств дорожного транспорта. В общем случае, индивидуальный объект будет иметь дополнительно релевантные атрибуты более низкого родового уровня того класса, к которому он относится. Назовем G-атрибутами конкретного объекта атрибуты этого объекта, которые релевантны классу G.

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

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

Наш метод представления родовой иерархии требует, чтобы непосредственные потомки любого узла были разбиты на группы. Каждая группа должна содержать родовые объекты, классы которых являются взаимно-исключающими. На практике такое группирование обычно может быть весьма легко сделано из семантических соображений. Например, потомки на Рис. 3 могли бы быть сгруппированы следующим образом: {Транспортные средства, приводимые в движение ветром; Моторизованные транспортные средства; Транспортные средства, приводимые в движение человеком} и {Воздушный транспорт; Водный транспорт; Наземный транспорт}. Первая группа содержит взаимно-исключающие классы, которые соответствуют альтернативным типам "Системы приведения в движение". Вторая группа, в свою очередь, содержит взаимно-исключающие классы, которые соответствуют различным типам "Среды передвижения"³⁾.

Назовем взаимно-исключающие группы родовых объектов, имеющие общие родительские объекты, кластерами. Будем говорить, что кластер относится к его родительскому родовому объекту. Например, мы можем говорить о двух кластерах, относящихся к объекту "Транспорт" на Рис. 3. Узлы-листья в родовой иерархии не имеют относящихся к ним кластеров. На Рис. 1 каждый родовой объект, не являющийся листом, имеет в точности один относящийся к нему кластер. На Рис. 2 кластер, относящийся к "Моторизованным транспортным средствам", и кластер, относящийся к "Воздушному транспорту", имеют общий элемент - вертолет.

Мы считаем необходимым дать каждому кластеру некоторое (осмысленное) имя. Это имя должно быть выбрано таким образом, чтобы оно было описательным для родовых объектов в данном кластере. Например, в качестве имени кластера {Транспортные средства, приводимые в движение ветром; Моторизованные транспортные средства; Транспортные средства, приводимые в движение человеком} можно было бы использовать "Категорию двигателя". Для кластера {Воздушный транспорт; Водный транспорт; наземный транспорт} может быть выбрано имя "Категория среды передвижения".

Опишем теперь метод представления родовой иерархии как иерархии отношений Кодда. Для каждого родового объекта в иерархии будет создаваться одно отношение. Пусть G - родовой объект такой, что 1) I есть класс конкретных объектов, ассоциированных с G; 2) A₁, ..., A_n - G-атрибуты и 3) C₁, ..., C_m - имена кластеров, относящихся к G. Тогда G представляется следующим отношением Кодда:

где:

а) имеется один и только один кортеж для каждого индивидуума, принадлежащего I;

б) если индивидуум имеет значение v_i для атрибута A_i, то его кортеж содержит v_i в домене A_i;

в) если индивидуум включается также в родовой объект v_n+j в кластере C_j, то его кортеж содержит v_n+j в домене C_j;

г) если индивидуум не включается ни в какой родовой объект в кластере C_j, то его кортеж содержит "пусто" (-) в домене C_j.

В Таблице II показано, как могут выглядеть отношения Кодда (в некоторый момент времени) для родовых объектов "Транспорт", "Моторизованный транспорт" и "Воздушный транспорт", представленных на Рис. 4. Заметим, что одним из следствий такого метода представления является появление имен отношений как значений в некоторых доменах. Например, домены "Категория среды передвижения" и "Категория двигателя" в отношении "Транспорт" имеют имена отношений в качестве значений. Это позволяет нам использовать операторы в манипулировании родовыми объектами. Как будет показано в разделе 4, это позволяет нам также использовать унифицированный метод для представления связей, в которых принимают участие родовые или индивидуальные объекты.

Будем называть домен в отношении, который содержит имя некоторого подчиненного отношения, доменом образа (image domain) этого потомка. Так, например, домен "Категория среды передвижения" в отношении "Транспорт" является доменом образа для подчиненных отношений "Наземный транспорт", "Воздушный транспорт" и "Водный транспорт". Существует взаимно-однозначное соответствие между кластерами в родовой иерархии и доменами образов в их реляционном представлении.

Заметим, что в Таблице II все домены, за исключением доменов образов в "Транспорт", наследуются подчиненными ему отношениями "Моторизованный транспорт" и "Воздушный транспорт". Хотя это наследование доменов часто может быть присущим реляционной модели, мы не настаиваем на том, что оно обязательно должно иметь место. Это позволяет представлять абстракции обобщения способом, наиболее подходящим для их пользователей.

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

а) на дублирование данных не затрачивалось дополнительное пространство памяти;

б) могла поддерживаться непротиворечивость избыточной информации. Этот вопрос обсуждается далее в разделе 6.

3. РОДОВАЯ СТРУКТУРА

Опишем теперь примитивы структурирования для спецификации обобщений в реляционных моделях. В работе [4] мы ввели типы collection (коллекция) и aggregate (агрегат), после чего объявили отношение R следующим образом:

var R: collection of aggregate [список ключей]
s1: {key} R1;
...
sn: {key} Rn
end

В этом объявлении "список ключей" содержит селекторы для ключевых доменов R. Заключение зарезервированного слова "key" (ключ) в фигурные скобки показывает, что оно не всегда должно появляться. Теперь R может фактически рассматриваться как имя родового объекта. Для того чтобы определить позицию родового объекта R в родовой иерархии, нам необходимо лишь специфицировать его потомков в этой иерархии. Это дает возможность полагать, что структура, показанная на Рис. 5, является достаточной для определения отношений Кодда.

var R: generic

sk1 = (R11, ..., R1p1);

...

skm = (Rm1, ..., Rmpm)

of

aggregate [список ключей]

s1: {key} R1;

...

sn: {key} Rn

end

Рисунок 5.
Родовая структура.

Мы используем термин "родовой" (generic), а не более близкий термин "коллекция" (collection) с тем, чтобы указать, что определяются родовые объекты. Родовая структура одновременно специфицирует две абстракции: а) она специфицирует R как агрегацию связи между объектами от R₁ до R_n и б) она специфицирует R как обобщение класса, содержащего объекты от R₁₁ до R_mpm. Домены с селекторами от s_k1 до s_km являются доменами образов. Если никакие домены образов не специфицированы, то родовая структура является в точности такой же, как структура коллекции из [4].

Прежде чем перейти к обсуждению пяти синтаксических требований к родовой структуре, определим три отношения на основе Таблицы II. Эти определения показаны на Рис. 6. Заметим, что в определении отношения "Транспорт", родовые его потомки перечислены после зарезервированного слова "generic", а агрегированные потомки - после зарезервированного слова "aggregate". Родовые потомки группируются в кластеры, и каждый кластер ассоциируется с селектором соответствующего ему домена образов. В данном случае домены образов имеют селекторы MC и PC.

var Транспорт:

generic

of

aggregate [ID#]

end

var Моторизованный транспорт:

generic

of
aggregate [ID#]

end

var Воздушный транспорт:

generic

LC = (Самолет, Вертолет)

of

aggregate [ID#]

Рисунок 6.
Определение отношений из Таблицы II.

Мы не будем обсуждать два первых синтаксических требования в связи с Рис. 5, поскольку они поясняются в [4]. Требование в) сводится к тому, чтобы каждый родовой потомок R объявлялся где-либо как полноправный родовой объект. На Рис. 6 это иллюстрируется объявлениями "Моторизованного транспорта" и "Воздушного транспорта". Более того, все эти объекты-потомки должны иметь тот же самый ключевой домен, что и R. Это требование позволяет ссылаться на объекты-индивидуумы унифицированным образом независимо от того, в какой родовой класс они входят. Иногда полезным исключением из этого правила является то обстоятельство, что если s_ki входит в ключ R, то оно не обязательно должно появляться в ключе какого-либо R_ij (1 <= j <= p_i). Если бы оно все-таки появлялось, этот домен имел бы одно и то же значение для каждого индивидуума в R_ij.

Предположим, например, что PC было объявлено как относящееся к ключу объекта "Транспорт" на Рис. 6. Если мы далее добавим "Категорию двигателя" как новый домен в отношение "Моторизованный транспорт" для того, чтобы удовлетворить требование в), этот домен будет иметь одно и то же значение ("Моторизованный транспорт") для каждого индивидуума.

Благодаря требованию г) обеспечивается, чтобы каждый специфицированный кластер ассоциировался с конкретным доменом (образов). Требование д), в свою очередь, обеспечивает, чтобы каждый домен образов мог фактически принимать в качестве значений родовые идентификаторы, перечисленные в ассоциированном с ним кластере. Например, в определении объекта "Транспорт" на Рис. 6 тип "Категория среды" должен определяться в другом месте на множестве идентификаторов, включающем "Наземный транспорт", "Воздушный транспорт" и "Водный транспорт".

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

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

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

1) Каждый R-индивидуум должен определять некоторый уникальный Ri-индивидуум.

2) Никакие два R-индивидуума не определяют одно и то же множество R_i-индивидуумов для всех R_i, чьи селекторы принадлежат "списку ключей".

3) Каждый R_ij-индивидуум должен также быть R-индивидуумом.

4) Каждый R-индивидуум, классифицируемый как R_ij, должен также быть R_ij-индивидуумом.

5) Никакой R_ij-индивидуум не является также R_ik-индивидуумом при j<>k.

Здесь под R-индивидуумом (R_i-или R_ij-индивидуумом) мы понимаем экземпляр родового объекта R (R_i или R_ij) в том виде, как он появляется в реальном мире.

Первые два условия являются необходимыми для абстракции агрегации и обсуждаются в [1]. Остальные три условия являются необходимыми для абстракции обобщения. Условие 3) при этом обеспечивает, чтобы R_ij являлось подклассом R и, таким образом, чтобы R_ij могло быть обобщено до R. Например, в Таблице II моторизованные транспортные средства V1, V3 и V5 являются также транспортными средствами. Условие 4) обеспечивает, чтобы R_ij содержало все R-индивидуумы, классифицированные как относящиеся к R_ij. Например, в Таблице II часть "Моторизованный транспорт" содержит все транспортные средства, классифицированные таким образом в части "Транспорт". Условие 5), наконец, обеспечивает, чтобы кластеры содержали взаимно-исключающие классы.

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

4. Моделирование с помощью родовой структуры

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

Эта нотация основана на том наблюдении, что агрегация и обобщение являются независимыми действиями. Если задан конкретный объект, обобщения этого объекта могут рассматриваться независимо от связей, в которых этот объект принимает участие. Благодаря этому напрашивается графическая нотация, в которой обобщение и агрегация представляются ортогонально. Мы выбрали для представления агрегации плоскость страницы, а для представления обобщения - плоскость, перпендикулярную странице. Родовая структура, показанная на Рис.5, представлена графически на Рис.7.

Агрегированные объекты верхнего уровня будут при этом показываться вверху страницы, а объекты более низких уровней - ниже, к концу страницы. Таким образом, агрегация показывается вверх по странице. Родовые объекты верхних уровней будут показываться (в имитируемом таким образом трехмерном пространстве) на поверхности страницы, а родовые объекты более низких уровней - ниже поверхности. Обобщение, следовательно, показывается вне страницы.

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

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

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

Построим теперь реляционную модель,^***) удовлетворяющую перечисленным выше требованиям. Поскольку наиболее абстрактным объектом, который должен быть представлен, является "Служащий", начальная модель содержит в точности этот объект. Это показано на Рис.8. Следующий шаг заключается в декомпозиции этого объекта как в плоскости агрегации, так и в плоскости обобщения. Предположим, что мы решаем сначала произвести декомпозицию в плоскости обобщения. В этой плоскости компонентами "Служащего" являются родовые объекты "Водитель грузовика", "Секретарь" и "Инженер". Эти три объекта образуют единственный кластер. После этого модель приобретает вид, представленный на Рис. 9.

Теперь декомпозируем объект "Служащий" в плоскости агрегации. Имеется четыре атрибута служащих, которые должны регистрироваться: "Идентификационный номер", "Фамилия", "Возраст" и "Тип служащих". Поэтому мы включаем эти четыре атрибута как компоненты "Служащего". Полученный результат показан на Рис.10. За исключением "Типа служащих", указанные компоненты объекта "Служащий" являются примитивными объектами, т.е. каждый из них мыслится как единое целое. Однако объект "Тип служащих" имеет несколько важных компонентов, соответствующих атрибутам "Название типа", "Количество", "Вакансии" и "Учреждение". Все эти компоненты - примитивны. Полученная модель представлена на Рис.10.

Мы можем теперь развивать модель, декомпозируя любой объект (который еще не был декомпозирован) в любой плоскости. Поскольку для нас не представляют интерес какие-либо подтипы "Типа служащих", этот объект не декомпозируется в плоскости обобщения. По подобным же причинам мы не декомпозируем объекты "Водитель грузовика", "Секретарь" или "Инженер" в плоскости обобщения. Однако каждый из этих трех объектов должен быть декомпозирован на примитивные объекты в плоскости агрегации. Эти декомпозиции включены на Рис.11. Для обозримости на рисунке не проведены до конца линии, связывающие каждый объект "Идентификационный номер", "Фамилия" и "Возраст" с каждым из объектов "Водитель грузовика", "Секретарь" и "Инженер". Мы можем, наконец, выбрать селекторы и ключи для каждого объекта. Полученная в результате модель представлена на Рис.11.

Определения для отношений "Служащий" и "Тип служащих" даются на Рис.12. Заметим, что отношение "Тип служащих" описывает более детальные сведения о "Водителе грузовика", "Секретаре" и "Инженере", когда они рассматриваются как родовые объекты. Отношение "Служащий" отсылает к этим сведениям через домен образов (т.е. домен с селектором "TN"). Это позволяет для каждого отдельного служащего ссылаться на все родовые свойства подкласса служащих, к которому он относится.

var Служащий:
generic
TN = (Водитель грузовика, Секретарь, Инженер)
of
aggregate [E#]
E#: Идентификационный номер служащего;
N: Имя;
А: Возраст;
TN: Key Тип Служащих
end

var Тип Служащих:
generic of
aggregate [TN]
TN: Имя типа;
N: Количество;
А: Вакансии;
TN:Организация
end

Рисунок 12.
Определение для объектов "Служащий" и "Тип служащих" из Рис. 11.

Вообще, отношение R может иметь в плоскости обобщения несколько кластеров, которые к нему относятся. Для каждого кластера C будет существовать соответствующее отношение, на которое ссылается R в плоскости агрегации. Это отношение будет описывать атрибуты (если они имеются) родовых объектов, принадлежащих C. Можно следующим образом резюмировать это общее свойство реляционных моделей: Атрибуты родовых компонентов абстрактного объекта R определяются в отношениях, которые являются агрегатными компонентами R.

Рассмотрим теперь моделирование различных дополнительных аспектов реального мира, относящихся к служащим. В качестве первого аспекта предположим, что должны моделироваться "Профсоюзы", объединяющие различные типы служащих. Будем считать релевантными следующие атрибуты профсоюза: его название, адрес и руководитель. На Рис.13 объект "Профсоюз" показан в плоскости агрегации объекта "Служащий", а плоскость обобщения опущена (см. Рис.10).

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

var Членство: 
generic of 
agregate [TN, UN] 
TN: key Тип служащих; 
UN: key Профсоюз; 
S: Представитель 
end 

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

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

Второй способ моделирования требуемой связи между служащими и транспортными средствами - это декомпозировать ее в плоскости обобщения на две связи - одна между "Водителем грузовика" и "Грузовиком", а другая между "Инженером" и "Легковым автомобилем". Первая связь может быть абстрагирована как агрегированный объект "Перевозка", а вторая - как "Визит". Эти объекты показаны на Рис.16.

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

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

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

Определение объекта "Работа" с соответствующим выбором селекторов и ключа приводится ниже:

var Работа:
generic of
aggregate [E#, P#]
E#: key Служащий;
P#: key Проект;
T: Название;
PR: Оклад
end

Здесь выбран ключ "E#, P#", поскольку, в соответствии с указанным выше ограничением, работы находятся во взаимно-однозначном соответствии с парами служащий-проект. В этом определении предполагается, что не представляет интереса никакая декомпозиция "Работы" в плоскости обобщения. Теперь предположим, что некоторые пользователи модели заинтересованы в отдельных типах работ. Допустим, что среди проектов имеется проект, связанный с разработкой модемов, и другой, предусматривающий модернизацию принтеров. Некоторые пользователи могут пожелать рассматривать "Работу по модемному проекту" и "Работу по принтерному проекту" как родовые объекты. На Рис.18 показано, каким образом выглядит эта модель после того, как в нее включены эти объекты в статусе потомков "Работы" в плоскости обобщения.

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

Во-вторых, заметим, что каждый тип работы является абстракцией всех работ, относящихся к определенному проекту. Поэтому, одним из атрибутов типа работы должен быть проект, к которому все его работы относятся. Соответственно, на Рис.18 "Проект" показан как атрибут "Типа работы". "Проект" теперь больше не является непосредственным компонентом "Работы", как было показано на Рис.17. Он теперь - косвенный компонент через посредство "Типа работы". Определения объектов "Работа" и "Тип работы" приведены ниже:

var Работа:
generic
TN = (Работа по модемному проекту, Работа по принтерному проекту)
of
aggregate [E#, TN]
E#: key Служащий;
T: Название;
PR: Оклад;
TN: key Тип работы
end

var Тип работы:
generic of
aggregate [TN]
TN: Имя типа;
P#: key Проект;
AP: Средний оклад
end

Обратим внимание на то обстоятельство, что "Работа" представляет собой пример отношения, в котором ключ содержит домен образов.

Введение "Типа работы" иллюстрирует вид реструктуризации, которая часто может стать необходимой по мере того, как эволюционирует приложение модели. В первоначальном приложении для пользователей может представлять интерес общий класс объектов C. В процессе эволюции приложения некоторые пользователи могут стать заинтересованными только в подкатегории C-объектов, чей атрибут A равен некоторому значению v₁, в то время, как другие пользователи будут заинтересованы в подкатегории со значением атрибута A, равным v₂. Эти подкатегории C относительно атрибута A должны быть далее представлены как кластер в плоскости обобщения C. На Рис.18 этот кластер Работа по модемному проекту, Работа по принтерному проекту представляет подкатегоризацию "Работы" по отношению к "Проекту".

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

5. Реляционные инварианты

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

Insert (вставить) - эта операция выполняется, когда становится интересен новый индивидуальный объект;

Delete (удалить) - эта операция выполняется, когда существующий индивидуальный объект перестает быть интересным; и

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

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

а) Каждый R-индивидуум должен определять некоторый уникальный R_i-индивидуум.

б) Никакие два R-индивидуума не определяют одно и то же множество R_i-индивидуумов для всех R_i, селекторы которых принадлежат "списку ключей".

в) Каждый R_ij-индивидуум должен также быть R-индивидуумом.

г) Каждый R-индивидуум, классифицируемый как R_ij, должен также быть R_ij-индивидуумом.

д) Никакой R_ij-индивидуум не является также R_ik-индивидуумом при j<>k.

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

Пусть t - некоторый кортеж, принадлежащий R_ij. Образ-предок t - это некоторый кортеж t" из R, для которого: 1) t и t" имеют одни и те же значения во всех общих доменах и 2) t".ski имеет значение "R_ij". С семантической точки зрения, кортеж и его образ-предок совместно описывают один и тот же индивидуум реального мира; однако, образ-предок принадлежит более высокому уровню обобщения.⁴⁾ Если t" - образ-предок t, то мы говорим, что t - образ-потомок t".

Для представления абстракций мы можем теперь наложить ограничения на отношение вместе с его агрегатными и родовыми компонентами:

а) Для каждого R-кортежа t, если t.s_i не есть "пусто", то в случае, когда R_i - родовой идентификатор, t.s_i является ключом некоторого R_i-кортежа, а в случае, когда R_i - идентификатор некоторого типа, t.s_i имеет тип R_i.

б) Никакие два различных R-кортежа не могут иметь один и тот же ключ.

в) Каждый R_ij-кортеж имеет образ-предок в R.

г) Для каждого R-кортежа t, если t.s_k - не "пусто" и имеет значение R_ij, то R имеет образ-потомок в R_ij.

д) Никакой R-кортеж не может иметь одновременно образы-потомки как в R_ij, так и в R_ik при j<>k.

Эти пять условий мы называем реляционными инвариантами.⁵⁾ Они являются трансформацией пяти предыдущих условий, в соответствии с методом представления родовых объектов как отношений. Имеется одно небольшое исключение, связанное с инвариантами а) и г). Дело в том, что на практике необходимо допускать в некоторых доменах значения "пусто", которые означают "неизвестно" или "безразлично". Инварианты а) и г) предусматривают существование такой возможности.

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

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

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

В дальнейшем обсуждении будут полезны введенные ниже аббревиатуры. Рассмотрим реляционную модель M, которая наряду с прочим содержит отношение R. Будем говорить, что по отношению к R некоторое отношение является:

paR, если оно является предком в плоскости агрегации отношения R;

caR, если оно является потомком в плоскости агрегации отношения R;

pgR, если оно является предком в плоскости обобщения отношения R;

cgR, если оно является потомком в плоскости обобщения отношения R.

На Рис.19 показано, как отношение "подключается" к его отношениям paR, caR, pgR и cgR.

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

Предполагается, что реляционные инварианты удовлетворяются перед операцией обновления. Каждая таблица показывает, каким образом могут быть нарушены инварианты в результате операции обновления, а также какие действия можно предпринять для устранения каждого нарушения. Эти действия всегда сводятся к выполнению операции обновления над одним или несколькими отношениями paR, caR, pgR или cgR. Они, в свою очередь, могут вызвать нарушения и, следовательно, операции обновления над другими отношениями. Таким образом, единственная инициированная пользователем операция обновления может запустить дополнительные операции обновления, которые распространяются как в плоскости агрегации, так и в плоскости обобщения.

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

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

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

Допустим теперь, что мы нарушаем инвариант в), удаляя кортеж t. Это означает, что данный кортеж t", который был образом-потомком t, больше не имеет образа-предка в R. Чтобы устранить это нарушение, мы должны удалить кортеж t". Такое корректирующее действие отражает семантическое требование, состоящее в том, что объект, который не появляется в некотором классе на верхнем уровне обобщения, не может появиться в каком-либо классе на более низком уровне обобщения.

Предположим, наконец, что мы нарушаем инвариант г), модифицируя кортеж t. Имеется два случая, когда может иметь место такое нарушение. Первый случай возникает, когда после модификации t имеет некоторое значение, например R", в каком-либо домене образов, скажем, в домене d, и t еще не имеет никакого образа-потомка в R". В этом случае корректирующее действие зависит от того, изменялся ли d при выполнении данной операции модификации. Если d не изменялся, то должен быть модифицирован старый образ-потомок t в R" так, чтобы сделать его новым образом-потомком. Вся требуемая для этого информация уже имеется в t. Если же d изменялся, то в R" должен быть вставлен образ-потомок. Ключ этого образа-потомка содержится в t, однако, в каждый домен, значение которого не содержится в t, должно быть помещено значение "пусто".

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

Анализируя Таблицу III, можно обнаружить, что существует два метода коррекции нарушений инвариантов а) и г), возникающих вследствие операции удаления. Каждый из этих методов семантически соответствует определенным ситуациям. Рассмотрим сначала инвариант а). Допустим, что имеется абстрактный объект x, агрегатным компонентом которого является некоторый объект y. Возникает вопрос, должен ли удаляться x, если удаляется y. Представляется, что ответ зависит от контекста.

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

Применим аналогичные соображения к инварианту г). Пусть мы имеем общий класс объектов x, который включает все объекты из более специального класса y. Вопрос состоит в том, следует ли удалять объект из x, когда он удаляется из y. Допустим, например, что некоторый объект прекращает быть "Автомобилем Форд". Поскольку изменение изготовителя - не слишком осмысленная интерпретация, естественно предположить, что он перестал быть "Автомобилем" любой марки. С другой стороны, допустим, что некоторый объект прекратил быть "Красным автомобилем". Поскольку достаточно легко перекрасить красный автомобиль в голубой цвет, можно предположить, что данный объект все еще остается "Автомобилем". Следовательно, решение о том, как следует поддерживать инвариант г) при операциях удаления, должно приниматься на более высоком уровне моделирования.

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

С концептуальной точки зрения, запускаемые операции обновления одновременно распространяются несколькими путями. Что произойдет, если какие-либо два из этих путей пересекаются? Может ли одно запускаемое обновление аннулировать результаты работы другого? Является ли итоговый результат определенной пользователем операции обновления независимым от порядка, в котором выполнялись запускаемые операции обновления? Может ли последовательность запускаемых обновлений стать циклической? Если запускаемое обновление является неприемлемым (в связи с тем, что были бы нарушены инварианты б) или д)), то должен быть произведен откат последовательности запускаемых обновлений, и должно быть отвергнуто первоначальное обновление. Каким образом можно узнать, что никакое "корректное" определенное пользователем обновление не будет отвергнуто по этой причине?

Нам хотелось бы потребовать, чтобы любая процедура поддержки инвариантов обладала, по крайней мере, следующими тремя свойствами:

1) Распространение запускаемых обновлений должно в конечном счете завершаться.

2) Общий эффект после завершения распространения независим от порядка, в котором выполняются запускаемые обновления.

3) "Корректное" определяемое пользователем обновление отвергается в единственном случае, когда оно требует поместить значение "пусто" в какой-либо ключевой домен.

Назовем эти свойства завершаемостью (termination), определенностью (determinancy) и согласованностью (compliancy). Мы предполагаем, что процедуры поддержки инвариантов, приведенные в Таблице III, обладают всеми этими тремя свойствами.

6. Заключительные замечания

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

В разделе 3 мы определили, что отношение является правильно определенным, если оно удовлетворяет пяти реляционным инвариантам. Кодд [1] и некоторые другие авторы предложили несколько нормальных форм, как некоторое понятие "хорошего" отношения. Какова связь между правильно определенным отношением и отношением в нормальной форме?

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

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

Рисунок 20.
Отношение в нормальной форме, которое не является эффективно именуемым.

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

В работе [4] была предложена методология проектирования баз данных, которая приводит к агрегатным объектам, а затем - к правильно определенным отношениям. Эта методология не рассматривает, однако, декомпозицию в плоскости обобщения (т.е., неявно предполагались одноуровневые родовые иерархии). Тем не менее, она может быть расширена очевидным образом с тем, чтобы рассматривать декомпозицию в обоих плоскостях. Может быть, наиболее выгодно осуществлять декомпозицию в плоскости обобщения прежде, чем проводить декомпозицию в плоскости агрегации. Причина заключается в том, что каждый кластер, вводимый в плоскости обобщения, требует вставки некоторого нового объекта в плоскости агрегации.

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

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

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

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

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

"Выяснить, какой тип имеет служащий E5, а затем извлечь его запись из множества записей этого типа служащих."

Этот запрос можно удобно выразить в двух частях, как показано ниже:

Часть 1:

R <- RESTRICT (Служащий to E# = E5);
S <- PROJECT (R on TN);
RETRIEVE S;

Часть 2 (в предположении, что ответ на Часть 1 - "Водитель грузовика"):

T <- RESTRICT (Водитель грузовика to E# = E5);
RETRIEVE T;

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

Если бы этот запрос реализовался как прикладная программа, пользователя можно было бы "заместить" приведенным ниже оператором Case:

READ X;
R <- RESTRICT (Служащий to E# = X);
S <- PROJECT (R on TN);
T <- case S of
Водитель грузовика: RESTRICT 
(Водитель грузовика to E# = X);
Секретарь: RESTRICT (Секретарь to E# = X);
Инженер: RESTRICT (Инженер to E# = X)
end
RETRIEVE T;

Проблема с использованием оператора case состоит в том, программа становится зависимой от родовых компонентов "Служащего" в один из моментов времени. Если нанимают служащего нового типа (скажем, "Сторожа"), то программа не будет работать, когда будет введен номер служащего-сторожа.

Эта "зависимость от времени" может быть устранена с помощью оператора высшего порядка, который мы назовем SPECIFY. При заданном имени отношения оператор SPECIFY будет возвращать отношение с таким именем. Теперь можно переписать программу так, как показано ниже.

READ X;
R <- RESTRICT (Служащий to E# = X);
S <- PROJECT (R on TN);
T <- SPECIFY S;
U <- RESTRICT (T to X);
RETRIEVE U;

Новая программа независима от родовых компонентов "Служащего" в любой момент времени.

Введение примитивов высших порядков может, таким образом, повысить стабильность программ, так как взаимодействие с базой данных согласуется с реальным миром. Не ясно, какие другие операторы высших порядков полезны наряду с SPECIFY. Насколько нам известно, эти аспекты программирования приложений должны еще быть исследованы.

Благодарности

Мы благодарны за замечания Р.В.Тейлору и анонимным рецензентам ранней версии этой работы.

Ссылки и библиография

1. Codd, E.F. Further normalization of the data base relational model. In Courant Computer. Science Symposium 6: Data Base Systems, Prentice-Hall, Englewood Cliffs, N.J., May 1971, pp. 33-64.

2. Hoare, C.A.R. Notes on data structuring. In APIC Studies in Data Processing. No. 8: Structured Programming, Academic Press, New York, 1972, pp. 83-174.

3. Quillian, M.R. Semantic memory. In Semantic Information Processing, M.I.T. Press, Cambridge, Mass., 1968, pp. 227-268.

4. Smith, J.M., and Smith , D.C.P. Database abstractions: Aggregation. Commun. ACM, 20, June 1977, pp. 405-413.

^**) Приведенные в таблице аббревиатуры представляют названия профессиональных обществ:
ACM - Association for Computing Machinary - Ассоциация по вычислительной технике, крупная международная организация , объединяющая специалистов во всех областях информатики. Ряд Секций ее Групп по интересам (SIG) работает в России.
IEEE - IEEE (The Institute of Electrical and Electronics Engineers, Inc.) Computer Society - Институт инженеров в области электротехники и электроники, крупная международная организация , объединяющая профессионалов в области информатики.
AMA - American Medical Association - Американская Ассоциация медицинских работников.

^***) Здесь и далее авторы используют понятие "реляционная модель", в соответствии с ранней (структурной) трактовкой понятия "модели данных". - Примеч. пер.

^****) Авторы имеют в виду Рабочую группу по базам данных КОДАСИЛ (CODASYL Data Base Task Group), опубликовавшую в 1969 году целостную концепцию систем управления базами данных сетевой структуры, включающую, в частности, первоначальную версию соответствующей модели данных, а также спецификации основанных на этой модели данных, а также спецификации основанных на этой модели языковых средств определения данных и манипулирования данными. В литературе, однако, чаще всего цитируется отчет DBTG 1971 года, содержащий следующую, значительно более продвинутую версию ее предложений. (См. Язык описания данных КОДАСИЛ. /Пер. с англ. - М.: Статистика, 1981.) - Прим. перев.