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

На правах рукописи ЗАСТАВНОЙ ДМИТРИЙ АЛЕКСАНДРОВИЧ

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

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Ростов-на-Дону 2005 г.

Работа выполнена на кафедре Информатики и Вычислительного эксперимента механико-математического факультета Ростовского Государственного Университета

Научный руководитель: кандидат технических наук,

Букатов Александр Алексеевич

Официальные оппоненты: доктор технических наук

Аграновский Александр Владимирович

кандидат технических наук Крицкий Сергей Петрович

Ведущая организация: Специальная астрофизическая

Обсерватория РАН

Защита диссертации состоится «24» ноября 2005 г. в 11 часов на заседании диссертационного совета К212.208.04 по физико-математическим и техническим наукам Ростовского государственного университета по адресу 344090, г. Ростов-на-Дону, пр. Стачки 200/1, корп.2, ЮГИНФО РГУ, аудитория 206.

С диссертацией можно ознакомиться в Зональной научной библиотеке РГУ по адресу г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан « 7и » 2005 г.

Ученый секретарь

диссертационного совета К212.208.04 кандидат физико-математических наук,

доцент Муратова Г.В.

2оо6-4

3

ПЪъЗ

I 1 У -'"як

<s -'тСктуальность исследований. Одной из основных важнейших компонент современных информационных систем являются базы данных (БД), что обуславливает постоянное внимание к таким важнейшим аспектам, как проектирование БД, развитие, совершенствование и повышение выразительности средств доступа к данным.

Основой современных методов проектирования БД является ER-диаграммы (ERD) различных нотаций. Эти диаграммы позволяют описывать структуру моделируемой предметной области, используя концепции связей между сущностями, и подобный подход является наиболее естественным для описания структурных аспектов данных. К 90-м годам технологии проектирования БД на основе ERD стали доминирующими и, более того, стали основной и неотъемлемой частью практической разработки БД, были стандартизированы, и в настоящее время поддерживаются многочисленными инструментальными средствами проектирования БД (Oracle Designer, ErWin и т.д.). Дальнейшее развитие эти методологии получили в современной технологии объектно-ориентированного анализа и проектирования, где функции ER-диаграмм выполняют диаграммы классов.

Вместе с тем, роль ER-диаграмм, точнее говоря, описание данных в терминах сущностей и связей, ограничивается стадией проектирования схемы БД. Это обуславливается тем фактом, что в языке SQL, являющимся базовым средством описания данных и доступа к ним в современных БД, концепция связи между объектами (сущностями) не поддерживается. Данный факт не препятствует проектированию схемы при помощи ER-диаграмм, поскольку существует и практически реализованы эффективные средства генерации по диаграммам физической схемы БД, где связи и их характеристики достаточно полно моделируются средствами SQL. Но для доступа к данным используются базовые средства SQL вне всякой связи с исходными ER-диаграммами. Эти средства доступа, как уже говорилось, понятие связи между объектами не поддерживают, что приводит к потере выразительности и естественности выражений запросов. Это позволяет говорить о разрыве между высокоуровневыми средствами проектирования БД и низкоуровневыми средствами доступа к данным.

Следует отметить, что появление концепции ER-моделирования явились началом периода обширнейших исследований в технологии баз данных, во второй половине 80-х годов слившимися с технологией БД на основе объектного подхода, который фактически унаследовал структурную основу представления данных по принципу сущность-связь. Однако разработка высокоуровневых языков запросов к таким БД фактически не привела к появлению оригинальных результатов. Оба основных современных направления - объектно-ориентированные БД (семейство стандартов ODMG) и объектно-реляционные системы (напр. Oracle8) в качестве языка запросов предлагают расширения языка SQL. Конечно, эти расширения SQL, в особенности язык OQL стандарта ODMG, существенно обогащают средства доступа к данным, в том числе

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

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

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

при помощи высокоуровневого языка запросов, и манипулирования результатами запросов к БД на единой основе концепции связи.

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

1. Проектирование схемы БД.

2. Формулировка высокоуровневого запроса к БД.

3. Манипулирование результатами запроса.

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

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

1. Разработаны объектная модель данных, высокоуровневый язык запросов к объектной БД (ОБД), язык манипулирования объектами и язык доступа к значениям запросов на основе единой концепции навигационных путей в ОБД.

2. Разработаны и исследованы методы реализации системы ОБД, которые основаны на трансляции языковых конструкций разработанного языка в команды языка SQL.

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

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

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

Апробация. Основные материалы по теме диссертационной работы представлялись на следующих конференциях и семинарах: Третья всероссийская научная конференция студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления", Таганрог, 1996; Всероссийского симпозиума "Математическое моделирование и информационные технологии", Кисловодск, 1997; Первого Восточно-европейского симпозиума "Advances in Databases and Information Systems", Санкт-Петербург, 1997; Всероссийских конференциях "Компьютерные технологии в инженерной и управленческой деятельности", Таганрог, 1997, 1999, 2000 и 2001 г.г.; Международной конференции "2nd Join Conference on Knowledge-Based Software Engineering", Словакия; Международной конференции "Computer Science and Information Technologies", Москва, 1999; Международной конференции "3rd Join Conference on Knowledge-Based Software Engineering", Прага, Чехия, 2000; Пятой научно-практической конференции "Искусственный интеллект-2004", Крым, Украина; научных семинарах ЮГИНФО (ВЦ) РГУ.

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

удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» НОП Минобразования РФ «Научное, научно-методическое, материально-техническое обеспечение развития технологий информационного общества и индустрии образования» (2003 год) и использованы при разработке системы ГИС "Горгаз-Ростов" (свид. Госпатента № 2003610160) и БД астрофизических объектов, разработанной в Специальной Астрофизической Обсерватории РАН.

Публикации. Результаты диссертации опубликованы в 11 печатных работах, включая 1 статью в журнале, рекомендованном ВАК РФ для публикации результатов докторских диссертаций и 2 статьи в рецензируемых зарубежных изданиях.

Структура диссертации. Диссертационная работа включает Введение, 4 Главы, Заключение, Список использованной литературы из 110 наименования и Приложения. Объем основного текста диссертации составляет 147 стр.

