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

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

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

КРАСНОВ ВЯЧЕСЛАВ НИКОЛАЕВИЧ

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

УРОВНЕ.

Специальность: 05.13.11 - Математическое и программное обеспечение

вычислительных машин, комплексов, систем и сетей.

Диссертация

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

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

профессор, чл.-корр. Международной академии информатизации БАШМАКОВ И.А.

Москва - 1998

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ................................................................................................................6

ГЛАВА 1. ЗАДАЧА ИЗВЛЕЧЕНИЯ И ИЗМЕНЕНИЯ ИНФОРМАЦИИ В ПРОЦЕССЕ ОБСЛУЖИВАНИЯ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ...............................12

1.1. Языки запросов................................................................................12

1ЛЛ. Реляционная алгебра............................................................................15

1.1.2. Язык запросов ALFA...........................................................................16

1Л.З. Язык запросов QUEL..........................................................................17

1Л.4. Язык запросов Structured Query Language (SQL).............................17

1Л.5. Язык запросов Query-by-Example (QBE)...........................................21

1Л.6. Подходы к обеспечению логической независимости данных........26

1.2. Нерешенные проблемы в современных средствах выполнения запросов к реляционной БД (РБД)...................................................................................34

1.2Л. Обеспечение логической независимости данных.............................34

1.2.2. Снижение сложности описания запросов к подчиненным файлам (отношение 1:М)....................................................................................................35

1.2.3. Проблема поддержания многообразия возможных связей таблиц.36

1.2.4. Автоматизация каталогизации запросов и подзапросов..................37

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

1.2.6. Уменьшение затрат на корректировку данных в табличном представлении..........................................................................................................38

1.3. Задачи, вытекающие из цели работы.................................................38

1.3.1. Общие требования к языкам запросов..............................................39

1.3.2. Поддержка реляционной алгебры......................................................40

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

1.3.4. Упрощение описания запросов к подчиненным файлам (отношение 1:М)....................................................................................................41

1.3.5. Поддержание многообразия возможных связей таблиц...............42

1.3.6. Каталогизация запросов и подзапросов.............................................42

1.3.7. Снижение требований к ресурсам вычислительной системы на этапе выполнения запроса.....................................................................................43

1.3.8. Редактирование базы данных..............................................................43

1.3.9. Наличие алгоритма получения сложного отчета по БД..................43

1.4. Выводы по первой главе....................................................................43

ГЛАВА 2. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ ВНЕШНЕЙ МОДЕЛИ ДАННЫХ -РЕЛЯЦИОННОЙ ЭЛЕКТРОННОЙ ТАБЛИЦЫ (РЕЭЛТ)..............................................46

2.1. Понятие РЕЭЛТ и ее математическое описание.................................47

2.2. Удовлетворение языком запросов РЕЭЛТ требований, предъявляемых к сверхвысокоуровневому языку запросов...........................................................68

2.2.1 Удовлетворение языком запросов РЕЭЛТ общих требований, предъявляемых к высокоуровневому языку запросов........................................68

2.2.2. Поддержка языком запросов РЕЭЛТ реляционной алгебры..........72

2.2.3. Работа пользователя с языком запросов РЕЭЛТ на логически независимом уровне................................................................................................74

2.2.4. Упрощение описания запросов к подчиненным таблицам (отношение 1:М)....................................................................................................75

2.2.5 Поддержка многообразия возможных связей таблиц....................76

2.2.6 Каталогизация запросов и подзапросов..............................................78

2.2.7 Снижение требований к ресурсам вычислительной системы на этапе выполнения запроса.....................................................................................80

2.2.8 Редактирование БД посредством РЕЭЛТ...........................................80

2.2.9 Алгоритм получения сложного отчета по БД....................................81

2.3. Выводы по второй главе....................................................................82

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РЕЭЛТ..............................................84

3.1. Место РЕЭЛТ в архитектуре АБнД и основные требования к программной реализации РЕЭЛТ.....................................................................84

3.2. Структура репозитория......................................................................88

3.2.1. Словарь...................................................................................................89

