Конверсия реляционных баз данных в объектно-ориентированные и соответствующая трансляция запросов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Станишич, Предраг

• Станишич, Предраг
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Станишич, Предраг

Оглавление

ВВЕДЕНИЕ

1 ОБЗОР РЕЛЯЦИОННОЙ МОДЕЛИ

1.1 ВВЕДЕНИЕ

1.2 СТРУКТУР А ДАННЫХ

1.3 ОПЕРАЦИИ МАНИПУЛИРОВАНИЯ ДАННЫМИ

1.4 ЯЗЫК ЗАПРОСОВ SQL

1.5 ОГРАНИЧЕНИЯ ЦЕЛОСТНОСТИ

2 ОБЗОР ОБЪЕКТНО-ОРИЕНТИРОВАННОЙ МОДЕЛИ

2.1 ВВЕДЕНИЕ

2.2 ЯДРО ОБЪЕКТНО-ОРИЕНТИРОВАННОЙ МОДЕЛИ ДАННЫХ

2.2.1 ОБЪЕКТ

2.2.2 СООБЩЕНИЕ, МЕТОД ИНКАПСУЛЯЦИЯ

2.2.3 КЛАСС

2.2.4 НАСЛЕДОВАНИЕ

2.3 ЯЗЫК ЗАПРОСОВ

3 ТРАНСФОРМАЦИЯ СХЕМЫ РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ В ОБЪЕКТНО-ОРИЕНТИРОВАННУЮ

3.1 ВВЕДЕНИЕ

3.2 ОПИСАНИЕ ПРОЦЕДУРЫ ТРАНСФОРМАЦИИ СХЕМЫ

3.2.1 СЛУЧАЙ 1

3.2.2 СЛУЧАЙ 2

3.2.3 СЛУЧАЙ 3

3.2.4 СЛУЧАЙ 4

3.2.5 СЛУЧАЙ 5

3.2.6 СЛУЧАЙ 6

3.2.7 СЛУЧАЙ 7

3.3 ПРИМЕР ТРАНСФОРМАЦИИ СХЕМЫ

4 КОНВЕРСИЯ ДАННЫХ В СООТВЕТСТВИИ С ТРАНСФОРМАЦИЕЙ СХЕМЫ

4.1 ВВЕДЕНИЕ

4.2 ПЕРВЫЙ АЛГОРИТМ КОНВЕРСИИ ДАННЫХ

4.2.1 ОСНОВНЫЕ ИДЕИ

4.2.2 ОПИСАНИЕ АЛГОРИТМА

4.2.3 КОНСТРУИРОВАНИЕ ЗАПРОСОВ

4.2.3.1 СЛУЧАЙ 1 ОБЫЧНЫЕ КЛЮЧИ

4.2.3.2 СЛУЧАЙ 2 НАСЛЕДОВАНИЕ

4.2.3.3 СЛУЧАЙ 3 ВНЕШНИЙ КЛЮЧ НЕ СОДЕРЖИТСЯ В

ВОЗМОЖНЫХ КЛЮЧАХ

4.2.3.4 СЛУЧАЙ 4 ВОЗМОЖНЫЙ КЛЮЧ, СОДЕРЖАЩИЙ

ВНЕШНИЕ КЛЮЧИ

4.2.4 ПРИМЕР КОНВЕРСИИ ДАННЫХ

4.3 ВТОРОЙ АЛГОРИТМ КОНВЕРСИИ ДАННЫХ

4.3.1 ОСНОВНЫЕ ИДЕИ

4.3.2 ОПИСАНИЕ АЛГОРИТМА

4.3 .3 ПРИМЕР РАБОТЫ ВТОРОГО АЛГОРИТМА КОНВЕРСИИ

ДАННЫХ

5 ТРАНСЛЯЦИЯ РЕЛЯЦИОННЫХ 80Ь-ЗАПРОСОВ В ЭКВИВАЛЕНТНЫЕ

ЗАПРОСЫ К ТРАНСФОРМИРОВАННОЙ БАЗЕ ДАННЫХ

5.1 ВВЕДЕНИЕ

5.2 ТРАНСЛЯЦИЯ 8ЕЬЕСТ-ЗАПРОСОВ

5.2.1 ЭКВИВАЛЕНТНОЕ ПРЕОБРАЗОВАНИЕ РЕЛЯЦИОННОГО

БЕЬЕСТ-ЗАПРОС А

5.2.1.1 СЛУЧАЙ 1

5.2.1.2 СЛУЧАЙ 2

5.2.1.3 СЛУЧАЙ 3

5.2.1.4 СЛУЧАЙ 4

5.2.2 КОНСТРУИРОВАНИЕ ГРАФА РЕЛЯЦИОННОГО ПРЕДИКАТА ИЗ WHERE-ЧАСТИ РЕЛЯЦИОННОГО SELECT-ЗАПРОСА

5.2.3 КОНСТРУИРОВАНИЕ ГРАФА ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРЕДИКАТА ИЗ ГРАФА РЕЛЯЦИОННОГО ПРЕДИКАТА

5.2.3.1 ТРАНСФОРМАЦИЯ ВЕРШИН

5.2.3.2 ТРАНСФОРМАЦИЯ РЕБЕР

5.2.3.3 ТРАНСФОРМАЦИЯ МЕТОК ВЕРШИН

5.2.4 КОНСТРУИРОВАНИЕ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРЕДИКАТА ИЗ ЕГО ГРАФА

5.2.4.1 АЛГОРИТМ