Содержание работы

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

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

1. Модель данных, позволяющая представлять информацию в БД в виде совокупности взаимосвязанных объектов.

2. Язык запросов к БД объектной модели.

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

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

Раздел 4 посвящен рассмотрению наиболее интересных теоретических исследований в области разработки языковых средств доступа к ОБД, к которым относятся:

1. Языки запросов, относящихся к собственно ER-модели.

2. Nested-relational - модель.

3. Объектно-реляционная модель.

4. "Классические" объектно-ориентированные БД.

5. Графовая модель ("Graph-based model").

Разделы 5 и 6 посвящены анализу систем и стандартов объектного подхода. В качестве примера выбрана система Огас!е8, иллюстрирующая ) объектно-реляционный подход. Кроме того, сделан обзор средств

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

доступа к объектам БД.

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

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

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

(DEPARTMENT, STAFF и PROJECTS) и двух связей, I изображенную на Рис. 1.

Рис.1. ER диаграмма схемы БД

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

g

( Desienneni ) ( CodeDent )

employs \ employs

involvedin

involvedin

WebStore

J ^ BankinaSystem J

Рис. 2. Экстенсиональная диаграмма БД

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

<DEPARTS/ProjDept employs STAFF/Smith involvedin PROJECTS/WebStore > <DEPARTS/CodeDept employs STAFF/Jones involvedin PROJECTS/WebStore > <DEPARTS/CodeDept employs STAFF/Jones involvedin PROJECTS/BankingSys> <DEPARTS/TestDept employs STAFF/Alison involvedin PROJECTS/BankingSys >

Учитывая, что все рассматриваемые здесь пути обладают одинаковой длиной и структурой, неформально задаваемой именами типов объектов и именами связей, данные пути могут быть записаны в эквивалентном виде, представленном в Таб.1.:

Таблица 1.

Табличное представление навигационных путей

DEPARTMENTS employs STAFF involvedin PROJECTS

DesignDept Smith WebStore

CodeDept Jones WebStore

CodeDept Jones BankingSystem

TestDept Alison BankingSystem

Введение понятия элементарных путей как основного способа идентификации объектов в ОБД обусловлено следующими факторами:

1. Понятие пути естественным образом отражает структуру БД, построенной на основе ЕЯ-методологии.

2. Любую (при некоторых естественных допущениях) множество однотипных композиционных структур можно представить в виде множества элементарных путей одинаковой длины и структуры.

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

> предложенного языка запросов, и аналогичное выражение SQL:

DEPARTMENTS employs STAFF involvedin PROJECTS

>

SELECT <список полей>

FROM DEPARTMENTS, STAFF, PROJECTS WHERE DEPARTMENTS.ID = STAFF.EMPLOYSJD AND STAFF.ID = PROJECTS.INVOLVEDINJD

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

Данное свойство позволяет определить предложенный язык запросов как язык, основанный на высокоуровневой навигации.

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

1. Список супертипов данного типа;

2. Список определений атрибутов объектов;

3. Список определений связей;

► 4. Список шаблонов коллекций.

5. Список индексов.

Определение связи включает имя связи, тип объектов, с которыми

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

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

Экземпляры статической связи создаются и удаляются явным образом при помощи соответствующих команд. Существование экземпляров вычислимой (или условной ) связи проверяется динамически

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

Для связей также при их определении задается кардинальность и ограничения референциальной целостности.

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

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

В качестве примера приведем (упрощенное) определение типа STAFF, используемый в приведенном выше примере:

create type STAFF

supertypes PEOPLES; attributes age number(6);

salary number(6);

position char (10); collections Aged( %1) { age > %1}; relationships Involved in static PROJECTS;

Wasinvolved conditional CLOSEDPROJECTS {target.stuffjd = id };

end;

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

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

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

Выражение запроса определяет: 4

- объекты первого уровня пути (начальные объекты путей);

- структуру путей, задаваемую последовательным списком имен

связей, образующих пути;

- условия на объекты путей;

- список атрибутов и производных от них выражений для объектов

каждого уровня.

Выражение запроса имеет следующую структуру:

звеноI. звено 2.....звено ,у

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

Значением выражения запроса является множество элементарных путей, существующих в ОБД и соответствующих структуре и условиям » выражения запроса. Операции, используемые в выражениях запросов,

приведены в Табл. 2.

Таблица 2.

Операции в выражениях запросов_

Обозначение Семантика

Вычисление значений связей (навигация)

; Получение значений атрибутов объектов

/ Селекция множеств объектов по именам объектов

- Вычисление коллекций

Спецификация имени типа

Рассмотрим пример запроса:

DEPARTMENTS/design-.name.

Employers-Aged(50): (name, salary, 60-age).

Involved: (name, deadline)

Запрос в данном примере находит имена, зарплату и время до выхода до пенсии сотрудников отдела design, возраст которых превышает 50 лет, и название и срок окончания проектов, в которых они задействованы. Формально, значение этого запроса - множество, состоящее из 4 путей, каждый из которых имеет 3 уровня (см. ниже) и содержит значения атрибутов объектов в соответствии с текстом запроса.

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

Каждое звено текста запроса соответствует уровню путей - значений запросов. Уровень - это множество объектов, соответствующих данному I звену. Текст приведенного выше запроса состоит из трех звеньев и

соответственно порождает три уровня.

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

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

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

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

РМУ представляются в системе в виде так называемых контекстов, с каждым из которых связывается имя. После вычисления запроса образуется стек контекстов, представляющий значение этого запроса. На Рис. 3. приводится структура стека контекстов для запроса из примера.

Рис. 3. Структура стека контекстов

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

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

1. Перемещение между контекстами, ассоциированными РМУ.

2. Получение информации о конкретном контексте и структуре данных РМУ.

3. Позиционирование текущего элемента в РМУ.

4. Выборка данных текущего элемента.

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

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

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

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

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

FOR $cxl

FOR $cxt%RIGHT left

FOR $cxt%RIGHT%RIGHT left

echo $cxt%l, $xt%RIGHT%l, $cxt%RIGHT%RIGHT%l

END

END

END

