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

кандидата технических наук
Соколова, Вероника Валерьевна
город
Томск
год
2006
специальность ВАК РФ
05.13.01
Диссертация по информатике, вычислительной технике и управлению на тему «Теория и алгоритмы обработки рекурсивных информационных структур»

Автореферат диссертации по теме "Теория и алгоритмы обработки рекурсивных информационных структур"

□иЗО52282

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

ТЕОРИЯ И АЛГОРИТМЫ ОБРАБОТКИ РЕКУРСИВНЫХ ИНФОРМАЦИОННЫХ СТРУКТУР

Специальность 05.13.01 — «Системный анализ, управление и обработка информации (отрасль: информация и информационные системы)»

АВТОРЕФЕРАТ

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

Томск-2007

003052282

Работа выполнена на кафедре оптимизации систем управления Томского политехнического университета

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

Официальные оппоненты:

НОВОСЕЛЬЦЕВ Виталий Борисович,

кандидат физико-математических наук, доцент

КОЧЕГУРОВ Владимир Александрович,

доктор технических наук, профессор

КАЛАЙДА Владимир Тимофеевич,

кандидат технических наук, доцент

Ведущая организация:

Томский государственный университет

Защита состоится «28» марта 2007 г. в 15— часов на заседании диссертационного совета Д212.269.06 при Томском политехническом университете по адресу: 634034, г. Томск, ул. Советская, 84, институт «Кибернетический центр» ТПУ.

С диссертацией можно ознакомиться в научно-технической библиотеке Томского политехнического университета по адресу: 634034, г. Томск, ул. Белинского, 53.

Автореферат разослан «27» февраля 2007 г.

Ученый секретарь диссертационного совета, / />

К.Т.Н.

4

доцент г ^^-у/' М.А. Сонькин

1. Общая характеристика диссертации

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

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

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

В работе строго показывается, что использование автоматного подхода позволяет эффективно обрабатывать рекурсивные зависимости. Учитывая, что общая задача обработки рекурсивного списка (развертка произвольной рекурсивной структуры) Л7>-трудна, предлагается корректная ограниченная стратегия достаточно эффективного (полиномиального) ее решения. Можно утверждать, что в проведенном исследовании предлагается совершенно новый подход к обработке рекурсивных структур данных.

Объектом исследования работы являются рекурсивные структуры данных. Предметом исследования - алгоритмы обработки и механизмы моделирования рекурсивных данных.

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

1. Расширение алгебры Кодда средствами описания рекурсивных структур.

2. Доказательство замкнутости расширенной реляционной алгебры.

3. Дополнение теории организации данных с использованием формализмов конечных автоматов.

4. Разработка и программная реализация процесса проектирования схем баз данных с рекурсивно-определяемыми атрибутами.

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

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

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

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

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

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

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

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

- 8th Korea-Russia International Symposium on Science and Technology «KORUS 2004» (г. Томск, ТПУ, 26 июня - 3 июля 2004 г.).

- V Всероссийская конференция «Системы и средства автоматизации» (г. Томск, ТПУ, 21-22 октября 2004 г.).

- III Всероссийская научно-практическая конференция «Молодежь и современные информационные технологии» (г. Томск, ТПУ, 15-17 февраля

2005 г.).

- Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2005» (г. Москва, МГУ, 12-15 апреля 2005 г.).

- X Байкальская Всероссийская конференция с международным участием «Информационные и математические технологии в науке, технике и образовании» (г. Северобайкальск, ИСЭМ СО РАН, 12-19 июля 2005 г.).

- 9lh Asian Logic Conference (г. Новосибирск, НГУ, 16—19 августа 2005 г.). III Всероссийская конференция молодых ученых в рамках Российского научного форума с международным участием «Демидовские Чтения» (г. Томск, ИОА СО РАН, 3-6 марта 2006 г.).

- IV Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, ТПУ, 28 февраля - 2 марта

2006 г.).

- Международная конференция «Инженерное образование и наука в мировом пространстве (GEER)», (г. Томск, ТПУ, 1-2 июня 2006 г.).

Публикации. Результаты диссертационного исследования изложены в 19 работах, в том числе 2 из перечня журналов, рекомендованных ВАК. Личный вклад автора в каждой публикации составляет 45-100%.

Личный вклад автора. Основные результаты диссертационной работы получены автором лично. Программный комплекс «RecModel 1.0» для проектирования схем баз данных с рекурсиями и представления их в стандартном реляционном описании разработан автором лично.

Внедрение результатов. Результаты работы используются в учебном процессе на кафедре Оптимизации систем управления ТПУ и в отделе Менеджмента качества Томского политехнического университета (КПР (ЦПР) №3.3.3.1.2. «Развитие СМК ТПУ на базе ISO 9001-2000»), внедрены в Институте оптики атмосферы СО РАН (г. Томск), в компании «ЭлеСИ» (г. Томск) и в ОАО «ТЭЛЗ» (г. Томск).

Результаты, выносимые на защиту:

1. Расширение алгебры (формальной теории) Кодца рекурсивными конструкциями.

2. Доказательство замкнутости и корректности модифицированной реляционной теории.

3. Представление и обработка рекурсивных структур данных посредством аппарата конечных автоматов.

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

Объем и структура диссертации. Диссертация включает в себя: введение, четыре главы, заключение, список литературы (120 наименований) и приложения, иллюстрирующие технические детали реализации программного комплекса. Общий объем работы составляет 150 страниц, включая 32 рисунка и 5 таблиц.

2. СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Глава 1

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

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

Материалы первой главы перекликаются с работами С.Д. Кузнецова1 и других ученых, чьи результаты связаны с проблемами развития технологий баз данных. В упомянутых работах отмечается необходимость выполнения рекурсивных запросов, но не приведены механизмы их реализации в существующих СУБД.

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

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

Глава 2

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

Фиксируется сигнатура. Определение 2.1. Сигнатурой Е = <Д, Ф, Т> назовем тройку, где Л- множество имен сущностей, Ф - множество имен доменов, Ф - множество имен функциональных связей над атрибутами.

Все множества сигнатуры являются не более чем счетными. Во множестве Ф зафиксировано непустое конечное подмножество Тс® - имен первичных доменов (предопределенных типов).

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

Определение 2.3. Под термином атрибут будем понимать пару (имя сущности, тип). Интерпретированный атрибут — суть подмножество элементов соответствующего типа, денотативно выделенное из последнего. Определение 2.4. Под термином кортеж, будем понимать список атрибутов. Определение 2.5. Ключ - это минимальный набор именованных атрибутов, определяющий оставшуюся часть кортежа.

* Кузнецов. С Д Основы баз данных Курс лекций Учебное пособие - А/ ИНГУШ] 2005 - 488 с

7

Определение 2.6. Домен данных - это (не более, чем счетное) множество некоторых однородных допустимых значений. Например, можно рассматривать множество целых чисел как домен. Для предметной области «Сотрудники» домен «разряд» будет принимать числовые значения, определенные Единой тарифной сеткой.

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

1. Домен имеет уникальное имя (в пределах базы данных).

2. Домен определен на некотором простом типе данных или на другом домене.

3. Домен может иметь некоторые логические свойства, позволяющие специфицировать его (домена) подмножества.

4. Домен несет определенную смысловую нагрузку.

При задании конкретной интерпретации I именам доменов (в том числе базовых) сопоставляются конкретизированные типы (множества). Предполагается, что именам базовых доменов при этом сопоставляются традиционные для программирования типы (например, integer, real, char, Boolean и т.д.).

Непервичными доменами могут выступать именованные подмножества базовых (например, Namecstring), либо подмножества декартовых произведений ранее определенных доменов (PersoncNamexAgexSex)

Суммируя сказанное, уточним определение домена следующим образом. Определение 2.7. Пусть задана интерпретация I,Ре% Reтогда

1) P\i- домен;

2) если /?|idP|Is_TO_/?|t - домен;

3) если R,h (¿=1,и) - домены, то 7?0|icj?i|ix...x/i,,|i - домен.

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

Прежде чем переходить к фиксации базового для реляционной алгебры понятия таблицы, отметим, что наследники примитивных типов импортируют все операции и отношения от порождающих. - Так, для AgeaPositivInteger имеет место отношение ">" и все операции для целых положительных. Определение 2.8. Отношением является некоторое подмножество декартова произведения одного или более доменов. Отношение обычно записывается в следующем виде: R(AlrA2,---An)-

