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

• Соколова, Вероника Валерьевна
• кандидат технических наук
• 2006

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

Введение.

Глава 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. Выводы

Введение диссертации (часть автореферата) на тему «Теория и алгоритмы обработки рекурсивных информационных структур»

Базы данных (БД) являются важным инструментом построения информационных систем, используемых в производстве, бизнесе и научной деятельности. Большинство коммерческих систем управления базами данных (СУБД) поддерживает обработку плоских таблиц согласно реляционной модели данных, разработанной Коддом в семидесятых годах прошлого столетия [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» может быть использован при проектировании схем баз данных с рекурсивно-определяемыми атрибутами в экономических, медицинских, химических и других предметных областях.

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

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.