5.3 ТРАНСЛЯЦИЯ DELETE-, UPDATE- И INSERT-ЗАПРОСОВ

5.3.1 ОПРЕДЕЛЕНИЕ ДЕРЕВА АТРИБУТА

5.3.2 ВЫЧИСЛЕНИЕ ВЫРАЖЕНИЙ ПУТИ ДЛЯ АТРИБУТА

5.3.3 ТРАНСЛЯЦИЯ DELETE-ЗАПРОСОВ

5.3.4 ТРАНСЛЯЦИЯ UPDATE-ЗАПРОСОВ

5.3.5 ТРАНСЛЯЦИЯ INSERT-ЗАПРОСОВ

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ

131

Введение диссертации (часть автореферата) на тему «Конверсия реляционных баз данных в объектно-ориентированные и соответствующая трансляция запросов»

Введение

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

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

Похожая проблема возникает и в неоднородных системах ([13, 14, 16, 18, 19]), которые содержат различные типы систем управления базами данных. Возникают многие трудности для пользователей, если они хотят оперировать данными, хранимыми в системах с разными моделями данных и языками запросов. Поэтому в неоднородных системах должны существовать механизмы преодоления этих трудностей.

В принципе, существуют три подхода к применению объектно-ориентированной технологии для реляционных баз данных:

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

■ миграция в объектно-реляционные системы управления базами данных ([22]),

■ конверсия реляционной базы данных в объектно-ориентированную. Какой из этих подходов применить, зависит от конкретной ситуации.

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

Процесс конверсии базы данных из одной модели в другую можно разделить на две фазы ([1, 29]):

■ трансформация схемы базы данных из одной модели в другую,

■ конверсия данных в соответствии с трансформацией схемы.

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

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

построении алгоритмов, которые автоматически, т.е. без вмешательства пользователя, выполняют этот процесс и соответствующую трансляцию SQL-запросов в объектно-ориентированные запросы. В работе предлагаются алгоритмы трансформации схемы, два алгоритма конверсии данных и алгоритмы трансляции SELECT-, DELETE-, INSERT- и UPDATE-запросов.

Для задачи конверсии реляционной базы данных в объектно-ориентированную весьма важен выбор исходной реляционной и целевой объектно-ориентированной модели. Существует много реляционных моделей (базовая модель Кодда, RM/2, RM/T, SQL-89, SQL-92, дополнения к SQL-92,... [24, 26, 27, 2, 7, 10, 17]) и объектно-ориентированных моделей (OMG, ODMG, С++, SmallTalk, ... [7, 8, 32, 15]). Каждая модель из этих двух семейств обладает некоторыми особенностями, преимуществами и недостатками по отношению к другим моделям из своего семейства. Чем более богатыми модели являются, т.е. чем больше концептов они содержат, тем больше существует дополнительных возможностей отображения базы данных из одной модели в другую (см. например [9, 11], где используется концепт зависимости по включению). Использование каждой дополнительной возможности может существенно усложнить задачу конверсии. Кроме того, дополнительные возможности иногда не приносят никакой существенной пользы, а иногда делают совсем невозможной автоматизацию всего процесса конверсии. Нашей целью является теоретическое исследование и иллюстрация реальной возможности автоматического проведения процесса конверсии реляционной базы данных в объектно-ориентированную, а также соответствующей трансляции запросов, вместе с изучением связей между фазами этого процесса.

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

С реляционной стороны, в работе используется базовые реляционные концепты - отношение, атрибуты, внешние и возможные ключи, и т.п. (см. п. 1). Что же касается языка запросов, для SELECT-, DELETE-, INSERT- и UPDATE-запросов используются соответствующие конструкции языка SQL в рамках стандарта SQL-92.

С объектно-ориентированной стороны в работе рассматривается так называемое ядро объектно-ориентированной модели (см. п.2, [8]). Ядро объектно-ориентированной модели - это множество концептов, которые приняты большинством исследователей и которые являются фундаментально важными концептами моделирования данных. Ядро включает следующие концепты: объект и объектный идентификатор, атрибуты, методы и передача сообщений, инкапсуляция, класс, а также иерархия классов и наследование. Практически все существующие объектно-ориентированные модели данных поддерживают тем или иным образом концепты ядра и добавляют некоторое число вариаций на конкретные интерпретации этих концептов. Концепты ядра не изменяются, так как ядро является относительно малым множеством фундаментальных и простых концептов. В качестве языка запросов объектно-ориентированной модели в данной работе принимается язык, описанный в п.2.3 (см.[5]), так как он достаточно хорошо использует концепт выражения пути, который является важным свойством объектно-ориентированной модели. В данной работе реляционные SQL-запросы без выражений пути транслируются в запросы объектно-ориентированной системы, которые содержат выражения пути.

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

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

В работе построен алгоритм трансформации схемы реляционной базы данных в объектно-ориентированную, который автоматически (в отличие от, например, [20, 30]) анализирует семантику схемы реляционной базы данных и трансформирует ее в объектно-ориентированную без помощи пользователя. В этом алгоритме отношения отображаются в классы, а связи между классами идентифицируются с помощью взаимосвязей возможных и внешних ключей. При наличии других концептов как в реляционной так и в объектно-ориентированной модели данных возможны и другие способы отображения. Отношения можно непосредственно отображать в классы (см. например [21]), но при этом теряется семантика реляционной базы данных. Целью предложенного в работе алгоритма является получение из реляционной схемы тех объектно-ориентированных концептов, которые адекватны действительной семантике базы данных (в отличие от [28, 31] где полученная объектно-ориентированная схема является почти реляционной). Из использованных семи наиболее информативных случаев взаимосвязей внешних и возможных ключей пять случаев известны из литературы ([3]), а два предлагаются автором. В работе все случаи детально проанализированы и предложен порядок их обработки, разрешающий значительное число конфликтов, которые могут возникнуть. Порядок обработки случаев изменяется только в некоторых специально оговоренных ситуациях. Кроме того, в этом алгоритме в соответствующих структурах сохранена вся информация, необходимая для следующих фаз процесса конверсии.