Отношение обладает двумя важными свойствами:

1) в отношении не содержится совпадающих кортежей;

2) порядок кортежей в отношении несущественен.

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

Термины «отношение» и «таблица» в значительной степени являются синонимичными, тем не менее, их имеет смысл различать.

Определение 2.10. Под реляционной базой данных будем подразумевать совокупность взаимосвязанных отношений.

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

Определение 2.11. Схема таблицы (домена) - это именованное множество пар (имя атрибута, имя домена) вида D(r)=r.(D\(ai),...J)„(a„)), где D, D,e<D (i=l,n) — имена доменов, г, а,с_Я 0=1,я) — имена атрибутов. В правой части определения г может «проноситься» в скобки на любую глубину, так что

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

Определение 2.12. Кортеж-тип для схемы D из определения 2.11 представляется формой C=<a¡:Di, a2:D2,..., a„:D„> с аналогичными функциями принадлежности. Степень или арность схемы отношения определяется количеством атрибутов п схемы.

Определение 2.13. Схема БД— это набор именованных схем отношений.

Например, схема отношения «СОТРУДНИК» выглядит так: сотрудник((фамилия, text{ 20)), (имя, tert(15)), (отчество, text{\5)), (дата рождения, date), (пол, Boolean)). При этом заранее может быть задан домен пол с областью значений (М, Ж).

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

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

Приведем определение операции объединения (остальные операции алгебры формулируются аналогично).

' Codd Е F A Relational Model of Dala for Large Shared Dala Banks //CACM - 1970 -Кг 13, пб -P 30-42

Определение 2.15. Пусть даны два непервичных домена и Т2а02, где

А=Д> синтаксически равны, тогда результатом операции объединения двух отношений является отношение, включающее все кортежи, входящие хотя бы водно из отношений-операндов. Таким образом, результат объединения это таблица Т^^Щ-^Т^у, где (Л1:('|| е Г^^^е Гг'ц)). Считается, что совпадающие кортежи элиминируются.

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

Реляционная алгебра представляет собой набор операторов, использующих отношения в качестве аргументов, и возвращающие отношения в качестве результата. Таким образом, реляционный оператор / выглядит как функция типа «отношения» с отношениями в качестве аргументов: Я=АГ1,Г2,--;Г„):Г0.

Реляционная алгебра является замкнутой, поскольку в качестве аргументов в реляционные операторы можно подставлять другие реляционные операторы, подходящие по типу: /¿=//¡0,ьг12,.. .,г,„),/2(^21/22,•• ■ •)•

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

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

ПОДРАЗДЕЛЕНИЕ -Он

Наименование(РК)

Руководитель

Подчиненное подразделение (РК)

У

Рис. 1. Схема рекурсивного объекта

В диссертации рассматриваются рекурсивные таблицы. Везде ниже допускается только явная рекурсия в смысле следующего определения. Определение 2.16. Таблица Т(г)=г.(а ] :£)] ,а2:02,... ,а„\Оп) является допустимой, если синтаксическое равенство А=Г, определяющее рекурсию, выполняется не более, чем для п-1 доменов.

Заметим, что кортеж не может ссылаться на самого себя ни непосредственно, ни опосредованно.

Расширим реляционную алгебру, переопределив понятие таблицы следующим образом.

Определение 2.17. Таблица - это совокупность конечного числа кортежей конечной длины, таких что

если C=<a\.Di,ai.D2,...,a„\Dn> - кортеж-тип, где все атрибуты а, попарно различны, то С назовем ос'новным кортежем-типом или основой; обобщенной таблицей основной таблицы Т будем называть конечную совокупность регулярных кортежей-значений Сг определяемых основным кортежем-типом С таблицы Т, при этом кортежи-значения Сг попарно различны;

каждый кортеж Сг[г w-кратно (т>1) повторенный набор атрибутов-значений <o11,oI2,...,ai„,<a2i,a22,-,a2„,...,<ami,am2,...,iJmn...>», таких что a,keDk (1 <к<п) основного кортежа С и никакие два подкортежа <а,\,аа,-■ ■ ,а,„> и не совпадают при

хотя бы один из атрибутов первого подкортежа имеет значение nil в позиции рекурсивной ссылки (выход из рекурсии). Частный случай основной рекурсивной таблицы можно представить

PRIMARY OTHER FOREIGN

KEY ATTRIBUTES KEY

R

r

М- 1 |

Рис. 2. Схема основной рекурсивной таблицы Определение 2.18. Для обобщенной таблицы Т стандартным образом определены ключевой набор К и индексный набор / , такие что (1) D(K)aD(J), (2) KDI=# и (3) определено отображение R:I—>K, причем неподвижной точкой такого транзитивного замыкания R* является пустое значение nil.

Тогда рекурсивным эквисоединением таблицы Т по отношению R называется операция, результатом которой выступает обобщенная таблица ТК, такая что для каждого её кортежа - значения Cr\i, состоящего более чем из двух кортежей основной таблицы <с\,с2,...,с„>:

1) /(с„)=т/;

2) f(ckA)= K(ck), где к<т.

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

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

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

селекция, соединение) к произвольным таблицам Т\ и Т2 будет таблица в смысле того же определения 2.17.

Теорема 2.1. Рассмотрим таблицы Т\ и Т2. Пусть G=T\\JT2. Покажем, что G удовлетворяет определению 2.17. Доказательство (схема).

а) Поскольку Т\ и Т2 - таблицы в смысле определения 2.17, то каждая из них состоит из попарно различных кортежей С'г (1<г<п) и С", (1<г<ш) соответственно. Тогда по определению операции объединения таблица G будет также состоять из попарно различных кортежей Cr (1 <r<k, k<m+n -повторяющиеся кортежи исключаются).

б) Аналогично, в таблице G каждый кортеж есть m-кратно повторенный набор атрибутов-значений <a,i,ai2,-,ai„,<a2i,a22,...,a2„,...,<amuam2,-,amp'», таких, что a,„eDs (1 <s<ri) основного кортежа С и никакие два подкортежа <а,иад,. ..,£!,*> и <а/],а)7,...,а,р> не совпадают при

в) Г] - таблица в смысле определения 2.17. Следовательно, хотя бы один из атрибутов первого подкортежа имеет значение nil. Т2 — также таблица в смысле определения 2.17. Следовательно, хотя бы один из атрибутов её первого подкортежа имеет значение nil. Тогда таблица G будет также содержать хотя бы один такой подкортеж (по действию операции объединения).

г) Т\ - таблица в смысле определения 2.17, следовательно, в ней заданы ключевой набор К' и индексный набор /', такие что D(K')=D(I') и

Т2 — также таблица в смысле определения 2.17, следовательно, и в ней заданы ключевой набор К" и индексный набор /", такие что D(K")=D(I") Из требования совместимости таблиц Г] и Т2 по объединению и действию операции объединения вытекает, что D(K)=D(J) и KCV=£f, где

K=K\JK", 1=1 VI".

д) Г, -таблица в смысле определения 2.17, следовательно, существует отображение R':I'->K', причем неподвижной точкой такого транзитивного замыкания R'* является значение nil. Т2 - таблица в смысле определения 2.17, следовательно, существует отображение причем неподвижной точкой такого транзитивного замыкания R"* является значение nil. В таблице G можно определить отображение R:I^>K, которое действует по правилу R(i)=R'(/) при /е/' и R(i)=R "(г) при iel". Транзитивное замыкание R* будет иметь неподвижные точки, значение которых nil.

е) Для каждого кортежа-значения Сг|г таблицы G, состоящего более чем из двух кортежей основной таблицы <ci,c2,...,cm> будут выполняться условия i(cm)=nil и Г(скАу-К(ск), к<т

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

Глава 3

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

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

Определение 3.1. Атомарный запрос есть первичное значение, допустимое в заданной интерпретации. Непервичный (автоматный) запрос определяется некоторым конечным автоматом и реализуется применением этого автомата к входным данным.

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

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

Для строгого введения последующих понятий зафиксируем сигнатуру: Определение 3.2. Сигнатурой назовем тройку Z=(A <7), здесь Я. - множество символов атрибутов, £ - множество символов состояний, Т- множество символов доменов (возможных типов). Полагаем, что в Т зафиксировано непустое подмножество <Z>zT символов первичных доменов (Ф*0), содержащих базовые значения атрибутов (например, integer, date, text и т. д.). Считается, что при любой интерпретации первичному домену сопоставляется перечислимое множество элементов.

Определим схему обобщенной (автоматной) рекурсивной таблицы. Определение 3.3. Обобщенная рекурсивная таблица Т определяется записью Т^(а]:Тиа2:Т2,. ,.,а„:Т„), при этом 7',е'Г - принадлежат множеству символов типов сигнатуры и, как минимум, один Т,еФ, а,е_Я - принадлежат множеству символов атрибутов. Разрешено синтаксическое равенство (текстуальное совпадение) Г и одного или нескольких (но не более, чем /7-1) 7) При рассмотрении набора таблиц допускается появление неявной или