Здесь РМУ курсора с именем $cxt, в котором хранится РМУ для объектов из первого уровня, открывается в обычном (независимом) режиме, при котором доступны все хранящиеся в нем объекты. РМУ последующих контекстов, на имена которых ссылаются при помощи переменных контекста $cxt%R!GHT и $cxt%RIGHT%RIGHT, открываются в режиме согласования (подчиненном режиме) с их предыдущими контекстами. Для доступа к значениям текущих элементов используется номер поля, в данном случае 1.

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

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

t

CREA ТЕ CONTEXT $cxt;

$cxt;

QUERY STAFF. Involved id; EXEC STACK; SHOW CONTEXT ALL; GOTOBOTTOM;

— создание нового контекста

— установление его текущим

— ввод текста запроса

— исполнение

— выдача статистики о стеке

— установление текущим

— верхнего в стеке контекста

В Главе 3 описаны архитектура и методы реализации системы объектных баз данных. В разделе 1 рассматриваются общие вопросы реализации, и представляется архитектура реализованной системы и краткое определение функций ее основных компонент.

Система реализована в виде интерактивного интерпретатора команд разработанного языка. Данный интерпретатор является оконным приложением, написанном на языке Си в среде Win32 и Oracle Server 7.3 с использованием интерфейса OCI.

В основу реализации системы ОБД положено использование SQL БД в качестве низкоуровневого репозитория для представления в нем следующих данных:

1. Представление объектов и экземпляров статических связей

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

Архитектурно интерпретатор состоит из следующих основных компонент:

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

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

- модуль, выполняющий исполнение откомпилированных команд языка;

- менеджер кеша и контекстов;

интрпппйтптпп

О

коианды

А

обработчик входного потока

менеджер схемы

исполнитечь запросов

менеджер контекстов

пользователь

данные экземпляров объектов и связей

SOL сервер ———————— N

результирующие множества

ч..........'

Рис. 4. Архитектура системы

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

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

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

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

Ниже приведен сокращенный список SQL-команд, генерируемых при создании SQL-представления для типа STAFF:

CREATE TABLE STAFF STRUCT(

ID INTEGER CONSTRAINT STAFF_NN NOT NULL, age number(6), salary number(6), position char(IO)) ALTER TABLE STAFFJTRUCT

ADD CONSTRAINT STAFFPK PRIMARY KEY (ID) CREATE TABLE STAFF InvolvedJn (

ID1 INTEGER CONSTRAINT STAFFJnvolvedJn_NNl NOT NULL, ID2 INTEGER CONSTRAINT STAFFJnvolvedJn_NN2 NOT NULL ) ALTER TABLE STAFF JTRUCT

ADD CONSTRAINT STAFF_PEOPLES_SFK FOREIGN KEY (ID) REFERENCES PEOPLES JSTR UCT ON DELETE CASCADE ALTER TABLE STAFF Involved in

ADD CONSTRAINT STAFF InvolvedJn LFKI FOREIGN KEY (ID!) REFERENCES STAFF STRUCT ON DELETE CASCADE ALTER TABLE STAFFInvolved Jn

ADD CONSTRAINT STAFF JnvolvedJn_LFK2 FOREIGN KEY (ID2) REFERENCES PROJECTS STRUCT ON DELETE CASCADE ALTER TABLE STAFF Involved Jn

ADD CONSTRAINT STAFFJnvolvedJnPK PRIMARY KEY (ID 1.1D2)

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

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

1. Проверка семантического соответствия аргументов в выражении запроса.

2. Инициализация структур кеша.

3. Генерация SQL-предложений, реализующих семантику операций выражений запросов.

4. Исполнение SQL-предложений и помещение данных в кеш. Первая стадия исполнения запроса имеет своей целью связывание

имен, используемых в выражении запроса, с именами, определенными в схеме, разрешение типов полиморфных элементов, проверка других

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

- имя типа объектов звена;

- список супертипов, в которых определены атрибуты, связи и коллекции, использованные в выражении звена;

- список имен объектов, специфицированных в звене;

- список имен атрибутов и производных от них выражений;

- логические выражения для условных связей и коллекций; Далее, на второй стадии, происходит генерация новых контекстов,

требующихся для хранения РМУ; при этом ранее существующие контексты стека удаляются, а ассоциированные с ними РМУ освобождаются. Так же выполняется требуемая инициализация параметров контекстов.

На третьей стадии происходит генерация и исполнение SQL-запросов и заполнение объектами РМУ. Ниже приводится текст запроса и соответствующий SQL-текст, генерируемый для запроса:

DEPARTMENT/designname Employers:(firstname,lastname,salary age-60)

CREATE TABLE RS_cxtJAS

SELECTB.1D ASID, B.NAME FROMDEPARTMENTSJTRUCTВ WHERE B.NAME IN ('design')

CREATE TABLERS_cxt_I AS

SELECT C.ID1 AS IDL, C.ID2 AS ID, Bl.flrstname AS FLDO,

Bl. Шпате AS FLDI,B.salary AS FLD2, 60-B.age AS FLD3 FROM RS_cxt_0 A, STAFF JTRUCT В, DEPARTMENTS_Employers С,

PEOPLES_STRUCT Bl WHERE A.ID = C.ID1 AND C.ID2 = B.1D AND Вl.ID = B.1D

Из приведенного примера видно, что генерация SQL-запросов сводится к формированию:

1. списка таблиц, содержащего: (1) имя таблицы, представляющим РМУ предыдущего уровня; (2) имя таблицы, содержащей представление объектов текущего звена; при необходимости - (3) имена таблиц с представлением объектов супертипов; и (4) имя таблицы, в которой содержится информация об экземплярах статической связи;

2. списка имен выбираемых из таблиц полей и производных от них выражений;

3. условий, куда входят (1) условия селекции по именам объектов, (2) условия для коллекций и условных связей, и (3) эквисоединениями соответствующих таблиц.

Подробное описание правил генерации SQL-запросов приведено в тексте диссертации.

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

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

Открытие РМУ в независимом режиме реализуется при помощи генерации и исполнения SQL-запроса, извлекающего все записи из таблицы, представляющей РМУ. Далее выборка доступна как обычный курсор, в котором осуществляется позиционирование текущей записи и доступ к значениям ее полей. Соответствующие операции реализованы как обращение к базовым функциям интерфейса OCI.

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

