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

Московский Государственный Университет им. М.В. Ломоносова Факультет Вычислительной Математики и Кибернетики

На правах рукописи

Предраг Станишич

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

( 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей )

Диссертация на соискание ученой степени кандидата физико-математических наук

г. Москва

1999

Оглавление

ВВЕДЕНИЕ.................................................................................................................1

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

1.1 ВВЕДЕНИЕ.....................................................................................................9

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

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

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

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

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

2.1 ВВЕДЕНИЕ..................................................................................................20

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

2.2.1 ОБЪЕКТ........................................................................................21

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

2.2.3 КЛАСС...........................................................................................23

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

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

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

3.1 ВВЕДЕНИЕ...................................................................................................28

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

3.2.1 СЛУЧАЙ 1.....................................................................................32

3.2.2 СЛУЧАЙ 2.....................................................................................35

3.2.3 СЛУЧАЙ 3.....................................................................................38

3.2.4 СЛУЧАЙ 4.....................................................................................40

3.2.5 СЛУЧАЙ 5.....................................................................................42

3.2.6 СЛУЧАЙ 6.....................................................................................44

3.2.7 СЛУЧАЙ 7.....................................................................................46

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

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

4.1 ВВЕДЕНИЕ...................................................................................................54

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ДАННЫХ.......................................................................................74

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

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

5.1 ВВЕДЕНИЕ...................................................................................................78

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

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

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

5.2.1.1 СЛУЧАЙ 1..............................................................................81

5.2.1.2 СЛУЧАЙ 2..............................................................................82

5.2.1.3 СЛУЧАЙ 3..............................................................................83

5.2.1.4 СЛУЧАЙ 4..............................................................................85

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

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

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

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

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

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

5.2.4.1 АЛГОРИТМ............................................................................97

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ.......................................................................................................113

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

ПРИЛОЖЕНИЕ 1....................................................................................................119

ПРИЛОЖЕНИЕ 2

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. Экземпляр всегда можно идентифицировать, так к