Классика баз данных - статьи

       

Абстракции обобщения


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

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

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

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

  1. применение операций к родовым объектам;

  2. спецификацию атрибутов для родовых объектов;
  3. спецификацию связей, в которых участвуют родовые объекты.

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

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

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

Родовой объект, подобно индивидуальному, может участвовать в связях с другими объектами. В качестве примера мы можем рассмотреть связь между "профессиями" и примыкающими к ним "сообществами". К числе конкретных профессий относятся "водитель грузовика", "computer scientist" и "докторa", и все они являются родовыми объектами. Эта связь, которая называется "принадлежность", представлена в таблице I. Заметим, что "профессия" – это обобщение класса, который включает "водителя грузовика", "computer scientist" и "доктора".



Таблица I. Родовые объекты, участвующие в связи

Принадлежность:

Профессия

Сообщество

computer scientist

computer scientist

доктор

водитель грузовика

инженер-электрик

ACM

IEEE

AMA

Teamsters

IEEE

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


Эти средства очень разнотипны и включают, например, грузовики (truck), подводные лодки (submarine), велосипеды (bicycle), вертолеты (helicopter).

На рис. 1 показан конкретный вариант декомпозиции "транспортного средства" на родовые объекты более низкого уровня. Заметим, что отдельные транспортные средства при этом явно не представляются. Следует представлять, что каждый родовой объект определяет некоторый класс индивидуальных транспортных средств. На рисунке видно, например, что "грузовик" (truck), "велосипед" (bike) и автомобиль (car) могут быть обобщены понятием "дорожное транспортное средство" (road vehicle), "дорожное транспортное средство" и "рельсовое транспортное средство" (rail vehicle) – понятием "наземное транспортное средство" (land vehicle), и, наконец, что "наземное транспортное средство", "воздушное транспортное средство" (air vehicle) и "водное транспортное средство" (water vehicle) могут быть обобщены понятием "транспортное средство".



Рис. 1. Родовая иерархия транспортных средств

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


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

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

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



Рис. 2. Родовая иерархия, не являющаяся деревом



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

Рис. 2 показывает, что объект "вертолет" может быть обобщен двумя способами – как "моторизованное транспортное средство" (motorized vehicle”) либо как "воздушное транспортное средство" (air vehicle). Рис. 3 иллюстрирует декомпозицию объекта "транспортное средство" на два различных вида родовых объектов.


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

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

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



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

Опишем теперь метод представления родовой иерархии как иерархии отношений Кодда. Для каждого родового объекта в иерархии будет создаваться одно отношение. Пусть G – родовой объект такой, что

  1. I есть класс конкретных объектов, ассоциированных с G;
  2. A1, ..., An

    – G-атрибуты и


  3. C1, ..., Cm

    – имена кластеров, принадлежащих G.
Тогда G представляется следующим отношением Кодда:

A 1

 ... 

 A n

C1

 ... 

Cm

...

 v 1

...

 ... 

 ... 

 ... 


...

 v n

...

...

vn+1

...

 ... 

 ... 

 ... 


...

vn+m

...

где:

  1. имеется один и только один кортеж для каждого индивидуума в I;


  2. если значением атрибута Ai индивидуума является vi, то его кортеж содержит vi в домене Ai;


  3. если индивидуум включается также в родовой объект vn+j

    в кластере Cj, то его кортеж содержит vn+j

    в домене Cj;


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


Таблица II. Примеры отношений Кодда для трех родовых объектов из иерархии на

транспортное средство:

идент.
номер

изготовитель

цена

вес

категория
среды
передвижения

категория
двигателя

V1

Mazda

65.4

10.5

наземное
транспорт.
средство

мотор.
транспорт.
средство

V2

Schwin

3.5

0.1

наземное
транспорт.
средство

транспорт.
средство,
привод. в
движение
человеком

V3

Boeing

7,900

840

воздушное
транспорт.
средство

мотор.
транспорт.
средство

V4

Aqua Co

12.2

1.9

водное
транспорт.
средство

транспорт.
средство,
привод. в
движение
ветром

V5

Gyro Inc

650

150

воздушное
транспорт.
средство

мотор.
транспорт.
средство

<


моторизованное транспортное средство:

идент.
номер

изготовитель

цена

вес

мощность
в л.с.

запас
горючего

категория
мотора

V1

Mazda

65.4

10.5

150

300

роторное
траспорт.
средство

V3

Boeing

7,900

840

9600

2600

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

V5

Gyro Inc

650

150

1500

2000

роторное
траспорт.
средство

воздушное транспортное средство:

идент.
номер

изготовитель

цена

вес

максим.
высота

пробег
при взлете

категория
подъем.
механизма

V3

Boeing

7,900

840

30

1000

самолет

V5

Gyro Inc

650

150

5.6

0

вертолет

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



Рис. 4. Родовая иерархия транспортных средств

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

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

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

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


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


Этот вопрос обсуждается далее в .


Содержание раздела