Глава 4 посвящена практическому применению разработанной технологии для организации внутреннего представления в базе данных текстов программных модулей и выполнения некоторых запросов, извлекающих из БД фрагменты представления. Хранение текстов программ в БД является задачей, типичной для современных CASE-систем. Важной особенностью является необходимость представления программных модулей в БД в виде синтаксических компонент (операторов, выражений, etc.), связанных между собой различными связями. Эти связи традиционно разделяются на структурные, выражающие вхождение одних программных конструкций в другие, и семантические, выражающие различные прочие отношения между компонентами программы.

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

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

2. Построение метода представления программных модулей в ОБД в соответствии с разработанной схемой.

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

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

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

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

Вхождение одних программных конструкций в другие реализуется при помощи связей. Например, тип 1F, представляющий условные операторы, имеет три связи: связь condition с типом EXPRESSION, и две связи с именами then и else с типом INCLOSED. Примером неструктурной связи является связь между определяющим вхождением переменной и ее вхождением в выражения. Для этой цели в типе VARVALUE определена связь variable с типом VARIABLE.

На рис. 4 приведена ER-диаграмма, изображающая схему ОБД.

Рис 4. ER-диаграмма внутреннего представления в ОБД исходных текстов

программ

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

Раздел 4.4 содержит примеры запросов к ОБД, иллюстрирующих идентификацию программных компонент в БД по следующим видам поиска:

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

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

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

- по имени конструкции, включая искусственно созданные имена;

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

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

Ниже приведено несколько примеров запросов.

1. Функции и всходящие в них параметры

FUNCTION. Includes~ VARIABLE

2. Все входящие в заданную функцию описания локальных переменных (не массивов)

FUNCTION/"Fun".Includes-SINGLE

3. Все входящие в заданную функцию вложенные конструкции

FUNCTION/"Fun ".Includes

4. Операторы присваивания, вложенные в циклы, в левой части которых находятся заданная локальная переменная

FUNCTION Includes~ASSIGH. Left/"x "-LocalQ

5. Выражения типа "... = а[... ] + ... " любого уровня вложенности

ASSIGH.Right-Kind( "+ ").Left. Variable/"a"

6. Выражения типа "... = а[... ] + ..." вложенные в заданный цикл заданной функции

FUNCTION/"Fun ". Includes/" ForO ". Includes-ASSIGH. Right-Kind( "+ ").Left. Variable/"a"

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

В Приложениях приводятся краткое описание команд интерпретатора и акты внедрения.

Результаты, представляемые к защите

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

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

3. Язык покомпонентного доступа к значениям запросов к ОБД, ориентированный на последовательный покомпонентный доступ к этим значениям из сред включающих языков.

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

5. Экспериментальная реализация репозитория макетной САБЕ-системы на основе разработанной ОБД, предназначенного для хранения внутреннего представления исходных текстов программ.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО МАТЕРИАЛАМ ДИССЕРТЦИИ

1. Заставной Д.А. Высокоуровневый язык запросов для объектно-ориентированных баз данных. //Третья всероссийская научной конференция студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления", 10-11 окт. 1996 г., Таганрог: Сб. материалов. -Таганрог, 1996. - С.86-87.

2. Букатов А.А., Заставной Д.А. Организация объектно-ориентированной СУБД инструментальной системы поддержки программирования суперкомпьютера nCube //Всероссийский симпозиум "Математическое моделирование и информационные технологии", 24-26 сент. 1997 г., Кисловодск: Сб. материалов, - Кисловодск., 1997. - С. 57-59.

3. Заставной Д.А.. Развитие концепции полиморфизма в высокоуровневом языке запросов для объектных баз данных. // Всероссийская конференция "Компьютерные технологии в инженерной и управленческой деятельности", 21-23 окт. 1997 г., Таганрог: Сб. материалов. - Таганрог, 1997. - С. 198-201.

4. Zastavnoy D.A. High-level Declarative Language for Object-Oriented Databases. // First East-European Symposium on Advances in Databases and Information Systems, Sept. 2-5, 1997, St.Petersburg, - St.Petersburg, 1997. - P.26-28.

5. Bukatov A.A, Zastavnoy D.A. High-level Navigational Language for Querying Complex Data Objects and its Application to CASE Systems. //Frontiers in Artificial Intelligence and Applications. - Amsterdam. IOS Press. 1998.-P. 103-107.

6. Букатов A.A., Заставной Д.А.. Спецификация и представление сложных навигационных запросов для объектных баз данных. // Всероссийская конференция "Компьютерные технологии в инженерной и управленческой деятельности", 19-21 мая 1999 г., Таганрог: Сб. материалов. -Таганрог, 1999, - С. 295-301.

7. Zastavnoy D.A.. Bukatov A.A. Representation of Complex Structures Extracted from Object Databases, and Access to their Components. //Frontiers in Artificial Intelligence and Applications. - Amsterdam. IOS Press, 2000, - P. 93-100.

8. Заставной Д.А. Реализация навигационного языка запросов для объектных баз данных на основе SQL-сервера Oracle. // Всероссийская конференция "Компьютерные технологии в инженерной и управленческой деятельности", 26-28 мая 2001 г., Таганрог: Сб. материалов, - Таганрог, 2001, - С. 178-184.

9. Заставной Д.А. Язык запросов для специфицирования сложных ассоциативных структур в объектных баз данных // Известия вузов Северо-Кавказского региона. Технические науки. - 2001, № 3, -С.8-13.

10. Заставной Д.А. Применение концепции навигационных п>тей для построения навигационного языка запросов для объектных баз данных. //Международная научно-техническая конференция "Искуса венный интеллект". 20-25 септ. 2004 г., Таганрог: Сб. материалов. - Таганрог, 2004. - С.236-241

11. Заставной Д.А. Построение высокоуровневого языка запросов баз данных на основе концепции навигационных путей. //Искусственный интеллект, - 2004. - № 4, - С.328- 338.

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

Автор выражает глубокую признательность научному руководителю Букатову АлександруАлексевичу за многолетнюю помощь и поддержку.