Для создания целевой объектно-ориентированной базы данных, необходимо провести конверсию данных в соответствии с трансформацией схемы. Так как отношения отображаются в классы, в рамках использованных моделей естественным является отображение кортежей

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

Первый алгоритм конверсии данных, в отличие от второго, основан на предположении, что классы в объектно-ориентированной схеме содержат точно те атрибуты, которые описаны в процессе трансформации, т.е. не существует никаких дополнительных атрибутов, содержащих избыточную информацию. Этот факт является проблемой при конверсии данных, так как в некоторых ситуациях нет возможности однозначно идентифицировать нужный экземпляр класса. Чтобы позже изменять экземпляры, необходимо иметь возможность однозначно идентифицировать тот экземпляр, который мы хотим изменять. Это изменение, конечно, может выполнить только целевая объектно-ориентированная система, и потому алгоритм конверсии данных должен в качестве результата иметь последовательность INSERT- и UPDATE-запросов объектно-ориентированного языка запросов, которые ООСУБД может непосредственно выполнить, в результате чего получается объектно-ориентированная база данных, эквивалентная исходной реляционной базе данных.

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

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

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

Предлагаются методы трансляции SELECT-, DELETE-, UPDATE- и INSERT-запросов языка SQL в соответствующие объектно-ориентированные запросы.

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

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

Для трансляции DELETE-, UPDATE- и INSERT-запросов в работе вводится понятие дерева атрибута отношения. Эти деревья используются для вычисления выражений пути для тех атрибутов, которые в трансформированной объектно-ориентированной схеме играют роль атрибутов реляционных запросов. С помощью этих выражений пути формируются эквивалентные объектно-ориентированные DELETE-, UPDATE- и INSERT-запросы.

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

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

1 Обзор реляционной модели

1.1 Введение

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

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

■ структурная простота

■ формальное и строгое обоснование

■ экономичные языки запросов

■ разграничение уровней представления данных

Существует много реляционных моделей (базовая модель Кодда, RM/T, SQL-86, SQL-89, SQL-92, дополнения к SQL-92, ... [24, 26, 27, 2, 7, 10, 17]). В работе используется модель, содержащая фундаментальные и наиболее часто встречающиеся концепты, которые определяют принадлежность некоторой модели семейству реляционных моделей. Для SELECT-, DELETE-, INSERT- и UPDATE-запросов используются соответствующие конструкции языка SQL, в рамках стандарта SQL-92.

В пункте 1.2 описывается структура данных, в пункте 1.3 описываются операции манипулирования данными, а в пункте 1.4 использованная часть языка запросов SQL.

Большинство определений в этой главе взято из [2] и [7].

1.2 Структура данных

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

Пусть Э], D2, ..., Оп (пе1Ч) будут домены (не обязательно разные).

Декартово произведение доменов, обозначим его через 0|х Т>2 х ••• х Оп,

есть множество п-кортежей вида (у^, \2, ... , Уд) причем е для

каждого 1 = 1, 2 , ... , п. Отношение г (или отношение с названием г) степени п, определенное на доменах Т>2, ..., Оп, есть любое

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

Если вместо множества индексов доменов {1,2, ... , п} возьмем любое множество различно именованных индексов {А^, А2, ... , Ап}, тогда каждый элемент ^ кортежа характеризуется не только доменом но и индексом А\. Разные именованные индексы А^ (1=1, 2, ... , п) называются атрибутами (или атрибутами с названиями А^) отношения г и обозначают

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

множество из п упорядоченных пар (Aj, vj), i=l, 2, ... , п, где vj является значением из домена Dj. Здесь г - это название отношения.

С помощью отношения г представляется некоторое множество сущностей Е, а n-кортежами этого отношения представляются отдельные сущности типа Е. Поэтому каждый атрибут А[ отношения г можно

интерпретировать как отображение типа сущностей Е в соответствующий домен Dj, т.е.

Ai:E-*Di.

Аналогично, каждое подмножество {Ajj, Aj2,..., А^} множества

атрибутов отношения г можно интерпретировать как отображение (Aij, Ai2,..., Aik) : Е Dijx Di2 х ... х Dik

Несмотря на факт, что Dj здесь является кодоменом отображения (т.е. атрибута) Aj, в терминологии реляционной модели он называется доменом атрибута Aj и обозначается dom(Aj). Аналогично, с1от(Ац, Aj2,..., А[к) обозначает домен множества атрибутов {Ац, Aj2,..., Ajk}, т.е. множество Вцх Dj2 х ... х D]^ .

Пусть е будет сущностью типа Е. Тогда элемент vj е Dj есть значение атрибута Aj сущности е (т.е. соответствующего п-кортежа), если Aj(e)=vj. Аналогично, элемент (vjj, vj2, ••• , v^)g Djjx Dj2 x ... x есть значение множества атрибутов {Ац, Aj2, ... , А^} сущности е (т.е. соответствующего n-кортежа), если (Ац, Aj2,..., А^)(е)=(уц, vj2, ..., v^).

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

создают множество. Обозначение г(А1:01, А2'.Т>2 >■••> АП:ВП), которое

используется для представления отношения г, чей атрибут А] имеет

значения из домена атрибут А2 имеет значения из домена 02 , и т.п.,

называется схемой отношения г. Если понятно, о каких доменах идет речь, либо если это не важно для дальнейшего изложения, будем пользоваться обозначением г(А^, А2, ... , Ал) или г(А]А2 ... Ад). Схемы

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

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