3.2.2. Дерево связей таблиц (схема представления файлов БД для РЕЭЛТ)...................................................................................................................100

3.2.3. Общая схема представления БД для РЕЭЛТ..................................102

3.2.4. Выражения языка запросов РЕЭЛТ (условие выборки, выражение сортировки, значение запроса, условие запроса).............................................102

3.2.5. Файл описания меню файлов, файл описания меню справочников и файл описания меню процедур.......................................................................103

3.3. Функции и процедуры инструментального средства............................105

3.3.1. Процедура загрузки инструментального средства..........................105

3.3.2. Менеджер процедур инструментального средства.........................106

3.3.3. Поддержка и описание меню выборок, меню отчетов, меню запросов и меню наборов запросов....................................................................108

3.3.4. Функция формирования выражения................................................109

3.3.5. Процедура добавления записи в экране специального редактирования......................................................................................................109

3.3.6. Процедура специального редактирования записи файла..............110

3.3.7. Процедура вызова меню файлов, меню справочников и меню процедур пользователя..........................................................................................110

3.3.8. Процедура корректировки справочников........................................111

3.3.9. Процедура удаления записей в подчиненных файлах...................111

3.3.10. Процедура сохранения удаляемых упаковкой записей..............112

3.3.11. Процедура обработки нажатия клавиши ENTER в поле редактирования......................................................................................................112

3.3.12. Функция выбора значения поля из справочника.........................113

3.3.13. Схема вызова процедур инструментального средства..................113

3.3.14. Настройка параметров системы.....................................................114

3.3.15. Дополнительные возможности для проектировщика..................115

3.4. Сверхвысокоуровневый язык программирования пользовательского интерфейса (ЯПС ИП) РБД..........................................................................117

3.5. Сверхвысокоуровневый язык запросов для определения РЕЭЛТ (ЯЗ РЕЭЛТ) конечного пользователя....................................................................123

3.5. Выводы по третьей главе..................................................................124

ГЛАВА 4. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ И ПРОГРАММНЫЕ

ЭКСПЕРИМЕНТЫ.........................................................................................................127

4.1. Алгоритм настройки РЕЭЛТ для получения отчета............................127

4.2. Примеры РЕЭЛТ.............................................................................128

4.2.1. Предметная область............................................................................128

4.2.2. Реализованные РЕЭЛТ в рассмотренной предметной области.... 132

4.3. Сравнение характеристик практических реализаций языков...............144

4.3.1. Сравнение функциональных характеристик...................................144

4.3.2. Сравнение количественных характеристик.....................................147

4.4. Выводы по четвертой главе..............................................................149

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ......................................................153

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

ПРИЛОЖЕНИЕ 2...................................................................................................159

ПРИЛОЖЕНИЕ 3...................................................................................................160

ПРИЛОЖЕНИЕ 4...................................................................................................165

ПРИЛОЖЕНИЕ 5...................................................................................................165

ПРИЛОЖЕНИЕ 6...................................................................................................166

ПРИЛОЖЕНИЕ 7...................................................................................................169

ПРИЛОЖЕНИЕ 8...................................................................................................169

ПРИЛОЖЕНИЕ 9...................................................................................................170

ПРИЛОЖЕНИЕ 10.................................................................................................170

ПРИЛОЖЕНИЕ 11.................................................................................................170

ПРИЛОЖЕНИЕ 12.................................................................................................171

ПРИЛОЖЕНИЕ 13.................................................................................................171

ПРИЛОЖЕНИЕ 14.................................................................................................172

ВВЕДЕНИЕ

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

В этой сфере работы отечественных и зарубежных ученых направлены на облегчение взаимодействия пользователя с языком запросов [2,3,4,6,9].

Наиболее распространены системы, использующие реляционную модель данных [10]. Первой проблемой является необходимость обеспечения независимости данных от обрабатывающих их программ (отделение информационной структуры от физического представления). Различают два уровня независимости данных: физическую и логическую. Физическая независимость - независимость прикладных программ, внешних и концептуальной схем от физической организации данных. Предполагает, что любые изменения, вносимые в данные, не требуют коррекции этих программ и схем. Логическая независимость - независимость прикладных программ от данных, определенных на логическом уровне. Предполагается, что любые изменения в концептуальной схеме не требуют коррекции этих программ [65].

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