Печать цифровая Бумага офсетная. Гарнитура «Тайме» Формат 60x84/16. Объем 1,0 уч.-изд.-л. Заказ №699. Тираж 100 экз. Отпечатано в КМЦ «КОПИЦЕНТР» 344006, г. Ростов-на-Дону, ул. Суворова, 19, тел. 247-34-88

РНБ Русский фонд

2006-4 17339

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ИССЛЕДОВАНИЙ В ОБЛАСТИ ЯЗЫКОВ ЗАПРОСОВ ДЛЯ ОБЪЕКТНЫХ БАЗ ДАННЫХ.

1.1. Цели главы.

1.2. Исторический аспект развития концепции объектных баз данных.

1.3. Общие характеристики языков запросов для объектных баз данных.

1.4. Обзор исследований навигационных языков запросов.

1.4.1. Языки для ER-модели.

1.4.2. Расширенная реляционной модели (nested-relation, composite objects).

1.4.3. Графовые модели.

1.4.4. Навигационные языки.

1.4.5. " Классические" объектно-ориентированные системы.

1.5. Объектно-реляционные системы.

1.6. Обзор стандартов ODMG.

1.7. Результаты анализа.

ГЛАВА 2. СОЗДАНИЕ ВЫСОКОУРОВНЕВОГО НАВИГАЦИОННОГО ЯЗЫКА ЗАПРОСОВ ДЛЯ ОБЪЕКТНЫХ БАЗ ДАННЫХ.

2.1. Концептуальное обоснование применения высокоуровневой нотации связи для построения языков запросов к объектным БД.

2.1.1. Применение понятия связи в базах данных.

2.1.2. Построение запросов в терминах навигационных путей.

2.1.3. Передача множества путей в приложение.

2.2. Язык объектной базы данных.

2.2.1. Объектная модель данных.

2.2.2. Создание экземпляров объектов и связей.

2.2.3. Управление контекстами.

2.2.4. Запросы.

2.2.5. Средства вторичной навигации.

2.3. Методология использования языка запросов.

2.3.1. Создание схемы.

2.3.2. Исполнение запросов.

2.3.3. Доступ к данным из результирующих множеств.

2.4. Выводы по главе 2.

ГЛАВА 3. РЕАЛИЗАЦИЯ ЯЗЫКА ОБЪЕКТНЫХ БАЗ ДАННЫХ.

3.1. Архитектура системы.

3.1.1. Общие вопросы.

3.1.2. Обработчик входного потока.

3.1.3. Реализация представления схемы.

3.2. Реализация представления объектов и экземпляров связей.

3.3. Исполнение запросов.

3.3.1. Анализ выражения запроса.

3.3.2. Генерация SQL-предложений.

3.3.3. Исполнение SQL-предложений.

3.4. Реализация кеша и средств вторичной навигации.

3.5. Выводы по Главе 3.

ГЛАВА 4. ПРИМЕНЕНИЕ ОБД ДЛЯ ПРЕДСТАВЛЕНИЯ В БАЗЕ ДАНЫХ ИСХОДНЫХ ТЕКСТОВ ПРОГРАММ.

4.1. Представление исходных текстов программ в БД.

4.2. Проектирование схемы репозитория.

4.3. Генерация внутреннего представления исходных текстов в ОБД.

4.4. Поиск в БД компонент представления программных текстов.

4.5. Выводы по Главе 4.

Актуальность исследований

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

Основой современных методов проектирования баз данных является ER-диаграммы (ERD) различных нотаций [27,30,38,42,45,96]. Эти диаграммы позволяют описывать структуру моделируемой предметной области, используя концепции связей между сущностями, и подобный подход является наиболее естественным для описания структурных аспектов данных. К 90-м и годам технологии проектирования баз данных на основе ERD стали доминирующими и, более того, стали основной и неотъемлемой частью практической разработки баз данных, были стандартизированы, и в настоящее время поддерживаются многочисленными инструментальными средствами проектирования БД (Oracle Designer, ErWin. и т.д.). Дальнейшее развитие эти методологии получили в современной технологии объектно-ориентированного анализа и проектирования, где функции ER-диаграмм выполняют диаграммы классов.

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

Следует отметить, что появление ER-моделирования исторически явились по существу началом периода обширнейших исследований в технологии баз данных, во второй половине 80-х годов слившимися с технологией баз данных на основе объектного подхода, который фактически унаследовал структурную основу представления данных по принципу сущность-связь. Однако разработка языков запросов к таким базам данных фактически не привела к созданию каких-либо оригинальных высокоуровневых языков. Оба основных современных направления -объектно-ориентированные базы данных (семейство стандартов ODMG) [14,74] и объектно-реляционные системы (напр. Огас1е8) [96] в качестве языка запросов предлагают расширения языка SQL. Конечно, эти расширения SQL, в особенности язык OQL стандарта ODMG, существенно обогащают средства доступа к данным, в том числе средствами высокоуровневой навигации, но при этом сохраняется семантическая основа SQL, который ориентирован на работу с так называемыми "плоскими" множествами. Результат запроса представляется так же в виде "плоского" множества.

Другой важный аспект связан с взаимодействием между выражениями языка запросов и средствами включающего языка (языка разработки приложений), используемого для создания приложений. Давно было замечено и осознано, что современные языки программирования по своим функциональным возможностям сильно отличны как от языка запросов SQL, так и от каких-либо средств ER-моделирования. Более того, как показала практика и опыт многолетних исследований, надежды на возможность создания единой среды программирования, объединяющей и высокоуровневый язык запросов, и возможности процедурных языков, являются нереальными. Это порождает необходимость разработки приемлемых интерфейсов между двумя вычислительными средами, и в случае с SQL, такие интерфейсы были реализованы (на основе механизмов курсоров) и успешно применяются в настоящее время. Аналогичные средства используются и для доступа к значениям запросов в среде OQL, которые дополняются специфическими интерфейсами, классифицируемыми как низкоуровневые средства покомпонентной навигации по связям [48].

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

Цель и задачи исследований

Целью данной диссертационной работы является выработка единого подхода к построению и использованию баз данных, соответственно реализуемого на трех уровнях работы с БД:

1. Проектирование схемы БД.

2. Формулировка высокоуровневого запроса к БД.