1.3 Операции манипулирования данными

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

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

вычисления. В отличие от реляционной алгебры, реляционное исчисление -это декларативный язык.

Реляционная алгебра есть множество операций на отношениях. Реляционное выражение в реляционной алгебре состоит из последовательности операций над соответствующими отношениями. Операциями реляционной алгебры являются традиционные операторы на множествах - объединение, пересечение и разность, и специальные операторы - селекция, проекция, произведение, соединение и деление. Операторы на множествах имеют стандартную семантику; их результатом являются объединение, пересечение или разность множеств п-кортежей содержащихся в отношениях, к которым эти операторы применяются. Селекция, применяемая к некоторому отношению г, дает в результате отношение, содержащее все кортежи отношения г, которые удовлетворяют определенному условию. Проекция отношения г на множество атрибутов X дает отношение, содержащее только те столбцы отношения г, которые соответствуют атрибутам X. Произведение отношений есть операция, которая дает отношение, содержащее по одному кортежу для каждой пары кортежей из отношений, к которым произведение применяется. Новый кортеж (концептуально) создается таким образом, что к кортежу одного отношения дописывается кортеж второго отношения. Соединение похоже на произведение, только здесь комбинируются кортежи из двух отношений, которые имеют одинаковые значения на общих атрибутах, а при создании нового кортежа удаляется по одному атрибуту из каждой пары общих атрибутов (это, по существу, так называемое естественное соединение). Деление отношения г со схемой К на отношение 5 со схемой Я, где Я сг Я , дает отношение со схемой Я-Я, которое является подмножеством проекции отношения Л на множество атрибутов Результирующее отношение содержит все кортежи, которым в отношении г соответствуют все кортежи отношения 5.

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

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

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

1.4 Язык запросов SQL

Здесь, в кратких чертах описывается самый популярный реляционный язык запросов Structured Query Language или SQL. Этот язык стандардизован и получил широкое распространение. Вместо более формального описания SQL приводится несколько коротких примеров, которые демонстрируют основные характеристики языка. Дается также описание SELECT, DELETE, UPDATE и INSERT-запросов.

SELECT-запросы имеют вид SELECT - FROM - WHERE.

SELECT-часть SELECT-запроса специфицирует названия атрибутов отношений, которые являются результатом выполнения запроса.

FROM-часть SELECT-запроса специфицирует кортежные переменные отношений (КПО), которые использованы в запросе. Например, во FROM-части некоторого SELECT-запроса "FROM student, person as X" определены две кортежные переменные отношений, student и X, доменами которых являются отношения student и person, соответственно.

WHERE-часть SELECT-запроса специфицирует квалификационное условие запроса, т.е. условие, которому должны удовлетворять текущие значения КПО, чтобы эти значения вошли в результат. В работе предполагается, что WHERE часть реляционного SELECT-запроса задана в конъюнктивном виде и что не существуют вложенности, так как каждый реляционный запрос можно привести к этому виду (см. [6]).

Пусть, например, даны отношения student (studentid, name, lastjiame), profesor(profesorJd, name, last name) и exam(profesor_id, student id, exam name, mark). Тогда запрос: "SELECTX. name, Xlastname FROM student AS X, profesor, exam WHERE (X.student id=exam. student Jd) AND

(exam, profesor id = profesor, profesor id) AND (exam_name= 'mathematics') AND (exam.mark>8) AND (profesor, last_name=Smith) " возвращает имена и фамилии всех студентов, которые сдали экзамен по математике у профессора Смита с оценкой более чем 8.

Реляционные DELETE-запросы имеют вид DELETE - WHERE. DELETE-часть DELETE-запроса специфицирует отношение, к которому относится этот запрос. Как и для SELECT-запроса, WHERE-часть DELETE-запроса специфицирует квалификационное условие запроса, т.е. условие, которому должны удовлетворять текущие значения кортежей отношения, чтобы они были удалены. WHERE-часть DELETE-запроса может содержать и подзапросы, которые являются SELECT-запросами. Например, запрос:

"DELETE student

WHERE (student. пате= 'John') AND EXISTS (SELECT exam FROM exam WHERE (exam.student Jd=student, student Jd)) AND OR NOT( (student. last_name= 'Smith')) " удаляет всех студентов, для которых выполняется условие: их фамилии отличаются от Smith, их имена John, и они сдали хотя бы один экзамен.

UPDATE-запросы имеют вид: UPDATE - SET - WHERE. UPDATE-часть UPDATE-запроса специфицирует отношение, к которому относится этот запрос, а WHERE-часть запроса специфицирует квалификационное условие запроса. Как и для DELETE-запроса, WHERE-часть UPDATE-запроса может содержать и подзапросы. SET-часть UPDATE-запроса специфицирует атрибуты и значения, которые им надо присвоить. Значения не обязательно являются константами. Они могут содержать арифметические операции над атрибутами, а также и подзапросы. Например, запрос:

"UPDATE student SET student Jd= student id +1,