1 Карпов Ю Г Теория алгоритмов и автоматов - СПб Геликон Плюс, 2000 - 256 с

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

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

((а и а и (a2i а22 nil)) (а,, аЪ2 (а4! а42 (а5, а52 nil)))).

Автомат, воздействуя на входную строку (домен), может активизировать другой КА или самого себя (рекурсивно и, возможно, опосредованно):

^оо^Яоо: Аю,- ■ А>ьЯом:-^Оо*+],• • ■ Лш-• •■!'...)

Определение 3.4. С учетом заданной сигнатуры непервичный автомат Q определяется следующим образом: где QeT\<D- Q не является

именем первичного домена; А - алфавит над декартовым произведением то есть это все комбинации допустимых пар из декартова произведения типов и имен атрибутов; Re<E- конечное множество состояний автомата; Д - функция перехода, определенная на множестве AxR; стеЛ — начальное состояние; FcR -непустое множество конечных состояний.

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

Функция перехода, ассоциированная с автоматом Q, является частичной функцией Д:AxR-*AxR. Областью определения данной функции является декартово произведение атрибутов и состояний, допустимых для конечного автомата Q, а множеством значений - преобразованные конечным автоматом пары <элемент_алфавита, состояние>. При необходимости подчеркнуть связь Д с автоматом Q используется запись Де.

Определение 3.5. Считается, что функция перехода, как правило, дискретна, т.е. может быть задана множеством пар: Д^{(а,5),(а',5')}.

На рис. 3 данным парам соответствуют х - текущий анализируемый атрибут, у - атрибут, который автомат записал в выходной поток после обработки, и переход между состояниями б—>8'.

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

ВХОДНАЯ ЛЕНТА

УСТРОЙСТВО УПРАВЛЕНИЯ КА

ВЫХОДНАЯ ЛЕНТА

Рис. 3. Структурная схема конечного автомата

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

Пусть aejl, а - допустимое имя, тогда а и а.а - также допустимые имена, во втором случае а и а называются префиксом и суффиксом, соответственно. Допустимое имя а становится именем атрибута, только если оно связывается с некоторым доменом Те'Т. Факт связывания отмечается записью Да) или а. Г (точечная пара, согласно нотации языка ЛИСП) - первая форма подчеркивает функциональность связывания, а вторая - его ссылочность. Если Ге®, и а -примитивный атрибут, то а Г заменяется ira аТ либо на а, когда ссылка на домен не существенна или очевидна из контекста. Связь именованного объекта с интерпретацией I изображается стандартной записью (имя)\\. Интерпретация задается традиционно: примитивному атрибуту сопоставляется константа из первичного домена a |ie7]b тогда автоматной функции соответствует отображение —jixj^Ii-

Определение 3.6. Любой непервичный домен Т, где ГеИ\Ф является структурой

над именованными компонентами: а.7'— а.(а\.Ти...,а„.Т„), где а - параметр-модификатор имен элементов списка согласно точечной нотации, а, а,еД -попарно-различные, ТеТ\Ф, Т,еТ. В определении домена допускается рекурсия (в том числе, и неявная).

Интерпретация a.J|i определяет пустой или сколь угодно длинный (ноконечный) регулярный список вида a.((al.rnli,...,a„.i„i|i)...(ai.ii)t|b...,an.int|i)),

где для всех значений индексов г=(1,...,и), у"=(1,.. а,е.А, Т,е 1'.

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