3. Манипулирование результатами запроса.

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

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

Научная новизна

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

1. Разработаны объектная модель данных, высокоуровневый язык запросов к объектной БД (ОБД), язык манипулирования объектами и язык доступа к значениям запросов на основе единой концепции навигационных путей в ОБД.

2. Разработаны и исследованы методы реализации системы ОБД, которые основаны на трансляции языковых конструкций разработанного языка в команды языка SQL.

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

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

Результаты, представляемые к защите

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

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

3. Язык покомпонентного доступа к значениям запросов к ОБД, ориентированный на последовательный покомпонентный доступ к этим значениям из сред включающих языков.

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

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

Апробация

Основные материалы по теме диссертационной работы представлялись на следующих конференциях и семинарах: Третья всероссийская научная конференция студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления", Таганрог, 1996; Всероссийского симпозиума "Математическое моделирование и информационные технологии", Кисловодск, 1997; Первого Восточно-европейского симпозиума "Advances in Databases and Information Systems", Санкт-Петербург, 1997; Всероссийских конференциях "Компьютерные технологии в инженерной и управленческой деятельности", Таганрог, 1997, 1999, 2000 и 2001 г.г.; n j

Международной конференции "2 Join Conference on Knowledge-Based Software Engineering", Словакия; Международной конференции "Computer Science and Information Technologies", Москва, 1999; Международной конференции "3rd Join Conference on Knowledge-Based Software Engineering", Прага, Чехия, 2000; Пятой научно-практической конференции "Искусственный интеллект-2004", Крым, Украина; научных семинарах ЮгИнфо (ВЦ) РГУ.

Реализация и внедрение результатов работы

Результаты диссертационной работы были использованы в отчетах по проекту 1.7.43 «Разработка методов, технологии и специальных программных средств удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» НОП Минобразования РФ «Научное, научно-методическое, материально-техническое обеспечение развития технологий информационного общества и индустрии образования» (2003 год) и использованы при разработке системы ГИС "Горгаз-Ростов" (свид. Госпатента № 2003610160) и БД астрофизических объектов, разработанной в Специальной Астрофизической Обсерватории РАН.

Публикации

Результаты диссертации опубликованы в И печатных работах, включая 1 статью в журнале, рекомендованном ВАК РФ для публикации результатов докторских диссертаций и 2 статьи в зарубежных изданиях.

Структура диссертации

Представляемая к защите диссертационная работа включает Введение, 4 Главы, Заключение, Список использованной литературы из 110 наименования и Приложения. Объем основного текста диссертации составляет 147 стр.

4.5. Выводы по Главе 4

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

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

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

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

Полученные результаты подтверждают эффективность предложенного подхода.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Язык покомпонентного доступа к значениям запросов к ОБД, ориентированный на последовательный покомпонентный доступ к этим значениям из сред включающих языков.

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

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

1. Агафонов В.И. Язык запросов для концептуальных моделей и языков спецификаций типа "объект-связь". //Программирование. 1996, - N5, стр.30-40.

2. Аткинсон М., Бансилон Ф., ДеВитт Д., Диттрих К., Майер Д., Здоник С. Манифест систем объектно-ориентированных баз данных. //СУБД, 1995, -N4, стр.142-155.

3. Атре III. Структурный подход к организации баз данных. М. ФиС. 1983. 256 с.

4. Браун П. Реализаций идей SQL-99. // Открытые системы, 1999, N1., стр 34-38 .

5. Букатов А.А. Разработка средств построения систем преобразования исходных текстов программ //Информационные технологии, 1999, 2, стр.22.25.

6. Буч Г., Рамбо Дж., Джекобсон А. Язык UML: руководство пользователя. М. ДНК. 2001.412 с.

7. В. Кришнамурти, С. Бенерджи, А. Нори. Объектно-реляционная технология стала магистральным направлением. //Открытые системы,1999, N1. стр. 38-42.

8. Вейд А. Стандарты объектных запросов. Открытые системы, N4, 1994. стр. 29-33.

9. Вон Ким. Технология объектно-ориентированных баз данных. //Открытые системы, 1994, -N4(8), стр. 30-42.

10. Дарвин X., Дэйт К. Третий манифест .СУБД, 1996, N1. стр. 56-62.

11. Дейт К.Дж. Введение в системы баз данных, 6-е издание. С-Пб. Вильяме.2000.

12. Джордан Д. Обаботка объектных бах данных в С++. Программирование с использованием стандарта ODMG. С-Пб.: Вильяме. 2001. 384 с.

13. Замулин А.В. Системы программирования баз данных и знаний. Новосибирск. Наука. 1990. 352 с.

14. Замулин А.В. Перспективы развития систем баз данных третьего поколения. // Программирование, 1992, -N2, стр.33-46.

15. Заставной Д.А. Язык запросов для специфицирования сложных ассоциативных структур в объектных баз данных.// Известия вузов Северо-Кавказского региона. Технические науки. 2001. -N3. стр. 8-13.

16. Заставной Д.А. Применение концепции навигационных путей для построения навигационного языка запросов для объектных баз данных.//Материалы конференции "Искусственный интеллект". Таганрог, изд. ТРТУ, 2004 г. с.236-241,

17. Заставной Д.А. Построение высокоуровневого языка запросов баз данных на основе концепции навигационных путей. //Искусственный интеллект, журнал Академии наук Украины, № 4, изд. «Наука i освгга», 2004 г. С.328- 338.

18. Зиндер Е.З. Проектирование баз данных: новые требования, новые подходы. СУБД, 1996, -N3, стр. 10-22.

19. Калиниченко JI.A. Стандарт систем управления объектными базами данных ODMG-93: краткий обзор и оценка состояния. СУБД, N1, 1996. стр. 6-16.

20. Ким Вон, Гарза Жорж Ф., Грэхэм Брюс. Пути развития объектно-реляционных технологий баз данных. Открытые системы, 4, 1996. стр. 4349.

21. Кодд Э.Ф. Расширение реляционной модели для лучшего отражения семантики. //СУБД, 1996. -N1. стр.163-192.

22. Конолли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Изд. Вильяме. Москва. 2000. 1120 с.