name=(SELECT student, name FROM student WHERE student. id= 45) WHERE (student. last_name= 'Smith') " увеличивает на единицу идентификатор студента с фамилией Smith, и его имени присваивает имя студента с номером 45.

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

"INSERT INTO student (studentJd, name, last name) VALUES(5, 'John', 'Smith')".

Вместо VALUES-части может стоять и подзапрос. Например: "INSERT INTO old students (studentJd, name, last name) SELECT student, student id, student, name, student, last name FROM student

WHERE (student.name= 'John') AND (student.last_name= 'Smith') ".

1.5 Ограничения целостности

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

Частные условия целостности имеют два вида. Во-первых, это могут быть характеристики частных атрибутов или их доменов или связи между частными значениями атрибутов п-кортежей одного или более отношений. Например, тираж в издательстве "МГУ" не может быть меньше чем 1000 экземпляров. Вторым видом частных условий целостности являются логические связи, существующие между атрибутами одного отношения. Например, один атрибут может однозначно определять некоторый иной атрибут. Второй вид частных условий целостности формализуется с помощью различных видов зависимостей между атрибутами. Зависимости играют важную роль в логическом проектировании базы данных. Опишем здесь наиболее часто встречающийся вид зависимости - функциональную зависимость, которая используется в определении первичного, возможного и внешнего ключа.

Пусть X, У е {А^, А2, ... , Ап} - непустые подмножества множества

атрибутов отношения г(А}, А2, ... , Ад). Обозначим через г[ХУ] проекцию

отношения г на объединение множеств атрибутов X и У (атрибуты в пересечении берутся только один раз). Тогда между множествами атрибутов X и У существует функциональная зависимость, которая обозначается X -» У, если в каждый момент существования отношения г г[ ХУ] является функцией г[Х] -» г[У], т.е. если для каждой пары кортежей Ц,

t2&r, для которых выполняется ^[Х] = 12[X], также выполняется и 1^[У] =

12[У]. Далее, определяем понятия первичных, возможных и внешних ключей.

Пусть X е{ А}, А2, ... , Ап} будет непустое подмножество множества атрибутов отношения г(А|, А2, ... , Ад). Тогда множество X есть

возможный ключ отношения г, если выполняются условия:

a) имеют место функциональные зависимости X А[ для 1=1, 2, ..., п

(свойство уникальности)

b) не существует подмножество множества X, несовпадающее с X, которое обладает свойством а), т.е. для каждого множества X' сХ, причем X' ф X, существует 1 < j < п, для которого не выполняется

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

выполняется функциональная зависимость {А], А2, ... , Ап}-> А], для каждого 1 < 1 < п. Значит, множество {А], А2, ... , Ап} всех атрибутов отношения г является его надюпочом. Если не существует, несовпадающее с этим множеством подмножество с этим свойством, то множество {А], А2, ... , Ап} есть возможный ключ. Если такое подмножество существует,

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

Пусть даны два отношения г] и г2 (не обязательно различные) и пусть

отношение Г2 содержит возможный ключ СК. Внешний ключ отношения

гу, который указывает на возможный ключ СК отношения г2, есть

подмножество РК множества атрибутов отношения Г], для которого

выполняется условие, что в каждый момент, значения атрибутов РК в отношении гу являются подмножеством множества значений атрибутов

возможного ключа СК в отношении г2-

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

2 Обзор объектно-ориентированной

модели

2.1 Введение

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

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

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

В настоящее время существует целое семейство объектно-ориентированной моделей данных, например OMG, ODMG, С++, SmallTalk, ... ([8, 32, 15, 7]). Из-за того, что между исследователями существуют различия в том, какие точно концепты содержит объектно-ориентированная модель, удобно идентифицировать минимальное множество объектных концептов, которые приняты большинством исследователей и которые поддерживает (тем или иным образом) каждая объектно-ориентированная система. Это множество концептов называется ядром объектно-ориентированной модели данных ([8]).

2.2 Ядро объектно-ориентированной модели данных

Ядро объектно-ориентированной модели данных содержит следующие концепты:

■ объект

■ класс

■ сообщение и метод

■ инкапсуляция

■ наследование

2.2.1 Объект

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

переменных (или атрибутов). Роль идентификатора - заменить объект, когда он является значением экземплярной переменной некоторого другого объекта. Например, объект, идентификатор которого есть о j, может иметь

экземплярные неременные пате, со значением John Smith, birth date со значением 1.9.1972 и chief со значением pj, где р; является уникальным

объектным идентификатором объекта - шефа человека о] . 2.2.2 Сообщение, метод, инкапсуляция

Поведение объекта описывается множеством сообщений, на которые объект может отвечать. Для объекта о j этими сообщениями могут быть,

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

имеет доступа, например, к экземплярной переменной birth date. Эту переменную можно использовать в методе age, чтобы по отношению к текущей дате вычислить возраст человека oj. В отличие от этой "чистой"

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

2.2.3 Класс

Каждый объект принадлежит некоторому классу, определяющему структуру объектов этого класса (экземплярные переменные или атрибуты) и множество операций и функций, которые можно выполнять над объектами этого класса (сообщения). Объект называется экземпляром класса, которому он принадлежит. Атрибуты и сообщения определяются на уровне класса, а применяются к экземплярам класса. Методы, которые реализуют сообщения - операции и функции, реализуются на уровне класса. Например, объект oj может принадлежать классу person,

экземплярными переменными которого являются name, birth date и chief. Сообщениями класса person, т.е. его методам, являются те, которые применяются к объекту о j .

