Содержание к диссертации
Введение
1. Модели представления структур баз данных: и организация оптимальной обработки данных 8
1.1. Семантические модели представления предметной области 9
1.2. Реляционная схема БД 13
1.3 Семантические ограничения и интерфейс обращения в реляционных и объектно-реляционных системах 18
1.4. Математические основы операций обработки информации. Преобразование и оптимизация запросов 21
2. Расширяемая структура данных информационной системы учета объектов региональной сети связи 36
2.1. Система учета объемных показателей и структуры сети электросвязи 36
2.2. Разработка расширяемой схемы базы данных 45
2.3. Объектно-ориентированный и реляционный интерфейсы работы с данными 62
2.4. Использование расширяемой модели в информационной системе для управления объектами сети связи. 71
2.5. Выводы 75
3. Альтернативная формализация реляционного исчисления. Критерий оптимальности запроса в непроцедурной форме 79
3.1. Альтернативная формализация реляционного исчисления 79
3.2. Критерий оптимальности непроцедурной формы запроса 83
3.3. Выводы 92
4. Логическая оптимизация различных классов запросов в рамках реляционной модели 93
4.1. Оптимизация класса запросов, содержащих операцию разности 93
4.2. Оптимизация класса дизъюнктивных запросов 103
4.3. Выводы 112
5. Разработка расширяемой структуры данных и оптимизация запросов в информационно-управлящих системах 114
5.1. Расширение структуры базы данных в системе "Связь-Глобальная" 114
5.2. Алгоритм оптимизации запросов разности в информационной системе "Связь-Глобальная" 120
5.3. Алгоритм оптимизации дизъюнктивных запросов в информационной системе "Связь-Глобальная" 124
5.4. Выводы 129
Заключение 130
Список литературных источников 128
Приложения 138
- Семантические модели представления предметной области
- Система учета объемных показателей и структуры сети электросвязи
- Альтернативная формализация реляционного исчисления
- Оптимизация класса запросов, содержащих операцию разности
Введение к работе
Актуальность. В современных автоматизированных системах управления производственными процессами динамично развивающихся предприятий постоянно растет объем и степень детализации данных. Это влечет за собой появление в информационных структурах новых параметров и объектов новых типов.
Большинство существующих информационных систем имеет существенные недостатки, связанные с задачей представления развивающейся предметной области и трудоемкостью соответствующего расширения функциональности системы. Традиционные способы проектирования структуры представления данных оказываются неэффективными для решения данной задачи из-за чрезмерного увеличения и усложнения структуры базы данных (БД) и ее регулярной модификации. Это не только усложняет процесс разработки информационной схемы, но и делает созданную систему заведомо ограниченной и негибкой.
Известно, что эффективность функционирования информационных систем наряду с удачной организацией схемы базы данных во многом определяется оптимальным выполнением запросов, на основе которых осуществляется обработка данных. При этом логическая оптимизация является универсальным инструментом, не зависящим от конкретной системной платформы. Однако, традиционным направлением в этой области является оптимизация конъюнктивных SPJ-запросов (Select-Project-Join), связанных с композициями из ограниченного перечня операций над отношениями.
Таким образом, актуальной является разработка технологии проектирования расширяемой структуры базы данных, реализующей независимое представление структурных связей и параметров производственных объектов, средств логической оптимизации запросов, выходящих за рамки SPJ, а также гибкого интерфейса доступа к данным, учитывающего специфику расширяемой схемы.
Работа выполнена в соответствии с научным направлением ЛГТУ "Современные сложные системы управления".
Цель исследования состоит в решении комплекса задач, связанных с совершенствованием технологии проектирования информационных систем, учитывающей развитие и изменение производственных объектов и предметной области в целом.
Задачи исследования: разработать методику формирования структуры данных в информационной системе для управления производственными процессами, отражающей разнородные объекты предметной области однородными структурными единицами; разработать интерфейс доступа к базе данных с расширяемой структурой в информационной системе управления производственными объектами; - провести исследование логически эквивалентных вариантов запросов, f необходимых для обработки данных в информационно-управляющей системе, определить и обосновать выбор логического представления запроса для дальнейшей его оптимизации; - выявить и сформулировать критерии оптимальности запросов к данным производственных объектов, представленных в логической непроцедурной форме; с - разработать алгоритмы логической оптимизации для классов запросов, не входящих в класс SPJ.
Методы исследования: использованы теория и методы проектирования информационных систем, баз данных, дискретной математики, логики высказываний и предикатов, а также объектно-ориентированно го анализа.
Научная новизна. В диссертационной работе получены следующие J результаты, характеризующиеся научной новизной: - разработана расширяемая структура базы данных информационной системы для управления производственными объектами, отличающаяся независимым представлением структурных связей и свойств объектов; разработан аппарат альтернативной формализации реляционного исчисления, отличающийся использованием области определения связанных переменных и непосредственным отражением семантики запросов языка SQL; разработан критерий оптимальности для эквивалентных реляционных выражений и запросов, отличающийся включением теоретико-множественных операций; разработан алгоритм оптимизации класса коррелированных запросов разности отношений путем преобразования к некоррелированному виду на основе аппарата реляционного исчисления; разработан алгоритм оптимизации класса дизъюнктивных запросов на основе декомпозиции исходного запроса на запросы с разделимыми конъюнктивными условиями.
Практическая значимость состоит в разработке методики и программного обеспечения, охватывающих задачи организации хранения и обработки данных с целью рационального управления производственными объектами.
Программные модули могут быть использованы в качестве надстройки в действующих информационных системах различных отраслей.
Реализация и внедрение результатов работы. Разработанные методы построения структуры данных и оптимизации запросов реализованы и внедрены при создании и расширении информационных систем "Липецкэлектросвязь" - филиала ОАО "ЦентрТелеком". Материалы по теме диссертации используются в Липецком государственном техническом университете при подготовке инженеров, бакалавров и магистров по специальностям "Автоматизированные системы обработки информации и управления" и "Прикладная математика".
Апробация работы. Основные положения работы докладывались и обсуждались на международной научно-практической конференции «Теория активных систем» (Москва-2003), на международной научно-технической конференции «Современные сложные системы управления CCCy/HTCS'2003» (Воронеж-2003), на международной конференции «Программное обеспечение автоматизированных систем управления (SAS-2000)» (Липецк-2000), на семинаре Липецкого регионального отделения Российской ассоциации искусственного интеллекта «Методы и модели искусственного интеллекта» (Липецк-2003).
Положения работы поддержаны грантами по фундаментальным исследованиям:
Министерством образования РФ - Г00 4.1-68 "Разработка теории оптимизации проектирования информационных систем";
Российским фондом фундаментальных исследований - № 03-01-96487 "Оптимизация схем баз данных и запросов на основе теории преобразований реляционных выражений" и JSTa 03-01-96487 "Формализация алгоритма оптимизации реляционных запросов ".
Публикации. По результатам исследования опубликовано 8 печатных работ. В [2] и [29] автором разработан аппарат альтернативной формализации реляционного исчисления; в [28] формализованы правила преобразования семантики реляционных выражений в SQL-запросы; в [I] предложено применение разработанного формального аппарата при построении информационных систем; в [3] и [27] разработаны алгоритмы оптимизации коррелированных и дизъюнктивных запросов на основе преобразований выражений реляционного исчисления; в [26] приведена разработанная методика построения структур баз данных; в [30] разработан программный комплекс для оптимизации запросов, проведен сравнительный анализ с известными алгоритмами.
Структура и объем работы. Диссертационная работа состоит из пяти глав, введения, заключения, библиографического списка из І08 наименований, приложений; содержит 130 страниц основного текста, 25 рисунков, 12 таблиц.
Семантические модели представления предметной области
Основой для построения схемы базы данных является модель "сущность-связь" состоящая из двух базовых элементов: сущностей и связей между ними [47, 97]. Ее термины первоначально были определены в [46, 59] и получили развитие и уточнение в работах Чена и других исследователей [47, 105, 106].
В соответствии с работой [47], сущность представляет собой некоторый тип объекта, который может быть идентифицирован. Выделяют независимые стержневые сущности, и характеристические, находящиеся в зависимости от объектов других типов. Сущности обладают набором атрибутов характеристик объектов данного типа, для которых определены множества допустимых значений (домены). Свойство может быть простым или составным, ключевым, однозначным или многозначным, отсутствующим, базовым или производным.
В модели также определяются связи, как ассоциация объектов некоторых сущностей [47]. В рамках модели "сущность-связь" рассматриваются только бинарные связи между сущностями. Для сущностей, включенных в некоторую связь, выделяют обязательный и необязательный класс принадлежности. Обязательный класс принадлежности характерен для характеристических сущностей. По количественному соотношению объектов участвующих сущностей выделяются следующие типы связей: один-к-одному, один-ко-многим, многие-к-одному, многие-ко-многим. Подробное рассмотрение связей типа один-к-одному и их использования при описании предметной области приведено в работе К. Дейта [57].
Альтернативы подходу Чена к построению моделей "сущность-связь" изложены в [55, 76, 93, 101]. Обзоры работ по данной теме приведены также в [78, 96].
Модель "сущность-связь" представляет собой не только формализацию предметной области, но и метод представления логической структуры БД в графическом виде [48] для более простого и понятного выражения основных компонентов проекта БД. Существует несколько способов графического представления модели "сущность-связь" (см., например, [5]). Это определяет основное назначение данной модели при проектировании большинства информационных систем и ее использование в CASE-средствах [32, 33, 16]. В настоящее имеется достаточно работ, затрагивающих моделирование структуры БД средствами модели "сущность-связь" [65, 71, 89, 103, 104, 105].
К недостаткам модели следует отнести се недостаточную гибкость: рассмотрение в модели объектов нового типа приводит к появлению новой сущности и изменению имеющейся структуры связей, что в свою очередь выражается в изменении структуры базы данных. В работе [55] Э.Ф. Коддом были определены основные термины модели RM/T, которые получила в дальнейшем развитие в работах [100, 75, 58, 46, 104]. Для представления сущностей в модели используются два типа отношений — Е- и Р-отношения. Е-отпошсние служит для указания соответствия объекта некоторой сущности; Р-отношение (property-defining) содержит атомарные свойства (атрибуты) объектов данной сущности. В модели допускается принадлежность объекта нескольким сущностям одновременно.
Идентификация объектов осуществляется с использованием контролируемых системой и не изменяемых пользователем суррогатных первичных ключей (суррогатов). Принадлежность объекта различным сущностям определяется принадлежностью его суррогатного ключа соответствующим Е-отношсниям. На основе этого вводится особое ограничение целостности - целостность свойств — кортеж не может появиться в Р-отношении, если существование соответствующего объекта не декларировано в Е-отношении.
В модели рассматриваются следующие типы сущностей: - характеристические сущности, выполняющие вспомогательную роль в описании других сущностей; - ассоциативные сущности, определяющие взаимосвязи объектов других сущностей; - стержневые сущности, являющиеся самостоятельными и не выполняющие ни одну из вышеописанных функций. Характеристические сущности представляют реализацию многозначных свойств других сущностей, и могут характеризовать стержневую, ассоциативную или характеристическую сущность. Совокупность характеристических сущностей, описывающих некоторую стержневую [55], образуют строгую иерархию, названную характеристическим деревом. Ассоциативная сущность также может описывать связь стержневых, ассоциативных или характеристических сущностей. Рассматриваются обязательное или необязательное вхождение сущностей в ассоциацию.
Кроме того, выделяются несущностные ассоциации, характеризующие взаимосвязи сущностей, но сами не обладающие статусом сущности. Показано, что их использование не дает возможности вводить характеристические или ассоциативные сущности более низкого уровня.
В модели рассматриваются подтипы, супертипы [99, 100] и отношения обобщения. Рассматриваются отношения безусловного обобщения, при котором сущность является подтипом фиксированной сущности, и альтернативного обобщения, при котором сущность является подтипом одной из некоторого набора сущностей. Для определения связей альтернативного обобщения при создании объекта требуется дополнительно указать его принадлежность к одному из супертипов. Модель также представляет средства для представления временного измерения, сущностей типа событий и связей безусловного н альтернативного предшествования между ними. Модель содержит каталог, задающий формальное описание данных связей и порождаемые ими ограничения целостности.
Несмотря на то, что модель RM/T разрабатывалась как расширение модели "сущность-связь" и формальной реляционной модели представления данных, она не получила практического воплощения в системах управления базами данных. Из-за довольно большой сложности средств проектирования она также оказалась неэффективна для разработки информационных систем.
Система учета объемных показателей и структуры сети электросвязи
На предприятиях различных отраслей ставится задача построения информационной системы, отражающей основную структуру организационно-технологических связей подразделений и общее состояние и эффективность функционирования различных элементов технологического процесса. В рамках регионального оператора телефонной связи "Липецкэлектросвязь" - филиала ОАО "Центртелеком" одной из наиболее актуальных и востребованных является информационная система, отражающая структуру сети связи общего назначения на территории области. Разрабатываемая информационная система (ИС) получила название «Связь-Глобальная».
Мультисервисная сеть оператора телефонной связи представляет собой сложно организованную систему, состоящую из автоматических телефонных станций (АТС) различных моделей и другого коммутационного оборудования. Связь коммутационного оборудования обеспечивается соединительными линиями с установленной на них регенерационнои и усилительной аппаратурой. Сеть регионального оператора имеет выход в сеть российского оператора междугородней и международной связи ОАО "Ростелеком". К сети общего пользования оператора "Липецкэлектросвязь" подключены сети операторов сотовой связи и ведомственных АТС различных учреждений (рис. 2.2).
АТС разделяются по моделям используемого оборудования на: - декадно-шаговые, - координатные, - квазиэлектронные, - электронные - электронно-цифровые.
Кроме того, АТС также различаются согласно исполняемым функциям и управленческому учету на: городские (ГАТС), междугородной связи (АМТС), сельские (CATC), центральные сельские АТС района (ЦАТС), учережденческие ведомственные станции (УАТС) (рис. 2.2).
Проводные линии связи, соединяющие АТС друг с другом, разделяются по виду используемой среды передачи на медные и оптоволоконные линии. В свою очередь, медные линии связи делятся по способу передачи сигнала на аналоговые и цифровые. В оптоволоконных линиях связи применяется исключительно цифровой способ передачи сигналов.
Линия связи состоит из отдельных кабельных участков протяженностью до нескольких километров, на которых через определенные интервалы установлено усилительное или регенерационное оборудование (НУП или НРП). В настоящее время на территории области используются оптические и медные цифровые соединительные линии, состоящие из регенерационных участков, оборудованных аппаратурой НРП (необслуживаемый регенерационный пункт).
Организационное деление сети соответствует организационно-территориальному делению области, где в каждом из районных центров находится районный узел электросвязи (РУЭС), ответственный за свой участок сети.
В областном центре и районных центрах, являющихся городами, организационно выделяются городские телефонные сети (ГТС). АТС, обслуживающие сельское население районов области, организационно объединяются в сети сельской телефонной связи (СТС). Ведомственные станции, имеющие выход в сеть общего пользования, учитываются в рамках сети (узла) ведомственных станций (рис. 2.3). Основными задачами информационной системы по учету объектов телефонной сети являются: отражение структуры сети, учет и контроль емкости сети, количества установленных телефонов, выделения номерной емкости, учет использования оборудования.
Основным показателем, характеризующим АТС как коммутационное оборудование, является монтированная емкость АТС, т.е. количество абонентских устройств (телефонов и пр.) и устройств специального назначения (аппаратура линий связи, сигнализации и пр.), которое может быть подключено к данной АТС. Каждая линия для подключения абонентского устройства идентифицируется номером внутри сети (телефонным номером).
Для станции может быть выделено несколько диапазонов нумерации разного типа: нумерация обычных абонентских комплектов, нумерация ISDN, нумерация спаренных абонентских комплектов. Внутри сети оператора "Липецкэлсктросвязь" абонентский номер уникально идентифицируется семизначным числом. Телефонный номер внутри районов области является пятизначным и имеет двузначный префикс в областной сети, абонентские номера г. Липецка и Липецкого района являются шестизначными и имеют префикс, обозначенный цифрой «2».
Помимо монтированной и номерной емкости требуется учет задействованной емкости - количества телефонных линий, задействованных для подключения абонентских и прочих устройств.
Альтернативная формализация реляционного исчисления
Рассмотрим запись кванторов и кванторных выражений в традиционной формализации реляционного исчисления. Условие (3s)(g ) означает, что г существует такой кортеж s, для которого условие (р выполняется. Запись (у$)((р) обозначает, что условие (р выполняется для любого кортежа s [4]. Однако, для достаточно сложных выражений, содержащих условия вида (Vs}[(p), невозможно четко сформулировать какое множество кортежей определяется данным выражением.
В приведенной традиционной формализации не рассматривается такое понятие алгебры высказываний и предикатов, как область определения связанных переменных. Все условия, включая условия принадлежности кортежей отношениям, рассматриваются как равноправные и преобразуются согласно единым правилам. Согласно правилам построения отрицаний в выражениях, содержащих операцию разности отношений, появляются кванторы общности и дизъюнкция условий принадлежности кортежей с другими условиями. Дизъюнкция условий принадлежности кортежей появляется также в выражениях, содержащих операцию объединения отношений [4].
Выражение (3.6) было получено чисто формальным путем, и проверить его правильность, привести какую-либо словесную интерпретацию, получить из двух конкретных отношений их частное по данной формуле практически невозможно.
Таким образом, в рамках традиционной формализации обозримыми являются только преобразования конъюнктивных выражений, содержащих кванторы существования. Анализ и словесная интерпретация дизъюнктивных выражений и выражений, содержащих кванторы общности, оказываются невозможны, а работа с ними осуществляется только на уровне формальных преобразований. Поэтому в литературе не рассматриваются преобразования
Знак сэ здесь л далее обозначает однозначное соответствие выражении. сложных выражений, содержащих кванторы общности и дизъюнктивные условия. Введем альтернативную формализацию реляционного исчисления: Изменим в традиционной формализации реляционного исчисления правило о свободном и связанном вхождении переменных в формулу: Если р и у/ - формулы, то (3s/y/)((p), (ysfiy)( p) -также формулы [2, 29]. При этом запись (3s/ )(# ) означает, что существует такой кортеж s, удовлетворяющий условию у/, для которого выполняется условие (р, т. е. оба условия выполняются. Формула (Vs/у/)( р) означает, что для любого кортежа s, для которого выполняется условие у/, выполняется и условие р. Условие у/ называется областью определения связанной переменной s. Правила построения отрицаний для выражений алгебры высказываний, содержащих область определения связанных переменных: 1) квантор существования меняется на квантор общности, квантор общности - на квантор существования; 2) к условию, не входящему в область определения, строится отрицание; 3) область определения связанной переменной остается неизменной.
В рамках алгебры высказываний областью определения связанной переменной может являться любое условие. В реляционном исчислении наилучшим вариантом задания области определения являются условия принадлежности переменной-кортежа некоторому отношению. В выражении реляционного исчисления для всех связанных переменных содержатся условия принадлежности, кроме того, область определения каждой связанной переменной является конечным множеством.
Выражения реляционного исчисления в данной формализации совпадают по структуре с SELECT-предложениями языка SQL: отношениям, задающим область определения связанных переменных в выражениях реляционного исчисления, соответствуют отношения-аргументы SQL-запроса; условиям, приравнивающим атрибуты свободной переменной атрибутам связанных переменных, - атрибуты, указанные после SELECT; остальным условиям-ограничениям на свободные и связанные переменные- условия WHERE [I, 28].
Логическая оптимизация заключается в приведении непроцедурной формы запроса к некоторому каноническому виду, являющемуся оптимальным среди всех эквивалентных вариантов данного запроса. Оптимальность запроса в целом определяется результатом работы всех фаз оптимизатора. Определить критерий оптимальности логической формы представления запроса чрезвычайно трудно, так это представление является непроцедурным и не определяет в явном виде способы доступа к данным, объемы данных, задействованных в разных фазах выполнения запроса, и количество требуемых операций. Вместе с тем, именно исходная логическая форма запроса в значительной степени предопределяет выбор процедур доступа к данным и используемые при этом средств доступа.
Установив наиболее явные соответствия между структурой логического представления запроса и процедурным планом выполнения можно получить оценку наиболее вероятного числа операций чтения данных, требуемых для выполнения запроса. Для построения оценки необходимо установить связь имеющегося логического представления с порядком выполнения запроса, выбором процедурных методов выполнения каждой фазы запроса и размерами отношений, являющихся результатами выполнения промежуточных фаз.
Оптимизация класса запросов, содержащих операцию разности
Поскольку вес атрибуты свободной переменной t приравниваются атрибутам связанной переменной щ все условия, налагаемые на атрибуты переменной /, применяются и к переменной и. Таким образом, во всех условиях, помимо условий приравнивания t и и, атрибуты переменной / могут быть заменены приравненными атрибутами переменной и: /(ЗиєЯ:(і[ЛІ} = і,[Л1]л...лі[Л„] = гІ[Ап]))л \A(W ES;(u[A,} = v[Al}A..,Ali[An} = v[A„}))
Поскольку связанные переменные р и н имеют одну область определения — отношение R, то условие Vu{n) еК:(р[А1\-и[АІ]л...лр[АІ] = и[АІ}) будет всегда ложным и согласно аксиомам поглощения не влияет на значение дизъюнкции и всего выражения в целом.
Ситуации выпадения квантора и связанной им переменной из выражения реляционного исчисления соответствует уменьшение числа отношений-аргументов и существенное изменение структуры SQL-запроса. Для оптимизации запросов данного вида необходимо реализовать обратное преобразование, учитывающее ситуацию выпадения квантора и восстанавливающее исходную структуру запроса.
Существующие методы оптимизации SPJ-запросов применимы только к конъюнктивным запросам, так как механизм их выполнения основан на эффекте разделения конъюнктивной селекции в каскад селекции и дальнейшем их перемещении вглубь, из общего условия соединения в условия унарных селекции. Следовательно, оптимизация дизъюнктивных запросов невозможна без их приведения к конъюнктивным запросам. При этом используется следующее свойство эквивалентности по дизъюнктивному условию операции селекции и объединения результатов селекции по условиям, входящим в дизъюнкцию. Другими словами, запрос вида.
Использование этого свойства для селекции по одному отношению не имеет оптимизационного эффекта, поскольку селекция выполняется за меньшее число операций. Необходимость в таком представлении возникает в случае, когда осуществляется соединение отношений по дизъюнктивному условию, причем в запросах данного класса такое преобразование в сочетании с алгоритмом Ульмана дает существенный оптимизационный эффект.
Для оптимизации таких запросов традиционно используется наиболее "мелкое" разбиение операциями объединения до подзапросов, содержащих только конъюнктивные условия. Это заведомо дает возможность применить к каждому из полученных конъюнктивных подзапросов-соединений алгоритм Ульмана и уменьшить стоимость каждого отдельного запроса. В результате запрос оказывается разбит на такое количество отдельных соединений, сколько отдельных конъюнкций содержит его условие в дизъюнктивной нормальной форме (ДНФ). Для целого ряда запросов такое разбиение является неэффективным, так как приводит к появлению достаточно большого числа выполняющихся отдельно запросов соединения, суммарная стоимость которых может оказаться даже больше, чем стоимость выполнения исходного соединения.
Однако такое разбиение является не единственным вариантом оптимизации данных запросов - существует более эффективное представление условий, разбиение на основе которого также позволяет применить алгоритм Ульмана к полученным подзапросам.