23. Кузнецов С.Д. Об основах ненавигационного языка запросов к объектно-ориентированным базам данных. //Программирование, 1995, -N2, стр. 2130.

24. Кэри М. Что происходит с DB2. //Открытые системы. 1999, N7-8. стр. 5964.

25. Маклаков С.В. BPWin, ERWin. CASE-средства разработки информационных систем. М. Диалог-МИФИ. 2000. 256 с.

26. Мацяшек Л. Анализ требований и проектирование систем. Разработка информационных систем с использованием UML. -М. Вильяме. 2002. -432 с.

27. Олле. Язык описания данных КОДАСИЛ. -М.: Статистика, 1981. 286 с.

28. Пржиялковский В. Новые одежды знакомых СУБД: Объектная реальность, данная нам. СУБД, 4, 1997. стр. 47-52.

29. Саймон А. Стратегические технологии баз данных. М. ФиС. 1999. -479 с.

30. Стоунбрейкер М. Объектно-реляционные системы баз данных. Объектно-ориентированные базы данных сегодня или завтра? //Открытые системы, 1994, -N4(8), стр. 43-49.

31. Страуструп Б. Объектно-ориентированное программирование на языке С++. Невский диалект, 1999. 437 стр.

32. Троелсон Э. С# и платформа .NET. изд. Питер. Москва. 2002. 800 с.

33. Ульман Д., Уидом Д., Гарсия-Молина Г. Системы баз данных. Полный курс. Изд. Вильяме, Москва Санкт-Петербург - Киев, 2003. 1088 с.

34. Ульман Дж., Уидоу Дж. Введение в системы баз данных. М.2000. 382. стр.

35. Харрингтон Дж. Проектирование объектно-ориентированных баз данных. М. ДМК. 2001,272 с.

36. Цаленко М.Ш. Моделирование семантики в базах данных. М.: Наука. 1989. 288 с,

37. Циктритзис Д., Лоховски Ф. Модели данных. М.: ФиС, 1985. 344 с.

38. Цимбал А. Технология CORBA. изд. "Питер". 2001. 483 стр.

39. Чемберлин Д. Анатомия объектно-реляционных баз данных. //СУБД, N1-2,1998, стр. 22-31.

40. Чен П. Модель "сущность-связь" шаг к единому представлению о данных. СУБД, N3/95. стр. 138-158.

41. Шринивасан В., Чанг Д. Т. Долговременное хранение объектов в объектно-ориентированных приложениях. Открытые системы. 1990, 3.

42. Эйзенберг Э., Мелтон Дж. SQL1999, ранее известный как SQL3, //Открытые системы, 1999, N1. стр. 78-85.

43. Энсор Д. Oracle8: рекомендации разработчикам. Киев. BHV. 1999. 138 с.

44. Энсор Д., Стивенсон Й. Oracle. Проектирование баз данных. Киев. BHV. 1998.-560 с.

45. Abiteboul S, Beeri С: The Power of Languages for the Manipulation of Complex Values. //VLDB Journal 4,1995, pp. 727-794.

46. Abiteboul S, Kanellakis Paris C. Object Identity as a Query Language Primitive. 02 Book 1992: pp 97-127.г

47. Abiteboul S., Beeri C., van Gucht D., Gyssens M. An introduction to the completeness of languages for Complex Objects and Nested Relations, //in Lecture Notes in Computer Science, V361, Springer-Verlag, 1989.

48. Alashqur A.M., Stanley Y. W. Su, Herman Lam: OQL: A Query Language for Manipulating Object-oriented Databases. //VLDB 1989, pp. 433-442.

49. Alashqur A.M., Su S.Y.W., Lam H. Constraint Specification on Object-Oriented Databases.

50. Albano A., Cardelli L., Orsini R. Galileo: A strongly typed, interactive conceptual language. //ACM Transactions on Database Systems, 1985, 10(2), pp. 230-260.

51. Anthony C. Bloesch, Terry A. Halpin: Conceptual Queries Using ConQuer-II. ER 1997.

52. Atkinson M., Morris R. Orthogonally Persistent Object Systems. //VLDB Jornal, 1995,4, pp. 319-401.

53. Atkinson M.P., Buneman O.E Types and persistence in database programming languages. //ACM Computing Surveys, 1987,19(2), pp. 105-190.

54. Bachman С., The Programmer as Navigator, CACM, 10, 1973.

55. Bancilhon F, Cluet S, Delobel C. A Query Language for the 02 Object-Oriented Database System. //In Proc. DBPL, 1989, pp. 122-138.

56. Bancilhon F. et al. The Design and Implementation of O2, an Object-Oriented Database Systems. //In Proc. OODBS, 1988, pp 1-32.

57. Banerjee Jay, Won Kim, Kyung-Chang Kim. Queries in Object-Oriented Databases. //In Proc. ICDE 1988, pp. 31-38.

58. Baroody A., DeWitt D: An Object-Oriented Approach to Database System Implementation. //TODS, 1981, 6(4), pp. 576-601.

59. Beeri C. A formal approach to object-oriented databases. //Data & Knowledge Engineering. 1990, 5, pp. 353-382

60. Bertino Elisa, Negri Mauro, Pelagatti Giuseppe, Sbatella Licia. Object-oriented Query Languages: The Notion and the Issues. // IEEE Transaction on Knowledge and Data Engineering. Vol.4, No 3, 1992.

61. Bretl В., et al. The GemStone Data Management System. //In "Object-Oriented Concepts, Applications, and Databases", W.Kim, F.Lochovsky, eds, Addison-Wesley. 1989.

62. Butterworth P., Otis A., Stein J. The GemStone Object Database Management System. //Communications of the ACM. 1991,34, pp. 64-77.

63. Cardelli L., Wegner P. On understanding types, data abstraction and polymorphism. //ACM Computing Surveys, 1985, 17(4), pp. 471-523.

64. Carey M, DeWitt D, et al. The Architecture of the EXODUS Extensible DBMS. //On Object-Oriented Database Systems, 199, pp. 231-256.

65. Carey M, DeWitt D, Vandenberg S.A. Data Model and Query Language for EXODUS. //SIGMOD Conference, 1988, pp. 413-423.