Значением атрибута а объекта класса X может быть объект, т.е. объектный идентификатор объекта из некоторого класса Y. Этот объектный идентификатор ссылается на объект класса Y и поэтому этот концепт называется ссылкой или сложным атрибутом. Тогда класс Y является доменом атрибута а класса X и может иметь любую сложную структуру. В определении класса X этот факт обозначается выражением а : ref Y . Таким образом, определение класса X можно рассматривать как направленный граф иерархии композиции классов. Эта иерархия, которую иногда называют и горизонтальной иерархией классов, не является типичной иерархией, так как она может содержать циклы. Этот граф, по существу, представляет отношение агрегации между классом X и классами, которые являются доменами сложных атрибутов класса X.

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

2.2.4 Наследование

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

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

Структура классов, вместе с горизонтальной и вертикальной иерархиями классов образует объектно-ориентированную схему.

2.3 Язык запросов

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

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

Для задачи трансляции реляционных SQL-запросов в объектно-ориентированные предполагаем, что объектно-ориентированная система поддерживает язык запросов, похожий на SQL, т.е. что основной оператор этого языка имеет вид SELECT-FROM-WHERE.

SELECT-часть запроса, как и для реляционного запроса, специфицирует названия атрибутов классов, которые являются результатом выполнения запроса. Р<1зличие в том, что для объектных запросов SELECT-часть может содержать так называемые выражения пути (path expressions). Например, выражение "student.adviser.name".

FROM-часть объектного запроса специфицирует экземплярные переменные классов (ЭПК), которые используются в запросе аналогично тому, как используются кортежные переменные отношений во FROM-части реляционного запроса. Различие заключается в том, что во FROM-части объектного запроса могут быть определены переменные, связанные с обычными выражениями пути или с так называемыми выражениями пути с селещиями. Например, выражение "X (student: groups 123). adviser, name" связывает переменьсую X с выражением пути (student:

group=l 23).adviser.name. Это значит, что переменная Xпробегает все имена руководителей студентов группы 123. Эти переменные называем ссылочными.

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

1. ЛеваяЧасть есть выражение вида Termj.Term2...Termn. Здесь Termj

есть выражение вида (ЭПК}: Селекции-на-классеj), Termj есть

выражение вида (ATRf.j: Селекции-на-(1от(АТК1_¡)), причем ATRj.j

есть сложный атрибут класса, соответствующего 3I7Kj_j и

dom(ATBj_])=Kiaccj_], за i=2,...,n. Termn может быть и обычным

(простым) атрибутом. Выражение Селекции-на-классе/ состоит из

конъюнкции селекций вида А Компаратор Значение, где А -обычный атрибут класса Классу а Компаратор один из операторов

<,>,=, *,<= или >=.

2. ПраваяЧастъ есть выражение одного из следующих видов:

- отсутствует {Компаратор тоже отсутствует)

- константа. В этом случае Компаратор является одним из операторов <,>,=, Ф,<= или >=.

- то же самое, что и ЛеваяЧасть (это, по существу, явное соединение).

Пример. Запрос "Найти всех студентов, средняя оценка которых больше чем 9 и научный руководитель которых имеет офис в здании номер 3" можно выразить как:

'SELECT Student. Adviser.Name

FROM Student

WHERE (Student:Average 9). (Adviser:). (Office:). (Building: Number=3)'.

Здесь, Adviser есть сложный атрибут класса Student, домен которого есть класс Professor.

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

3 Трансформация схемы реляционной базы данных в объектно-ориентированную

3.1 Введение

Формально, ([1, 25]) трансформацию схемы , определенной средствами модели данных М], в другую схему , определенную средевами модели данных М2, определяем как трансформацию Т:

Трансформация есть множество правил, которые отображают концепты исходной модели данных М| в концепты модели данных М2 .

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

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

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

■ объект

■ класс

■ наследование

■ ссылки (сложные атрибуты).

Для трансформации реляционной схемы в объектно-ориентированную необходимым является знание внешних и возможных ключей отношений ([12]). В отличие от например [3], в работе используется определение внешних ключей, которые указывают не только на первичный ключ отношения, но и на любой возможный ключ ([2]).

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

Отношения можно непосредственно отображать в классы (см. [21]) но при этом теряется семантика реляционной базы данных. Целью описанного алгоритма является получение из реляционной схемы тех объектно-ориентированных концептов, которые адекватны действительной семантике базы данных (в отличие от [28, 31] где полученная объектно-ориентированная схема является почти реляционной). Алгоритм автоматически, т.е. без помощи пользователя, (в отличие от, например, [20, 30]) анализирует семантику схемы реляционной базы данных и трансформирует ее в объектно-ориентированную.

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

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

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

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

Этими случаями покрывается использование возможных и внешних ключей отношений реляционной базы данных. Случай 3 касается возможных ключей, которые одновременно являются внешними ключами, Случай 6 - возможных ключей, содержащих внешние ключи, а Случай 7 -всех остальных внешних ключей. Случай 2 рассматривает отношения с одинаковыми возможными ключами. Случаи 4 и 5 - некоторые частные случаи (внешний ключ, указывающий на то же отношение, которому этот ключ принадлежит - Случай 4, и два или более внешних ключей одного отношения, указывающих на некоторое другое отношение - Случай 5). Случай 1 иллюстрирует использование внутренней семантики данных.

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

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

Если дано отношение г со схемой R, т.е. отношение r(R), тогда класс с таким же названием, который получается из этого отношения, будем обозначать как С(г).