а.((а1./ц...)•■■)—(а-(«1-'п---) ..)~((а.а1.Гц...)■•■)■ Такие структуры можно считать таблицами, подразумевая, что подсписки соответствуют строкам (кортежам) таблиц реляционного подхода. Ясно, что в свою очередь, могут являться списками, возможно, пустыми.

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

Глава 4

В этой главе рассматриваются реализационные аспекты, использующие функциональный аппарат системы программирования ЛИСП. В главе также приведено описание разработанного программного приложения «КесМо(Зе1 1.0» и процесса проектирования схемы базы данных на примере информационной системы поддержки менеджмента качества.

Зададим описание автомата Я-термом в стиле функциональных языков. Определение 4.1. Автомат определяется функциональной записью вида £>=(?цх.Д[х]) при этом £>еТ,<Д где Q - имя автомата не могущее быть именем из первичного домена, а Д[х] традиционно обозначает вхождение (элементов) списка х в форму Д.

В наиболее общем случае структура формы Д определяется следующей конструкцией согласно нотации языка ЛИСП:

(ВО (<ти_/огт>) {<^1ор_сопс1Июп> <ас1юп.ч>) <асиою>).

Интерпретацией автомата Q, как отмечалось выше, является применение его к списку 5 интерпретированных атрибутов - это обозначается традиционной для функционального подхода записью (<2 ¿"Ь) или (<2 5), если интерпретация очевидна из контекста. Результатом интерпретации автомата является также список (возможно, пустой), который, в свою очередь, может использоваться в качестве домена при спецификации нового атрибута. Поскольку атрибуты Я могут являться применениями автоматов, возникает вопрос о трактовке операции суперпозиции автоматов, который решается через вложенный функциональный вызов.

Рассмотрим ряд дополнительных соглашений относительно рекурсивных структур данных. Пусть регулярный список Ь некоторым образом порождается доменом 7,0=(а1.7'|,,..,а„.Г„), состоящим из первичных атрибутов. Условимся рассматривать только такие списки, у которых первый атрибут связан с первичным доменом, то есть Г^Ф (синтаксическое ограничение) Соответственно, первый атрибут (а|.7У) будем называть первичным ключом

и считать его уникальным именем любого подсписка списка L верхнего уровня, так что в i,=a.((ai./M|I,...,o„.i„i|i)...(a1.iu|I,...,£i„./„t|I)) значения всех ai.tu\i -попарно-различны, т. е. уникальны (семантическое ограничение). Определение 4.2. Множество Ki^{a\.t\},\) будем называть ключевым множеством списка L. Считается, что на элементах К определено отношение полного порядка ("</£"), как правило, индуцируемое соответствующим отношением на Тх, а также операция инкрементирования. Важно подчеркнуть, что в набор параметров автомата х определения автомата в качестве обязательного параметра входит системный ключ ai. Отметим, что отношения порядка могут быть определены на домене любого атрибута (группы атрибутов), - это позволяет организовывать необходимые индексированные цепочки, что аналогично понятию ключа в реляционном подходе.

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

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

Определение 4.4. Для «свертки данных» используется автомат-конструктор: (CONSTR(r(aba2,...,<7r,)))^(7'(ab£'2,---,ar,)). Во внешней по отношению к конструктору переменной запоминается прохождение всех рекурсивных ответвлений при обработке данных, что сокращает время обработки.

Далее необходимо определить обратную операцию - развертку данных на непервичном атрибуте.

Определение 4.5. Пусть Т(г)=г.(.■ ..) - описание домена, и TviD.

Развёрткой домена Т на атрибуте arj будем называть список, получающийся в результате подстановки в описание исходного домена на место имени T,j{a,j), раскрытого соответствующим автоматом, подсписка-домена Tv{au). Все добавленные в развернутый домен Т в результате такого действия атрибуты модифицируются префиксом r.av, что индуцирует и модификацию автомата, доставляющего реализацию домена Ty(av). Процесс построения развёртки на атрибуте может повторяться многократно - пока имеются атрибуты, связанные с неэлементарными схемами.

Зададим операцию полной развертки. Определение 4.6. Под полной развёрткой Т понимается завершенный процесс применения соответствующего автомата к интерпретации домена.

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

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

На следующем рисунке приведена развёртка рекурсивной схемы.

|М|-1

Рис. 4. Развёртка рекурсивной схемы таблицы

Определение 4.7. Пусть Т - автоматный (возможно, рекурсивный) домен и пусть А - некоторый набор атрибутов домена. Замыканием А+ для А относительно Т будем называть объединение всех таких атрибутов X, что автоматное отображение ():А->Х может быть получено из информации о домене Т. Здесь <2 - (автоматный) терм в сигнатуре Е, построенный по специальным правилам, А и X - непустые наборы атрибутов. Замыкание А4 используется для обеспечения семантической необходимости выхода из рекурсии в практических случаях.

В предлагаемом подходе результат обработки произвольного списка вычисляется «по частям», т.е. вместо вычисления полного списка а.(а!.Г|,а2Лг,• •■А>Л) можно найти первый элемент а.(aj.ii) и выполнить вычисления остальных элементов с помощью автоматов, реализующих конкретные операции. При этом получается принципиальная экономия памяти ценой незначительного перерасхода времени на вспомогательное построение.

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

Рис. 5. Общий алгоритм выполнения запросов

В данной главе также рассматривается программная реализация процесса проектирования схемы баз данных с рекурсивными структурами с помощью разработанного программного комплекса «ЯесМосЫ 1.0». В целом программное моделирование рекурсивных зависимостей соответствует нотации ГОЕР1Х.

Программа выполняет следующие основные функции:

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

• обеспечивает построение ЕЯ-диаграммы (модель «сущность-связь»);

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

• предоставляет возможность генерации 8(ЗЬ-кода для создания таблиц базы данных с учетом ограничений целостности.

Пример окна программы «Создание таблицы» представлен на рисунке 6. В данном диалоговом окне пользователь может задать описание полей таблицы по основным параметрам: название поля, тип поля, размер поля, значение по умолчанию, описание поля, признак ключевого поля, тип ключа (первичный, внешний, рекурсивный), уникальность и ограничения на вводимые значения.

pa......

Код пацшего Код _ шла Название

Г

Г New [ ЕШ1 j Delete [ j-

Ok

Cancel

Fteki Name Код Key Type PRJMARY -1

jfieM Type MTEGCFt * Key Struct me SWl/lf'l F ~W |

field Size Null Sufiport NOT_NUU •w

Default Value Icheck Uniqueness UNIQUE •w;

Field Dcscf iptton Код подразделения |

Рис. 6. Диалоговое окно «Создание таблицы»

Для связывания таблиц между собой, пользователь должен установить их в диалоговом окне «Создание связей» как тжтано на рисунке 7.

ё

Рис. 7. Диалоговое окно «Создание свячен»

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

) ОЬ>еЯ

(сцк I

±

ЦпЫюкТуре Ц |

1юк

1 Г«к1 ПеН

1 1ТаЫ« ТаЬе ; ЯкМ Ре'с! ; гТлЫег Твое

йх-йлг

вйГекИО ^сУ цйПекЯО Г|ей 3*ТвИе10 ТаЫе Эе*Тай«20 Т^е 1гЛО *ой

Эигд с^вскЕчО сковал

кда 1

---г| Р«*<Ьме | I

рге*ег4Мюп

I СпацЦпквОМод Ц Сгеа!еи1*8Рч1од1|пИ>аи<«1ег || ипвЗЬард |[~МаМг«т» |

| ! |

----------1 | |

_____|

МмЛгв

, 1 йгтд 1Гяг|гдВцЯм |

'Л 1' Ирв

Рис. 8. Класс установлена связей между таблицами

Материал, иллюстрирующий этапы работы программного комплекса, оформлен в виде приложений в диссертации.

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

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

5. Предложенные формализмы, алгоритмы обработки и разработанный программный комплекс использованы при проектировании предметной области «Информационная система менеджмента качества кафедры» в отделе Менеджмента качества Томского политехнического университета, при проектировании и модификации баз данных метеорологических параметров атмосферы в системах «ТОР-станция» и «Аэрозольная станция» в Институте оптики атмосферы СО РАН (г. Томск) и при разработке программного комплекса «Управление основным производством» для ОАО «ТЭЛЗ» г. Томск, а также могут быть использованы при проектировании схемы базы данных «Профили компетентности специалистов» в компании «ЭлеСи» (г. Томск).

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Govorushko, V. V. (Sokolova, V. V.) Expansion of Codd algebra Operations with recursive objects / V. V. Govorushko, V. B. Novoseltsev // «KORUS 2004»: Proc. of 8'lh Korea-Russia International Symposium on Science and Technology, 26 june - 3 july, 2004. / TPU, - Tomsk, 2004. - P. 39-42.

2. Говорушко, В. В. (Соколова, В. В.) Расширение алгебры Кодца операциями с рекурсивными объектами / В. В. Говорушко, В. Б. Новосельцев // Вестник Томского государственного университета. - 2004. № 284, серия «Математика. Кибернетика. Информатика». - С. 18-21.

3. Соколова, В. В. Использование рекурсивных структур данных при построении сложных организационных систем // «Интеллектуальные технологии в образовании, экономике и управлении-2004»: Труды международной научно-практической конференции, 2004 г. / ВГУ, -Воронеж, 2004. - С. 175-177.

4. Сокрлова, В. В. Моделирование рекурсивных структур в реляционных базах данных / В. Б. Новосельцев, В. В. Соколова // «Информационные технологии и математическое моделирование (ИТММ-2004)»: Труды III Всероссийской научно-практической конференции, 11-12 декабря 2004 г. / Филиал КемГУ, - Анжеро-Судженск, 2004. - С. 107-109.

5. Соколова, В. В. Моделирование и реализация рекурсивных структур / В. Б. Новосельцев, В. В. Соколова // «Современные средства и системы автоматизации»: Труды V научно-практической конференции, 21 -22 октября 2004 г. / ТУСУР, - Томск, 2004. - С. 133-136.

6. Соколова, В. В. Применение операций с рекурсивными объектами в реляционной алгебре Кодца // «Инфотелекоммуникационные технологии

в науке, производстве и образовании»: Труды I международной научно-технической конференции, 19-20 декабря 2004 г. / СевКавГТУ, — Ставрополь, 2004. - С. 494-498.

7. Соколова, В. В. Моделирование рекурсивных структур в базах данных конечными автоматами / В. Б. Новосельцев, В. В. Соколова // «Ломоносов 2005»: Тезисы докладов международной конференции студентов и аспирантов по фундаментальным наукам, 12-15 апреля 2005 г. / МГУ им. М. В. Ломоносова, - Москва, 2005. - С. 68-69.

8. Соколова, В. В. Внедрение системы менеджмента качества на кафедре вуза / В. Б. Новосельцев, В. В. Соколова // «IT-инновации в образовании»: Труды Всероссийской научно-практической конференции, 27 июня -1 июля 2005 г. / ПетрГУ, - Петрозаводск, 2005. - С. 218-221.

9. Соколова, В. В. Моделирование рекурсивных структур конечными автоматами / В. Б. Новосельцев, В. В. Соколова // «Информационные и математические технологии в науке, технике и образовании»: Труды X Байкальской Всероссийской конференции, 12-19 июля 2005 г. / ИСЭМ СО РАН, - Северобайкальск, 2005. - С. 128-134.

10. Соколова, В. В. Таксономия рекурсивных зависимостей // «Молодежь и современные информационные технологии»: Труды III Всероссийской научно-практической конференции студентов, 15-17 февраля 2005 г. / ТПУ, - Томск, 2005. - С. 137 -138.

11. Соколова, В. В. К вопросу об информационной поддержке системы менеджмента качества / Е. И. Громаков, В. В. Соколова // «Качество высшего образования и подготовки специалистов к профессиональной деятельности»: Труды международного симпозиума, 9-11 ноября 2006 г. / Московский государственный институт радиотехники, электроники и автоматики, - Москва, 2006. - С. 272- 275.

12. Соколова, В. В. Применение автоматного подхода при обработке рекурсивных структур данных / В. Б. Новосельцев, В В. Соколова // «Фундаментальные проблемы новых технологий в 3-ем тысячелетии»: Труды III Всероссийской конференции молодых ученых в рамках Российского научного форума с международным участием «Демидовские Чтения», 3-6 марта 2006 г. / ИОА СО РАН, - Томск, 2006. - С. 674-677.

13. Соколова, В. В. Автоматный подход к организации многомерных рекурсивных СУБД // «Молодежь и современные информационные технологии»: труды IV Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых, 28 февраля — 2 марта 2006 г. / ТПУ, - Томск, 2006. - С. 220-221.

14. Соколова, В. В. Система поддержки принятия решений руководителя кафедры / А. Р. Вахитов, В. В. Соколова // «Молодежь и современные информационные технологии»: Труды IV Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых, 28 февраля - 2 марта 2006 г. / ТПУ, - Томск, 2006. - С. 186-187.

15. Соколова, В. В. Информационная система поддержки менеджмента качества / Е. И. Громаков, В. Б. Новосельцев, В. В. Соколова // «Инженерное образование и наука в мировом пространстве»: Труды международной конференции GEER, 1-2 июня 2006 г. / ТПУ, - Томск, 2006.-С. 371-372.

16. Соколова, В. В. Информационные технологии в системах поддержки принятия решений / А. Р. Вахитов, В. В. Соколова // «Математика, информатика, управление» (МИУ-06): Труды Всероссийской конференции с международным участием, 8-12 июля 2006 г. / БГУ, - Улан-Удэ, 2006. -С. 38-42.

17. Соколова, В. В. Система поддержки принятия решений для менеджмента качества / А. Р. Вахитов, В. В. Соколова // «Энергия молодых - экономике России»: труды VII Международной научно-практической конференции студентов и молодых ученых, 17-21 марта 2006 г. / ТПУ, - Томск, 2006. -С. 401-402.

18. Соколова, В. В. Обработка рекурсивных данных конечными автоматами / В. Б. Новосельцев, В. В. Соколова // Известия Томского политехнического университета. - 2006. Т. 309, №7. - С. 130-134.

19. Соколова, В. В. Моделирование рекурсивных структур в базах данных / В. Б. Новосельцев, В В. Соколова // «INTERMATIC - 2006»: материалы IV Международной научно-технической конференции «Фундаментальные проблемы радиоэлектронного приборостроения», 14-18 ноября 2006 г. / МИРЭА, - Москва, 2006. - С. 187-190.

СОКОЛОВА Вероника Валерьевна

ТЕОРИЯ И АЛГОРИТМЫ ОБРАБОТКИ РЕКУРСИВНЫХ ИНФОРМАЦИОННЫХ СТРУКТУР

АВТОРЕФЕРАТ

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

Подписано к печати 22.02.2007. Формат 60x84/16. Бумага «Классика» Печать RISO Уел печл. 1,45 Уч -изд.л. 1,32

Заказ % fi Тираж 100 экз.

Томский политехнический университет Система менеджмента качества Томского политехнического университета сертифицирована NATIONAL QUAUlY ASSURANCE по стандарту ISO 9001:2000

тТБАЬСТВ0»МПУ. 634050, г.Томск, пр. Ленина, 30

Оглавление автор диссертации — кандидата технических наук Соколова, Вероника Валерьевна

Введение.

Глава 1. Современная ор1анизация баз данных.

1.1. Системы баз данных, основанные на правилах.

1 2. Постреляциониые базы данных.

13 Объекшо-ориешированпые базы данных.

1 4 Технология 01 АР

1.5. Выводы.

Глава 2. Расширение реляционной алгебры Кодца.

2.1. Базовые понятия реляционной модели данных.

2 2 Средства манипулирования реляционными данными.

2.3. Расширение реляционной ал[ебры

2.4. Доказательство замкнутости расширенной реляционной ашебры.

2 5. Выводы.

Глава 3. Автоматный подход к обработке рекурсивных таблиц.

3.1. Базовые понятия и амлашения.

3 2 Автоматный подход к обработке рекурсивных наборов данных.

3 2 1 Списочная реализация автоматов.

3 22 Вложенные автоматы

3 3. Синхронный и асинхронный конечные автоматы.

3 4 Выводы

Глава 4. Реализация автоматного подхода к обработке данных с использованием функциональных языков.

4 1. Определения и соглашения

4 2. Язык спецификаций, основные алгоритмы работы.

4 3. Программная реализация процесса проектирования схемы базы данных.

4 3 1. Модель СМК как «черного ящика»

4 3 2 Программный комплекс моделирования предметной области.

4 4. Выводы

Введение 2006 год, диссертация по информатике, вычислительной технике и управлению, Соколова, Вероника Валерьевна

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

С появлением современных промышленных реализаций реляционных СУБД, их стали использовать и в менее традиционных прикладных областях, таких как САПР [101], системы обработки знаний [98] и т.д. Соответствующие программные комплексы обычно оперируют сложноструктурированными объектами, для обработки которых необходимо использовать запросы, требующие, в общем случае, рекурсивного соединения отношений.

Рекурсивные наборы данных встречаются во многих предметных областях и, в частности, в информационных системах поддержки менеджмента качества организаций и предприятий. Базовым стандартом, устанавливающим требования к системам менеджмента качества (СМК), является стандарт ИСО 9001:2000 [23]. Соответствие данному стандарту позволяется организациям, а именно ВУЗам, закрепить свои позиции на рынке образовательных услуг. Система контроля качества подготовки специалистов на современном этапе развития предполагает существование вузовской документации в виде положений, инструкций, методических указаний и стандартов предприятия по организации и контролю образовательною процесса. Согласно стандарту, каждое структурное подразделение (например, кафедра ВУЗа) должно иметь и поддерживать в рабочем состоянии свой комплект документов, определяющий характер деятельности подразделения в СМК и обеспечивающий возможность анализа результатов этой деятельности.

В целом, СМК является сложной экономико-технической системой, в которой возникает целый ряд новых, ранее не решаемых задач, поэтому для анализа и управления СМК целесообразно применять классические методы системного анализа. В соответствии со стандартом ИСО 9001:2000 ко всем процессам, характеризующим СМК, рекомендуется применять методологию постоянного улучшения, известную как цикл «Plan-Do-Check-Act» [29, 30], включающий рекурсию. Таким образом, для данной предметной области, как и для многих других, необходимо спроектировать информационную систему, позволяющую обрабатывать рекурсивные наборы данных. Большинство современных информационных систем базируются на реляционной модели данных, которая не предусматривала оперирования рекурсивными структурами, в связи с этим, определим, прежде всего, актуальность исследования, его цели и задачи, а также сформулируем выносимые на защиту новые полученные результаты.

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

В современных информационных системах, в частности, работающих с экономическими, медицинскими, химическими наборами данных, крайне важной является проблема построения и обработки рекурсивных информационных структур (структур, элементами которых выступают логически подобные комплексы). Данные структуры поддерживают большое количество скрытых зависимостей, которые важны для корректной обработки информации, например, в информационных системах поддержки менеджмента качества все процессы должны соответствовать циклу непрерывного улучшения. Манипулирование рекурсивными наборами данных в стандартных (де-факто - реляционных) комплексах осуществляется, как правило, внесистемными средствами: внешними модулями, триггерами и т.д. Объясняется это отсутствием в классической алгебре Кодда механизмов, естественным образом поддерживающих оперирование рекурсивными 5 комплексами. В настоящее время доступен некоторый инструментарий (опять же, технического характера), который можно найти в объектно-ориентированных оболочках [99, 107, 107, 108, 115, 119]. Однако отсутствие строгого теоретического аппарата, подобного реляционной алгебре, не обеспечивает уверенности в реализационных характеристиках конечного программного продукта (целостности, корректности, неизбыточности и т.д.), что, очевидно, вызывает необходимость дальнейших исследований в данной области.

Вторым фактором, определяющим актуальность работы, является то, что существующие на сегодняшний день CASE-средства [9, 14, 42, 55, 68], не предлагают эффективных решений в области моделирования рекурсивных наборов данных и их адекватного отображения в стандартное реляционное представление. Таким образом, необходим программный комплекс, интегрирующий процессы моделирования и представления в физическую структуру именно рекурсивных наборов данных.

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

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

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

Объектом исследования работы являются рекурсивные структуры данных.

Предмет исследования - алгоритмы обработки и механизмы моделирования рекурсивных данных.

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

1. Пополнение алгебры Кодда средствами описания рекурсивных структур.

2. Доказательство замкнутое i и расширенной реляционной алгебры.

3. Дополнение теории организации данных с использованием формализмов конечных автоматов.

4. Разработка и программная реализация процесса проектирования схем баз данных с рекурсивно-определяемыми атрибутами.

Методы исследования

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

Научная новизна работы

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

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

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

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

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

Практическая значимость работы

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

Положения, выносимые на защиту:

1. Расширение алгебры (формальной теории) Кодда рекурсивными конструкциями.

2. Доказательство замкнутости и корректности модифицированной реляционной теории.

3. Представление и обработка рекурсивных структур данных посредством аппарата конечных автоматов.

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

Внедрение полученных результатов

Результаты работы используются в учебном процессе на кафедре Оптимизации систем управления ТПУ и в отделе Менеджмента качества Томского политехнического университета (КПР (ЦПР) № 3.3.3.1.2. «Развитие СМК ТПУ на базе ISO 9001-2000»), внедрены в Институте оптики атмосферы СО РАН (г. Томск), в компании «ЭлеСИ» (г. Томск) и в ОАО «ТЭЛЗ» (г. Томск).

Публикации

Результаты диссертационного исследования изложены в 19 работах, в том числе 2 из перечня журналов, рекомендованных ВАК. Личный вклад автора в каждой публикации составляет 45-100%.

Личный вклад автора

Основные результаты диссертационной работы получены автором лично. Программный комплекс «RecModel 1.0» для проектирования схем баз данных с рекурсиями и представления их в стандартном реляционном описании разработан автором лично.

Апробация работы

Основные положения и результаты диссертации докладывались и обсуждались на следующих конференциях:

1. 8th Korea-Russia International Symposium on Science and Technology «KORUS 2004» (г. Томск, ТПУ, 26 июня - 3 июля 2004 г.).

2. V Всероссийская конференция «Системы и средства автоматизации» (г. Томск, ТПУ, 21-22 октября 2004 г.).

3. III Всероссийская научно-практическая конференция «Молодежь и современные информационные технологии» (г. Томск, ТПУ, 15-17 февраля 2005 г.).

4. Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2005» (г. Москва, МГУ, 12-15 апреля 2005 г.).

5. X Байкальская Всероссийская конференция с международным участием «Информационные и математические технологии в науке, технике и образовании» (г. Северобайкальск, ИСЭМ СО РАН, 12-19 июля 2005 г.). th

6. 9 Asian Logic Conference (г. Новосибирск, НГУ, 16-19 ав1уста 2005 г.).

7. III Всероссийская конференция молодых ученых в рамках Российского научного форума с международным участием «Демидовские Чтения» (г. Томск, ИОА СО РАН, 3-6 марта 2006 г.).

8. IV Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, ТПУ, 28 февраля - 2 марта 2006 г.).

9. Международная конференция «Инженерное образование и наука в мировом пространстве (GEER)», (г. Томск, ТПУ, 1 -2 июня 2006 г.).

Объем и структура диссертации

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

Заключение диссертация на тему "Теория и алгоритмы обработки рекурсивных информационных структур"

4.4. Выводы

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

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

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

4. С целью проектирования схемы базы данных для предметной области, содержащей рекурсивные структуры, был разработан новый программный комплекс «RecModel 1.0». Данный программный комплекс является универсальным инструментом для решения задачи проектирования схемы баз данных с рекурсивно-определяемыми атрибутами и их автоматического отображения в стандартном реляционном описании. Комплекс ориентирован на широкий круг пользователей, в частности, на разработчиков баз данных и может использоваться в автономном режиме.

Заключение

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

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

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

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

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

5. Предложенные формализмы, алгоритмы обработки и разработанный программный комплекс использованы при проектировании предметной области «Информационная система менеджмента качества кафедры» в отделе Менеджмента качества Томского политехнического университета, при проектировании и модификации баз данных метеорологических параметров атмосферы в системах «ТОР-станция» и «Аэрозольная станция» в Институте ошики атмосферы СО РАН (г. Томск), при разработке программною комплекса «Управление основным производством» для ОАО «ТЭЛЗ» (г. Томск), а также могут быть использованы при проектировании схемы базы данных «Профили компетентности специалистов» в компании «ЭлеСи» (г. Томск).

Рекомендации по использованию результатов диссертационной работы:

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

2. Разработанный программный комплекс «RecModel 1.0» может быть использован при проектировании схем баз данных с рекурсивно-определяемыми атрибутами в экономических, медицинских, химических и других предметных областях.

Библиография Соколова, Вероника Валерьевна, диссертация по теме Системный анализ, управление и обработка информации (по отраслям)

1. Андреев, А. М. Среда и хранилище: ООБД / А. М. Андреев, Д. В. Березкин, Ю. А. Кантонистов // Мир ПК. 1998. - №4. - С. 74 - 81.

2. Архипенков, С. Хранилища данных. От концепции до внедрения / С. Архипенков, Д. Голубев, О. Максименко. М.: Диалог-МИФИ, 2002. - 528 с.

3. Атре, Ш. Структурный подход к организации баз данных / Ш. Атре. -Пер. с англ. М.: Финансы и статистика, 1983. - 317 с.

4. Аткинсон, М. Манифест систем объектно-ориентированных баз данных / М. Аткинсон // Системы Управления Базами Данных. 1995. - №4. - С. 142155.

5. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. - 536 с.

6. Ахо, А. Структуры данных и алгоритмы / А. Ахо, Дж. Хопкрофт, Дж. Ульман. Пер. с англ. - М.: Вильяме, 2001. - 384 с.

7. Ахо, А. Компиляторы: принципы, технологии и инструменты / А. Ахо, Р. Сети, Дж. Ульман. М. : Вильяме, 2001. - 768 с.

8. Ахо, А. Теория синтаксического анализа, перевода и компиляции. В 2 т. Т. 1. Синтаксический анализ / А. Ахо, Дж. Ульман. М.: Мир, 1978. - 612 с.

9. Баженова, И. Ю. Основы проектирования приложений баз данных / И. Ю. Баженова. М.: ИНТУИТ, 2006. - 320 с.

10. Барон, Д. Рекурсивные методы в программировании. Математическое обеспечение ЭВМ / Д. Барон. Перевод с англ. - М.: Мир, 1974. - 80 с.

11. Барендрегт, X. Лямбда-исчисление. Его синтаксис и семантика / X. Барендрегт. М.: Мир, 1985. - 608 с.

12. Братчиков, И. JI. Синтаксис языков программирования / И. J1. Братчиков. М.: Мир, 1975. - 232 с.

13. Вирт, Н. Алгоритмы и структуры данных / Н. Вирт. Пер. с англ. -СПб.: Невский диалект, 2001. - 352 с.

14. Вольфенгаген, В. Э. Реляционные методы проектирования банков данных / В. Э. Вольфенгаген, J1. Т. Кузин, В. И. Саркисян. Киев : Наука, 1979.-420 с.

15. Гаврилова, Т. Базы знаний интеллектуальных систем: учебник для вузов / Т. Гаврилова, В. Хорошевский. СПб.: Питер, 2000. - 384 с.

16. Гарсиа-Молина, Г. Системы баз данных. Полный курс / Г. Гарсиа-Молина, Дж. Ульман, Дж. Уидом. М.: Вильяме, 2003. - 1088 с.

17. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах / Д. Гасфилд. СПб.: БХВ-Петербург, 2003 - 654с.

18. Гинзбург, С. Математическая теория контекстно-свободных языков / С. Гинзбург. М.: Мир, 1970. - 326 с.

19. Гладкий, А. В. Формальные грамматики и языки / А. В. Гладкий. М. : Наука, 1983.-368 с.

20. Городняя, J1. В. Основы функционального программирования / JI. В. Городняя. М.: ИНТУИТ, 2004. - 280 с.

21. Гросс, М. Теория формальных грамматик / М. Гросс, А. Лантен. М. : Мир, 1971.-294 с.

22. Грис, Д. Наука программирования / Д. Грис. М.: Мир, 1984. - 416 с.

23. ГОСТ Р ИСО 9000-2001 Системы менеджмента качества. Основные положения и словарь. М.: ИПК Издательство стандартов, 2001. - 25 с.

24. Дал, У. Структурное программирование. Математическое обеспечение ЭВМ / У. Дал, Э. Дейкстра, К. Хоор. Пер. с англ. - М.: Мир, 1975. - 247 с.

25. Дейт, К. Дж. Руководство по реляционной СУБД DB2 / К. Дж. Дейт. -М.: Финансы и статистика, 1988г. 320 с.

26. Дейт, К. Дж. Введение в системы баз данных. 7-е изд., перераб. и доп. - / К. Дж. Дейт. - М.: Вильяме, 2001. - 1072 с.

27. Дейт К. Дж. Основы будущих систем баз данных: третий манифест / К. Дж. Дейт, X. Дарвен. М.: Янус-К, 2004. - 656 с.

28. Джексон, Г. Проектирование реляционных баз данных для пользователя с микроэвм / Г. Джексон. М.: Мир, 1991. - 245 с.

29. Деминг, У. Э. Лекция перед японскими менеджерами в 1950 г. / У. Э. Деминг // Методы менеджмента качества. 2000. - № 10. - С. 24-29.

30. Деминг, У. Э. Выход из кризиса / У. Э. Деминг. Тверь : Альба, 1994. -498 с.

31. Диго, С. М. Проектирование и использование баз данных / С. М. Диго. -М.: Финансы и статистика, 1983. 208 с.

32. Дрибас, В. П. Реляционные модели баз данных / В. П. Дрибас. Минск : БГУ им. Ленина, 1982.-191 с.

33. Замулин, А. В. Системы програмирования баз данных и знаний / А. В. Замулин. Новосибирск : Наука, 1990. - 350 с.

34. Зубов, В. С. Справочник программиста. Базовые методы решения графовых задач и сортировки / В. С. Зубов. Пер. с англ. - М.: Филинъ, 1999. -256 с.

35. Иванов, А. Ю. Основы построения и проектирования реляционных баз данных / А. Ю. Иванов, И. Б. Саенко. СПб : ВАС, 1998. - 80 с.

36. Илюшин, А. И. Многоуровневая модель архитектуры БД и ИПС / А. И. Илюшин, В. И. Филлипов //Программирование. 1980. - № 6. - С. 7-28.

37. Карпов, Ю. Г. Теория алгоритмов и автоматов / Ю. Г. Карпов. СПб. : Геликон Плюс, 2000. - 256 с.

38. Катленд, Н. Вычислимость. Введение в теорию рекурсивных функций / Н. Катленд. Пер. с англ. - М.: Мир, 1983. - 256 с.

39. Качалов, В. А. Стандарты ИСО 9000 и проблемы управления качеством в вузах (записки менеджера качества) / В. А. Качалов. М. : ИздАТ, 2001. -128 с.

40. Когаловский, М. Р. Энциклопедия технологий баз данных / М. Р. Когаловский. М.: Финансы и статистика, 2002. - 800 с.

41. Когаловский, М. Р. Перспективные технологии информационных систем / М. Р. Когаловский. М.: ДМК-Пресс, 2003. - 288с.

42. Коннолли, Т. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. 3-е изд., перераб. и доп. - / Т. Коннолли, К. Бегг. - М.: Вильяме, 2003. - 1436 с.

43. Кнут, Д. Искусство программирования для ЭВМ. В 3 т. Т.1. Основные алгоритмы / Д. Кнут. М.: Мир, 1976. - 453 с.

44. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. М.: Мир, 1978. - 432 с.

45. Крюков, А. П. Программирование на языке R-Лисп / А. П. Крюков, А. Я. Родионов, А. Ю. Таранов, Е. М. Шаблыгин. М.: Радио и связь, 1991. - 192 с.

46. Кузнецов, С. Д. Основы баз данных. Курс лекций: учебное пособие / С. Д. Кузнецов М.: ИНТУИТ, 2005. - 488 с.

47. Кузнецов, С. Д. Базисные средства манипулирования реляционными данными, или На чем базируются языки запросов / С. Д. Кузнецов // Системы управления базами данных. 1995. - № 3. - С. 114-122.

48. Кузнецов, С. Д. Методы оптимизации выполнения запросов в реляционных СУБД / С. Д. Кузнецов // Вычислительные науки. Т. 1. Итоги науки и техники ВИНИТИ АН СССР. М. : ВИНИТИ АН СССР, 1989. - С. 76-153.

49. Кудрявцев, В. Б. Введение в теорию конечных автоматов / В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. М.: Наука, 1975. - 320 с.

50. Кормен, Т. Алгоритмы: построение и анализ Пер. с англ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. - М.: Вильяме, 2005. - 1296 с.

51. Котов, В. М. Структуры данных и алгоритмы: теория и практика / В. М Котов, Е. П. Соболевская. Минск.: БГУ, 2004. - 255с.

52. Лавров, С. С. Программирование. Математические основы, средства, теория / С. С. Лавров М. : Наука, 2000. - 317 с.

53. Лавров, С. С. Автоматическая обработка данных. Язык ЛИСП и его реализация / С. С. Лавров, Г. С. Силагаде. М.: 11аука, 1978. - 176 с.

54. Макконнел, Дж. Анализ алгоритмов. Вводный курс / Дж. Макконнел. -Пер. с англ. М.: Техносфера, 2002. - 304 с.

55. Малыхина, М. Базы данных: основы, проектирование, использование: учебное пособие / М. Малыхина. СПб.: БХВ-Петербург, 2003. - 512 с.

56. Марков, А. С. Базы данных. Введение в теорию и методологию / А. С. Марков, К. Ю. Лисовский. М.: Финансы и статистика, 2004. - 512 с.

57. Мартин, Дж. Организация баз данных в вычислительных системах / Дж. Мартин. М.: Мир, 1980. - 662 с.

58. Маурер, У. Введение в программирование на языке Лисп / У. Маурер. -Пер. с англ. М.: Мир, 1976. - 102 с.

59. Мейер, Д. Теория реляционных баз данных / Д. Мейер. Пер. с англ. -М.: Мир, 1987.-608 с.

60. Мелихов, А. Н. Ориентированные графы и конечные автоматы / А. Н Мелихов. М.: Наука, 1971. - 416 с.

61. Мескон, М. X. Основы менеджмента / М. X. Мескон, М. Альберт, Ф. Хедоури. Пер. с англ. - М.: Дело, 2000. - 704 с.

62. Новосельцев, В. Б. Теория структурных функциональных моделей / В. Б. Новосельцев // Сибирский математический журнал. 2006. - Т. 47. - № 5. -С. 1014-1030.

63. Нив, Г. Р. Пространство доктора Деминга / Г. Р. Нив. М. : МГИЭТ (ТУ), 1996.-344 с.

64. Опалева, Э. А. Технология программирования: учеб. пособие/ Э. А. Опалева, В. П. Самойленко С.-Пб.: BHV, 1995. - 480 с.

65. Райли, Д. Д. Абстракция и структуры данных: Вводный курс / Д. Д. Райли. Пер. с англ. - М. : Мир, 1993. - 750 с.

66. Райордан, Р. Основы реляционных баз данных / Р. Райордан. М. : Русская Редакция, 2001. - 384 с.

67. Ревунков, Г. И. Базы и банки данных и знаний: учеб. для вузов / Г. И. Ревунков, Э. Н. Самохвалов, В. В. Чистов М.: Высшая школа, 1992. - 367 с.

68. Роб, П. Системы баз данных: проектирование, разработка и использование /11. Роб, К. Коронел. СПб.: БХВ-Петербург, 2003. - 1200 с.

69. Савицкий, Н. И. Технологии организации хранения и обработки данных / Н. И. Савицкий. М.: Инфра-М, 2001. - 232 с.

70. Саймон, А. Р. Стратегические технологии баз данных / А. Р. Саймон. -Пер. с англ. М.: Финансы и статистика, 1999. - 479 с.

71. Стивене, Р. Программирование баз данных / Р. Стивене М. : Бином, 2003.-384 с.

72. Тиори Т. Проектирование структур баз данных: в 2-х кн. Пер. с англ. / Т. Тиори, Дж. Фрай - М.: Мир, 1985. - 2 кн.

73. Тужилов, И. В. Программирование на языке XLISP: учеб. пособие / И. В. Тужилов. Пенза : Изд-во Пенз. гос. техн. ун-та, 1996. - 80 с.

74. Уинстон, П. Искусственный интеллект / П. Уинстон. М. : Мир, 1980. -520 с.

75. Ульман, Дж. Основы систем баз данных / Дж. Ульман. М. : Финансы и статистика, 1983. - 334 с.

76. Ульман, Дж. Введение в системы баз данных / Дж. Ульман, Дж. Уидом -М.: Лори, 1999.-376 с.

77. Уоррен, Г. Алгоритмические трюки для программистов / Г. Уоррен. -Пер. с англ. М.: Вильяме, 2003. - 288 с.

78. Успенский, В. А. Теория алгоритмов: основные открытия и приложения / В. А. Успенский, А. Л. Семенов М.: Физматгиз, 1987. - 298 с.

79. Федоров А. Г. Базы данных для всех / А. Г. Федоров, Н. 3. Елманова. -М. : КомпьютерПресс, 2001. 256 с.

80. Филд, А. Функциональное программирование / А. Филд, П. Харрисон -Пер. с англ. М.: Мир, 1993. - 637 с.

81. Хансен, Г. Базы данных. Разработка и управление / Г. Хансен, Дж. Хансен. М.: Бином, 2001. - 704 с.

82. Харрингтон, Дж. Проектирование реляционных баз данных. Просто и доступно/ Дж. Харрингтон. М.: Лори, 2000. - 230 с.

83. Хоггер, К. Введение в логическое программирование / К. Хоггер. М.: Мир, 1988.-348 с.

84. Хопкрофт, Дж. Э. Введение в теорию автоматов, языков и вычислений, 2-е изд. / Дж. Э. Хопкрофт, Р. Мотвани, Дж. Д. Ульман. М. : Вильяме, 2002. -528 с.

85. Хендерсон, П. Функциональное программирование. Приложение и реализация / П. Хендерсон. Пер. с англ. - М.: Мир, 1983. - 349 с.

86. Хювеннен, Э. Мир Лиспа. В 2-х т. Т.1 : Введение в язык Лисп и функциональное программирование / Хювеннен Э., Сеппянен Й. Пер. с финск. - М.: Мир, 1990. - 447 с.

87. Хювеннен, Э. Мир Лиспа. В 2-х т. Т.2 : Методы и системы программирования / Хювеннен Э., Сеппянен Й. Пер. с финск. - М. : Мир, 1990.-319 с.

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

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

90. Чекалов, А. Базы данных: от проектирования до разработки приложений. Серия «Мастер программ» / А. Чекалов СПб.: БХВ-Петербург, 2003.-384 с.

91. Чемберлин, Д. Анатомия объектно-реляционных баз данных / Д. Чемберлин // Системы Управления Базами Данных. 1998. - № 1 -2. - С. 3-24.

92. Чен, П. Модель «сущность-связь» шаг к единому представлению о данных / П. Чен // Системы Управления Базами Данных. - 1995. - №3. - С. 137-158.

93. Черч, Л. Введение в математическую логику / А. Черч. М. : Изд-во иностранной литературы, 1960. - 488 с.

94. Шень, А. Программирование: Теоремы и задачи / А. Шень. М. : Наука, 2004. - 296 с.

95. Abiteboul, S. Towards a deductive object-oriented database language / S. Abiteboul // Data and Knowledge Eng. -1990. № 5. - P. 263-287.

96. Alashqur, A. M. A rule-based language for deductive object-oriented databases / A. M. Alashqur, S. Y. W. Su, H. Lam // 6th Int. Conf. Data Eng., Los Angeles, Calif., USA, Febr. 5-9, 1990. P. 58-67.

97. Beeri, C. A formal approach to object-oriented databases / Catriel Beeri // Data and Knowledge Eng. 1990. - № 5 - P. 353-382.

98. Bottcher, S. Attribute inheritance implemented on top of a relational database system / Stefan Bottcher // 6th Int. Conf. Data Eng., Los Angeles, Calif., USA, Febr. 5-9, 1990.-P. 503-509.

99. Chakravarthy, S. Making an object-oriented DBMS active: design, implementation, and evaluation of a prorotype / Sharma Chakravarthy, Susan Nesson // Advances in Database Technology EDBT'90. Lecture Notes in Computer Science. - 1990. - P. 393-406.

100. Chamberlin, D. D. A history and evaluation of System R / D. D. Chamberlin, M. M. Astrahan et al. // Commun. ACM. 1982. - № 10. - P. 632-646.

101. Ceri, S. Algres: An advanced database system for complex applications / Stefano Ceri, Stafano Crespi-Reghizzi, Roberto Zicari, Gianfranco Lamperti, Luigi A. Lavazza // IEEE Software. 1990. - № 4. p. 68-78.

102. Codd, E. F. Providing OLAP (On-Line Analytical Processing) to user-analysts: an IT Mandate / E. F Codd, S. B. Codd, С. T. Sal ley //CACM. 1993. - P. 223-354.

103. Codd, E. F. A relation model of data for large shared data banks / E. F Codd //Communication of the ACM, v.13. 1970. -№ 6. - P. 337-387.

104. Decouchart, D. Design of a distributed object manager for the Smalltalk-80 System / D. Decouchart // Proc. OOPCLA'86, Portland, Oreg., USA, Sept. 29 Oct. 2.-1986.-P. 444-452.

105. Fishman, D. H. An overview of the Iris object-oriented DBMS / D. H. Fishman // Digest of papers, 33rd CompCon, Spring 1988, Feb. 29 Mar. 4, USA. -1988.-P. 177-180.

106. Garvey, M. A. Introduction to object-oriented databases / M. A. Garvey, M. S. Jackson // Inf. and Software Technol.- 31.-1989. № 10. - P. 521 -528.

107. Haas, L. Starburst mid-flight: as the dust clears / Laura Haas, Walter Chang // IEEE Trans. Knowledge and Data Eng.- 2. 1990. -№ 1. - P. 143-159.

108. Kim, W. A model of queries for object-oriented databases / W. Kim // 15th Int. Conf. Very Large Data Bases, Amsterdam, Aug. 22-25. 1989. - P. 423-432.

109. Lee, K. An object-oriented approach to data/Knowledge Modelling Based on Logic / Kyuchul Lee, Sukho Lee // 6th Int. Conf. Data Eng., Los Angeles, Calif., USA, Febr. 5-9. 1990. - P. 289-294.

110. Maier, D. Development of an Object-Oriented DBMS / David Maier, Jacob Stein, Allen Otis, Alan Purdy // Proc. OOPCLA'86, Portland, Oreg., USA, Sept. 29 -Oct. 2.- 1986.-P. 472-482.

111. Rapaport, M. Object-Oriented Data Bases: the next step in DBMS evolution / Mattbew Rapaport // Сотр. Lang.- 5.- 1988. -№ 10. P. 91-98.

112. Rowe, L. The POSTGRES data model / L. Rowe, M. Stonebraker // 13th Int. Conf. Very Large Data Bases, Brighton, England, Sept. 1-4. 1987. - P. 83-96.

113. Roussopoulus, N. ROOST: A relational object-oriented system / Nick Roussopoulus, Hyun Soon Kim // Lect. Notes Comput. Sci.- 367. 1989. - P. 404420.

114. R., P. van de Riet. Introduction to the special issue on deductive and object-oriented databases / R. P. van de Riet // Data and Knowledge Eng.- 5. 1990. - P. 255-261.

115. Scott, H. Cactis: a self-adaptive, concurrent implementation of an object-oriented database management system / Hudson Scott, Roger King // ACM Trans. Database SySt.- 14. 1989. -№ 3. - P. 291-321.

116. Stonebraker, M. The design of the POSTGRES storage system / Michael Stonebraker // 13th Int. Conf. Very Large Data Bases, Brighton, England, Sept. 1-4.- 1987.-P. 289-300.

117. Stonebraker, M. Future trends in database systems / Michael Stonebraker // IEEE Trans. Knowledge and Data Eng.- 1. № 1. - 1989. - P. 33-44

118. Straw, A. Object management in a persistent Smalltalk system / Andrew Straw, Fred Mellender, Steve Riegel // Software Pract. and Exper.- 19. 1989. - № 8.-P. 719-737.

119. Shaw, Gail M. A query algebra for object-oriented databases / Gail M. Shaw, Stanley B. Zdonik // 6th Int. Conf. Data Eng., Los Angeles, Calif., USA, Febr. 5-9.- 1990.-P. 154-162.

120. Zicari, R. Incomplete information in object-oriented databases / Roberto Zicari // ACM SIGMOD Record.- 19.- 1990.-№ 3.-P. 5-16.