66. Carey M., DeWitt D. Of Objects and Databases: a Decade of Turmoil. //Proc. VLBD, 1996, pp.1-11.

67. Cattel R.G.G. The Object Database Standard: ODMG 2.0. Morgan Kaufinann. 1996. 471 p.

68. Cattell R.G.G, Barry D.K. (ed) "The Object Database Standard: ODMG 2.0". Morgan Kaufinann publ. San Francisco, 1997. 387 p.

69. Copeland G., Maier D., Making Smalltalk a Database System, Proc. 1984 ACM-SIGMOD Conference on Management of Data, 1984.

70. Deux O. et al. The 02 system. //Communications of the ACM. 34, 1991, pp. 35-48.

71. Dittrich K.R., Object-Oriented Database System: The Notions and the issues, in: Dittrich, K.R. and Dayal, U. (eds) Proceedings of the 1986 International Workshop on Object-Oriented Database Systems, IEEE Computer Science Press, pp. 12-18.

72. Elmasri R., Weiderhold G. GORDAS: A Formal High-Level Query Language for the Entity-Relationship Model. //ER-Approach to Information Modeling and Analysis. 1981. pp. 49-72.

73. Fisher P., Thomas S. Operators for non-first-normal-form relations. Proc. COMPSAC, 1983.

74. Goldberg A., Robson D, Smalltalk-80: the language and its implementation, Addison-Wesley, 1983.

75. Goldstein I.P., Bobrow D.A. An experimental description-based programming environment: four reports. Xeroc PARC CSL 81-3. 1981.

76. Gyssens M., Paredaens J., D. Van Gucht. A graph-oriented object database model. //Proc. ACM Symp. on Principles of Database Systems, Nashville., 1900, pp. 417-424

77. Hull R., King R. Semantic database modeling: survey, applications, research issues. //ACM Сотр. Survey. 19,1987, pp.201-260

78. Kim Won, Ballou Nat, Chou Hong-Tsai, Jorge F. Garza, Darrell Woelk. Features of the ORION Object-Oriented Database System. //In 00 Concepts, Databases, and Applications, Addison-Wesley. 1989. pp. 251-282.

79. Kim Won, Bertino E, Garza Jorge F. Composite Objects Revisited. //SIGMOD Conference 1989, pp 337-347.

80. Kim Won. A Model of Queries for Object-Oriented Databases. //VLDB 1989, pp. 423-432.

81. Kim Won. UniSQL/X Unified Relational and Object-Oriented Database System. //SIGMOD Conference 1994, pp. 481-492

82. Lamb Ch., Landis G., Orenstein J., Weinred D. The ObjectStore Database System. //Communications of the ACM. 34, 1991, pp. 50-63.

83. Levene M., Loizou G. A graph-based data model and its ramifications. //IEEE Trans, on Knowledge and Data Engineering. 1995, vol. 7. pp. 809-823,.

84. Lohman Guy et al. Extensions to Statburst: Objects, Types, Functions, and Rules. //Communications of the ACM. 34, 1991, pp. 94-109.

85. Markovitz V., Shoshani A. Object Queries over Relational Databases: Language, Implementation, and Applications. //Proc. of International Conference on Data Engineering. 1993. pp. 71-80.

86. Morrison R., Brown A.L., Carrick R., Connor R.C.H., Dearie A., Atkinson M.P. The Napier type system. Proceedings of the Third International Workshop on Persistent Object Systems, Newcastle, Australia, 1990. pp. 145-178.

87. Motschig-Pitrik R., Kaasboll J. Part-Whole Relationship Categories and Their Application in Object-Oriented Analysis. //IEEE Transaction on Knowledge and Data Engineering. Vol 11, No 5. 1999. pp 779-797.

88. Oracle Call Interface Programmer's Guide. Release 8.1.5. Oracle Corp. 1999.

89. Oracle8i Application Developer's Guide Fundamentals. Release 8.1.5. Oracle Corp. 1999.

90. Oracle7 Server SQL Reference Manual. Oracle Corp. 1997.

91. Partch H., Steinbruggen R. Program Transformation Systems. //ACM Computing Surveys, 1983, v. 15, N 3, pp. 199-236.

92. Peter J.Barclay, Jessie B.Kennedy. A Conceptual Language for Querying Object Oriented Data. //In Proceedings on BNCOD-94. pp. 187-204.

93. Poulovassilis A., Levene M. A nested-graph model for the representation and manipulation of complex objects. //ACM Trans, on Information Systems, 1994, vol. 12, pp 35-68.

94. Richardson Joel, Carey M. Implementing Persistence in E. //In "Proc. on Persistent Object Systems", 1989, pp.175-199.

95. Roth M.A., Korth H.F., Silberschatz A. Extended algebra and calculus for nested relational databases. ACM Trans, on Database Systems., vol.13,1988.

96. Shoshani A. CABLE: A Language Based on the Entity-Relationship Model, Lawrence Berkeley Lab, //Technical rep. LBL-22033, 1978.

97. Show G.M., Zdonik S.B. A Query Algebra for Object Oriented Databases. In Proc. of ICDE, 1990.

98. Stonebraker at el. Системы баз данных третьего поколения: Манифест. СУБД, 1995, 5. стр. 145-162.

99. Stonebraker М., Kemnitz С. The Postgres next generation database management system. //Communications of the ACM. 1991,34,, pp. 78-92.

100. Stonebraker M., Rowe L. The design of POSTGRES. In Proc. ACM SIGMOD, 1986.

101. Zastavnoy D.A. High-level Declarative Language for Object-Oriented Databases. //Proceedings of the First East-European Symposium on Advances in Databases and Information Systems. St.Petersburg, Nevski Dialect, 1997. pp.26-28.

102. Zastavnoy D.A., Bukatov A.A. Representation of Complex Structures Extracted from Object Databases, and Access to their Components. //In T.Hruska, M.Hishamoto, (ed), "Proceeding of 4th Joint Conference on

103. Knowledge-Based Software Engineering", IOS Press, Amsterdam, 2000, pp. 93-100.llO.Zdonic S., Maier D., Fundamentals of Object-oriented Databases, in Readings in Object-oriented Database Systems, Morgan-Kaufman, San Mateo, 1990. pp. 235-251.