С начала, для каждого отношения из базы данных надо определить класс с таким же названием, который содержит все его атрибуты. Например, отношение person(name, family) при условии, что домен атрибута пате и family есть string, трансформируем в класс С (person), который определен как: class person

name : string; family : string; end;

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

В процессе трансформации реляционной схемы в объектно-ориентированную требуется удалять некоторые атрибуты из таким образом определенных классов С(г), а некоторые заменять другими атрибутами. Информация о том, какие атрибуты удаляются, а какие заменяются другими атрибутами, является необходимой для других этапов трансформации реляционной базы данных в объектно-ориентированную. Эту информацию надо сохранить в течение процесса трансформации схемы. Соответствуюп]ую информацию будем сохранять во множествах CK-Inheritance, CK-Reference, CK-Ordinary, FK-Reference, Ordinary keys и

Ordinary, Move, case_4 and case_5. Семантика этих множеств и способ сохранения информации в них будут рассмотрены при описании процесса трансформации схемы. Сначала предполагается, что все эти множества пусты.

Во всех примерах подчеркнутые атрибуты обозначают возможные ключи.

3.2 Описание процедуры трансформации схемы 3.2.1 Случай 1

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

Алгоритмы обнаружения знания (knowledge discovery) могут идентифицировать этот факт в некотором отношении в исходной базе данных ([4]). Алгоритмы чаще всего идентифицируют правила следующего вида: (D=Vj) => \\-NULL (если атрибут или множество атрибутов D принимает значение Vj, тогда атрибут или множество атрибутов Х\

принимает неопределенное значение).

Пусть дано отношение r(R). Применяя алгоритм обнаружения знания к этому отношению, получаем множество правил приведенного вида. Тем самым получим множество Р, элементы которого являются множествами Xj

атрибутов отношения г.

Цель следующего алгоритма состоит в разбиении объединения множеств Х[ и создании соответствующего класса для каждого множества в

разбиении.

Шаг 1: Пусть Р будет множеством подмножеств Xi repeat

for each Xj,Xj eP, Xj n Xj do удалить Xj и Xj из множества P

добавить во множество Р подмножества (Xj n Xj), (Xj - Xj) и

(Xj - хо

until (Xi гi Xj =0 , V Xi,Xj eP , Щ )

Шаг 2: В исходном отношении r(R) и соответствующем классе С(г) пометить для удаления атрибуты, которые содержатся во множествах Хк,

ХкеР.

Шаг 3: Для каждого Х^еР создать и вычислить новое отношение г^ со

m

схемой Xk u (JK|» где Kj, К2, Km обозначают возможные ключи

¡и

отношения г. Возможными ключами отношения г^ являются те же Kj, К2,

..., Km. Во множество Move надо включить упорядоченную тройку (А, г, г£)

для каждого атрибута А из Хк. Упорядоченная тройка (А, Г], Г2) во

множестве Move обозначает, что атрибут А, который находился в отношении/классе г^ перешел в отношение/класс г2-

Если в отношении r(R) существовал внешний ключ, который указывал на возможный ключ некоторого отношения rg, причем этот

внешний ключ являлся подмножеством множества Х^, то надо удалить этот

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

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

Отношение г^ можно вычислить с помощью (псевдо) SQL-запроса:

m

SELECT r.( Х]< u Qki ) FROM г

1=1

Шаг 4: Для каждого нового отношения г^ создать соответствующий

класс С(г^) и объявить его подклассом класса С(г). Это делается удалением

атрибутов возможных ключей из определения класса С(г£) и добавлением

упорядоченной четверки (% Kj, г, Kj) для каждого ключа Kj (j=l,...,m) во

множество СК-Inheritance. Упорядоченная четверка (t, К^, s, Ks) во

множестве CK-lnheritance означает, что класс C(t) стал подклассом класса C(s) и что это сделано с помощью возможных ключей К^ и Ks отношений t

и s, соответстве1шо.

Пример: Пусть дано отношение projectfproject number, project пате, projecttype, vendor, programminglanguage), причем атрибут vendor является внешним ключом этого отношения, указывающим на некоторый возможный ключ отношения manufacturer.

project

vroiect number, project name, project type, vendor, programming language

project hardware_project u project number projectname project type v software_project

| vendor | programming language

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Станишич, Предраг

Заключение

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

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

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

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

Построены алгоритмы трансляции реляционных SELECT-, UPDATE-, DELETE- и INSERT-запросов в соответствующие объектно-ориентированные запросы.

Построены соответствующие программы, содержащие около 8000 строк з среде программирования Delphi, и проведены компьютерные эксперименты с конверсии экспериментальных баз данных в:а ряде представительных примеров.

Содержание работы опубликовано в 5 (пяти) печатных работах ([34, 35, 36,37, 38]).

К работе приложены псевдокоды алгоритма трансформации схемы и первого алгоритма конверсии данных.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Станишич, Предраг, 1999 год

Список литературы

1. Joseph Fong, "Converting Relational to Object-Oriented Databases", SIGMOD Record, Vol.26, No. 1, March 1997

2. C.J. Date, ",\n Introduction to Database Systems ", (6th edition) Addison-Wesley Systems Programming Series, 1995

3. Shekar Ramanathan, Julia Hodges, "Extraction of Object-Oriented Structures from Existing Relational Databases", SIGMOD Record, Vol.26, No. 1, March 1997

4. Gregory Pialetsky-Shapiro, William Frawley "Knowledge Discovery in Databases ", AAAI Press / MIT Press, California, 1991