СУБД взяло на себя работу с информацией на физическом уровне. Логическая организация обычно сильно отличается от способа организации и обработки файлов (физической организации). Попытки обеспечения логической независимость данных свелись к введению понятия универсального отношения и созданию двухзвенного (управляющий/пользователь) стиля администрирования языком запросов [2,3,9]. Комиссия Аш^Брагс предложила трехуровневую схему доступа пользователей к данным. Схема содержит два отображения: внешнее представление пользователей на концептуальную модель и концептуальную модель на физическое представление.

В реляционных СУБД обычно используются языки запросов SQL и QBE [9,10,16,17,19,20]. Для обеспечения простоты описания запросов для конечного пользователя создаются надстройки над языками запросов, называемые инструментальными средствами работы с высокоуровневыми языками запросов [9].

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

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

- определяющих атрибуты нового отношения;

- задающих условие отбора кортежей для нового отношения;

- определяющих группировку кортежей нового отношения.

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

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

- сохранения описаний отчетов;

- сохранение описаний выражений команд селекции.

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

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

Удобным является наличие преемственности описаний.

Однако проблема работы пользователя с языком запросов на логически независимом уровне осталась нерешенной. В лучшем случае проблема логической независимости данных решается в инструментальных средствах введением двухзвенного стиля администрирования - управляющий / пользователь. Управляющий обязательно должен знать структуру концептуальной схемы БД и работает с БД на уровне реляционной СУБД. Конечный пользователь работает на уровне абстракции, который, в некоторой степени, можно назвать логически независимым. Операторы реляционной алгебры, SQL и QBE требуют указания имен отношений и атрибутов в терминах концептуальной схемы. Говорить о работе пользователя в терминах внешней схемы не приходится. Проблема логической независимости данных для пользователя языком запросов реляционной БД (РБД) не решена. Трехуровневая схема доступа к данным SQL исчерпала свои возможности по оптимизации извлечения информации из РБД и требует значительных затрат ресурсов вычислительной системы на этапе выполнения запроса. В существующей математической модели не было удачных попыток решения проблемы с одновременным обеспечением логической независимости, простоты описания запросов на уровне управляющего и снижением требований к ресурсам вычислительной системе на этапе выполнения запроса. Это определяет актуальность темы диссертации.

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

Из темы вытекают следующие задачи исследования и разработки:

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

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

- разработка алгоритма реализации языка запросов;

- программная реализация языка запросов;

- проведение программных экспериментов на практически значимых задачах.

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

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

Во второй главе описана новая внешняя модель данных, названная реляционной электронной таблицей (РЕЭЛТ). Дано математическое описание РЕЭЛТ и ее отображения (представления БД для РЕЭЛТ) в концептуальную схему. Даны решения поставленных задач.

В третьей главе приведено описание программной реализации языка запросов. Определена структура репозитория. Перечислены основные функции и процедуры инструментального средства.

Четвертая глава содержит описание практического использования и программных экспериментов.

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

1. Сформулированы требования к сверхвысокоуровневому языку запросов конечного пользователя.

2. Создана новая внешняя модель данных, названная реляционной электронной таблицей (РЕЭЛТ). Дано математическое описание РЕЭЛТ и ее отображения (представления БД для РЕЭЛТ) в концептуальную схему.

3. Разработана типология запросов, формирующих РЕЭЛТ, и разработаны алгоритмы их выполнения.

4. Определены следующие классы РЕЭЛТ: представление реляционной электронной таблицы (представление таблицы), полное представление таблицы, сокращенное представление полного представления таблицы.

5. Разработана интерактивная процедура формирования пользователем запросов на логически независимом уровне - в терминах предметной области.

6. Разработан алгоритм получения сложного отчета по БД.

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

Реализован интерпретатор сверхвысокоуровневого языка программирования (ЯПС) пользовательского ин