5. Weiyi Meng, Clement Yu, Won Kim, Gaoming Wang, Tracy Pham, Son Dao, "Construction of a Relational Front-end for Object-Oriented Database Systems", Proceedings of Ninth International Conference on Data Engineering, Vienna. Austria, IEEE Computer Society, 1993

6. Won Kim, "On Optimizing an SQL-like Nested Query", ACM TODS, 1982

7. Gordana Pavlovic-Lazetic, "Osnove relacionih baza podataka", Vesta-Matematicki fakultet, Beograd, 1996

8. Won Kim, "Introduction to Object Oriented Databases", The MIT Press, 1990

9. Roger H.L. Chiang, Terence M. Barron, Veda C.Storey, "Reverse Engineering of Relational Databases: Exctraction of an EER model ftom a Relational Database", Data & Knowledge Engineering, (12), 1994

10. R. Elmasri, S.B. Navathe, "Fundamentals of Database Systems", Benjamin/Cummings, 2 edition, 1994

11. Paul Johamiesson, Katalin Kalman, "A method for translating relational schemas into conceptual schemas. In Frederick H. Lochovsky, editor, Proceeedings of the Eight International Conference on Entity Relationship Approach, Toronto, Canada, October 1989

12. P. Johannesson, "A method for translating relational schemas into conceptual schemas. In 10th International Conference on Data Engineering, IEEE Computer Society, Houston, February 1994

13. Y. Breitbart, L. Tieman, "ADDS: Heterogeneous Distributed Database System". In Distributed Data Sharing Systems. F. Schreiber and W. Litwin, eds. North Holland Publishing Co., 1985

14. C-W. Chung, "DATAPLEX: An Accesss to Heterogenuos Distributed Database System". CACM; Jan. 1990

15. James Rumbaugh, Michael Blaha, William Premerlani, Frederick Eddy, and William Lorensen. Object-oriented Modelling and Design. Prentice-Hall, Inc., Eaglewood Cliffs, New Jersey, 1991

16. A. Chen, D. Brill, M. Templeton, C. Yu. "Distributed Query Processing in a Multiple Database Systems". IEEE Journal on Selected Areas in Communications, 1999

17. С.Д.Кузнецов, "Стандарты языка реляционных баз данных SQL: краткий обзор", СУБД, 2/96

18. W. Litwin, W. and A. Abdellatif, "Multidatabase Interoperability". IEEE Computer, December, 1986

19. A. Sneth, J. Larson, "Federated Database Systems for Managing Disteributed, Heterogenuos, and Autonomous Databases". ACM Computing Surveys, Vol.22, No.3, September 1990

20. Ontos Inc. Ontos object integration server. WWW Home Page, 1996. http://www.ontos.com

21. Subtle Software Inc. Subtleware С++ class generator. WWW Home Page, 1996. http://world.std.com/subtle/

22. Michael Stonebraker, "Object-Relational DBMS - the next wave", White paper, Illustra Information Technologies Inc., 1995

23. M. Templeton, et. al, "Mermaid - A Front-end to Distributed Heterogeneos Databases", Proc. IEEE, May 1987

24. E. Codd, "Extending the database relational model to capture more meaning", ACM Transactions on Database Systems, 4(4), 1979

25. E. Lien, "On the Equivalence of Database Models", JACM, v29,n2, 1982

26. E. Codd, "The Relational Model for Database Management - Version 2", Addison Wesley Publ. Inc., 1983

27. E. Codd, "A relational model of data for large shared data banks", Comm.ACM, 13(6), 1970

28. M. Castellanos, F. Saltor, "Semantich enrichment of database schemas: An object-oriented approach", In Y. Kamabyashi et al., editor, First International Workshop on Interoperability in Multidatabase Systems, 1991

29. Ian Graham. "Migrating to Object Technology", Addison-Wesley, 1995

30. J. Janke, W. Schafer, A. Zundorf. "A design environment for migrating relational to object oriented database systems", In International Conference on Software Maintenance, IEEE Computer Society, 1996

31. L. Yan, T. Ling. "Translating relational schema with constraints into OODB schema", IFIP Transactions of Interoperable Database Systems (DS-5),1993

32. J. Hughes, "Object-Oriented Databases", Prentice Hall International Series in Computer Science, 1991

33. Predrag Stanisic, "Transformacija relacionih baza podataka u objektno-orijentisane (magistarska teza)'!, Matematicki fakultet, Beograd, 1998

34. Predrag Stanisic, "Schema Transformation From Relational to Object-Oriented Database as a Part of Database Reverse Engineering Process", Mathematica Montisnigri, No. 9, 1998

35. Предраг Станишич, "Конверсия данных из реляционной в объектно-ориентированную базу данных ", Вестник Московского Университета, Серия 15, Е.ычислительная математика и кибернетика, №1, 1999 (в печати)

36. Предраг Станишич, "Метод трансляции реляционных SQL-запросов в эквивалентные запросы к трансформированной объектно-

ориентированной базе данных", Численные методы и вычислительный эксперимент, раздел "Моделирование сложных объектно-ориентированных систем", под ред. А.А. Самарского, В.И. Дмитриева, 1998 (в печати)

37. Предраг Станишич, "Трансформация реляционных баз данных в объектно-ориентированные, включая трансляцию запросов", Программирование РАН, №2, 1999 (в печати)

38. Predrag Stanisic, "Database Transformation from Relational to Object-Oriented Database and Corresponding Query Translation", Proceedings of the Workshop on Computer Science and Information Technologies CSIT'99 Moscow, Russia, 1999