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

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

ТАРАСОВ Николай Анатольевич

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

Специальность 05.13.06 - «Автоматизация и управление технологическими процессами и производствами (промышленность)»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Липецк 2004

Работа выполнена в Липецком государственном техническом университете.

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

доктор технических наук, доцент Погодаев А.К.

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

доктор технических наук, профессор Кульба В.В.

кандидат технических наук, доцент Богданов Д. А.

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

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

Защита диссертации состоится 20 апреля 2004 г. в 12 часов 00 минут на заседании диссертационного совета Д212.108.02 в Липецком государственном техническом университете (398600 Липецк, ул. Московская, 30, ауд. 601)

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

Автореферат разослан 18 марта 2004 г.

УЧЕНЫЙ секретарь ДИССЕРТАЦИОННОГО СОВЕТА

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Работа выполнена в соответствии с научным направлением ЛГТУ "Современные сложные системы управления"

БИБЛПОТЕКА I CfUrepfvpr аол\ 09 ЮО

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

Задачи исследования:

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

— разработать интерфейс доступа к базе данных с расширяемой структурой в информационной системе управления производственными объектами;

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Разработанные методы построения структуры данных и оптимизации запросов реализованы и внедрены при создании и расширении информационных систем "Липецкэлектросвязь" -филиала ОАО "ЦентрТелеком". Материалы по теме диссертации используются в Липецком государственном техническом университете при подготовке инженеров, бакалавров и магистров по специальностям "Автоматизированные системы обработки информации и управления" и "Прикладная математика".

Апробация работы. Основные положения работы докладывались и обсуждались на международной научно-практической конференции «Теория активных систем» (Москва-2003), на международной научно-технической конференции «Современные сложные системы управления CCCy/HTCS'2003» (Bopo-неж-2003), на международной конференции «Программное обеспечение авто-

матизированных систем управления (SAS-2000)» (Липецк-2000), на семинаре Липецкого регионального отделения Российской ассоциации искусственного интеллекта «Методы и модели искусственного интеллекта» (Липецк-2003).

Положения работы поддержаны грантами по фундаментальным исследованиям:

- Министерством образования РФ - Г00 4.1-68 "Разработка теории оптимизации проектирования информационных систем";

- Российским фондом фундаментальных исследований - № 03-01-96487 "Оптимизация схем баз данных и запросов на основе теории преобразований реляционных выражений" и № 03-01-96487 "Формализация алгоритма оптимизации реляционных запросов ".

Публикации. По результатам исследования опубликовано 8 печатных работ. В [7] и [4] автором разработан аппарат альтернативной формализации реляционного исчисления; в [8] формализованы правила преобразования семантики реляционных выражений в SQL-запросы; в [1] предложено применение разработанного формального аппарата при построении информационных систем; в [3] и [6] разработаны алгоритмы оптимизации коррелированных и дизъюнктивных запросов на основе преобразований выражений реляционного исчисления; в [5] приведена разработанная методика построения структур баз данных; в [2] разработан программный комплекс для оптимизации запросов, проведен сравнительный анализ с известными алгоритмами.

Структура и объем работы. Диссертационная работа состоит из пяти глав, введения, заключения, библиографического списка из 108 наименований, приложений; содержит 130 страниц основного текста, 25 рисунков, 12 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

применена на базе произвольной реляционной системы управления базами данных (СУБД).

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

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

Во второй главе рассматривается задача построения расширяемой структуры базы данных для создания информационной системы "Связь-Глобальная" управления производственными объектами региональной сети связи (рис.1). Автоматические телефонные станции (АТС) различаются согласно исполняемым функциям и управленческому учету на: городские (ГАТС), междугородной связи (АМТС), сельские (CATC), центральные сельские АТС района (ЦАТС), учережденческие ведомственные станции (УАТС). Помимо АТС система отражает линии связи, распределение номерной емкости, насе-

ленные щание.

пункты и уровень обслуживания населения, эфирное и проводное ве-

Рис. 1. Схема организации сети связи

При проектировании информационно-управляющей системы к модели данных были предъявлены следующие основные требования:

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

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

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

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

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

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

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

Модульная структура (см. рис. 2) представления свойств объектов может надстраиваться над произвольной сущностью предметной области; более того достаточным является построение одного модуля для всех сущностей предметной области (рис. 3).

Методы

Рис. 2. Представление свойств и методов объекта

Рис 3. Представление объектов разных сущностей

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

Структура базы данных информационной системы "Связь-Глобальная" для управления структурой и объектами сети связи была построена на основе разработанной методики (рис. 4).

Рис 4. Структура информационной системы "Связь-Глобальная"

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

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

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

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

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

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

(3 w e R: (м{1] = и[1] л...лф -к] = и[п - к] л и{и - к+1] = v[l] л... л Цп\ = v{*]))

которое допускает следующую вербальную интерпретацию: результат формируют кортежи арности п-к (содержащие первые п-к атрибутов отношения R), любое дополнение (конкатенация) которых кортежами отношения S принадлежит отношению R.

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

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

1. Критерий оптимальности SELECT-предложения языка SQL равен произведению объемов отношений следовавших за FROM и отношений, задействованных в коррелированных подзапросах данного запроса: f ({Select}) = II N„

где N, - объем отношения-аргумента рассматриваемого запроса или его коррелированного подзапроса.

Объем результата выполнения SELECT-предложения - пропорционален объему исходных отношений и селективности условий запроса включенных в WHERE:

где CTj - селективность условия запроса.

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

/({Union}) = /({Minus}) = £ЛГ .log2(AT).

Объем отношения-результата операции объединения оценивается величиной не большей суммы объемов отношений-аргументов, а результат операции разности имеет объем не больше, чем объем отношения-вычитаемого: s({Union})^Ni' s({Minus})<Nt.

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

/({Query}) = £/(&/«*,)+Yjf(Unionj) + ^/(Minus,).

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

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

Алгоритмы оптимизации и логические преобразования класса запросов разности к некоррелированному виду в литературе на сегодняшний день не рассмотрены и на практике не реализованы в оптимизаторах различных СУБД,

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

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

SELECT DISTINCT {AttrFinal} FROM R WHERE NOT EXISTS (

SELECT * FROM S WHERE {R.AttrRepl} = {S.AttrRepl} AND F({R.AttrUsed}))

выполняется последовательность шагов:

1. Определим следующие множества атрибутов отношения R:

{AttrFinal} - множество атрибутов, составляющих финальный результат, {AttrUsed} - множество атрибутов, используемых в условиях подзапроса, {AttrRepl} - атрибуты, приравненные в подзапросе.

2. Если {AttrRepl} = {AttrFinal} и {AttrRepl} с {AttrUsed}, то строится разность

между отношениями R и S:

SELECT {AttrRepl} FROM R MINUS

SELECT {AttrRepl} FROM S WHERE F ({S.AttrUsed})).

Если {AttrRepl} <z {AttrFinal} и {AttrRepl} с {AttrUsed}, то строится разность между отношениями R и S, а после проекция на атрибуты {AttrFinal}:

SELECT {AttrFinal} FROM ( SELECT {AttrRepl} FROM R MINUS

SELECT {AttrRepl} FROM S WHERE F ({S.AttrUsed})), иначе разность строится между R и соединением R и S по имеющемуся условию:

SELECT {AttrFinal} FROM (

SELECT {AttrUsed} U {AttrFinal} FROM R MINUS

SELECT {AttrUsed} VJ {AttrFinal} FROM R,S WHERE {R.AttrRepl} = {S.AttrRepl} AND F(R.AttrUsed)).

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

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

J*(F,vF1v...)*{EivElv...)A..., О)

где J- условие соединения, Fj ■- i-oe условие из группы условий, применяемых к первому из отношений-операндов, £/ - ко второму и так далее. Число условий вида (1), соединенных дизъюнкцией, при декомпозиции исходного условия должно быть минимальным. В дальнейшем запросы с такими условиями соединения оптимизируются известными алгоритмами для конъюнктивных запросов, например алгоритмом Ульмана.

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

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

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

Рис 5. Вариан ты покрытий: а) непересекающиеся решетки, б) пересекающиеся максимальные решетки

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

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

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

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

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

Рис б. Количество реляционных отношений в базе данных на этапах развития информационной системы

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

Зона охвата АТС Адресный объект (нас. пункт)

Рис. 7. Фрагменты отношений

Коррелированный вариант запроса операции частного отношений, производной

от операции разности, имеет вид:

SELECT DISTINCT azl.atsjd FROM ats_zone azl WHERE NOT EXISTS(

SELECT * FROM (SELECT * FROM address WHERE^^bne^ addr WHERE NOT EXISTS (

SELECT * FROM ats_zone az2

WHERE azl.atsjd = az2.ats_id AND addr.adr_id = az2.adr_id)).

Некоррелированный вариант является более сложным по своей структуре, но

на порядок эффективнее при выполнении:

SELECT DISTINCT azl.ats_id FROM ats_zone_azl MINUS

SELECT DISTINCT azl.atsjd FROM ( SELECT DISTINCT azl.ats_id, addr.adr_id

FROM ats_zoneazl, (SELECT * FROM address WHERE <yсловие>)addr MINUS

SELECT DISTINCT ats__id, adr_id FRCM ats__zone az2).

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

ЗАКЛЮЧЕНИЕ

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

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

2. Реализованы объектно-ориентированный и реляционный интерфейсы доступа к хранилищу информации об объектах и классах в информационно-управляющих системах.

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

4. Разработаны формальные критерии оптимальности для классов запросов соединения, разности и объединения.

5. Разработаны алгоритмы оптимизации класса коррелированных запросов разности и дизъюнктивных запросов для повышения эффективности выполнения процедур обработки данных в рамках существующих информационно-управляющих систем. Алгоритмы позволяют существенно повысить скорость выполнения запросов данных классов.

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

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

1. Блюмин С.Л. Математическое обеспечение информационных технологий. Часть 1. Реляционная математика и базы данных: Учебное пособие/ С.Л. Блюмин, А.К. Погодаев, Н.А. Тарасов - Липецк: ЛЭГИ, 2001. -75с.

2. Погодаев А.К. Оптимизация некоторых классов запросов в системах баз данных // Теория активных систем /Труды международной научн.-

практ.конф./ А.К. Погодаев, НА Тарасов - М: ИЛУ РАН, 2003. Т.2. С.64-65.

3. Блюмин С.Л. Методы логической оптимизации запросов в информационных системах // Современные сложные системы управления CCCy/HTCS'2003: Сб. трудов международной научн.-техн.конф. 2т./ С.Л. Блюмин, А.К. Погодаев, Н.А. Тарасов - Воронеж: ВГСАУ, 2003. С.361-364.

4. Погодаев А. К. Роль логики высказываний и предикатов в реляционном исчислении. - В кн.: Программное обеспечение автоматизированных систем управления (SAS-2000): Доклада: международной научн.-техн. конфУ А.К. Погодаев, Н.А. Тарасов - Липецк: ЛГТУ, 2000. С.20-24.

5. Погодаев А. К. Оптимальное проектирование схем баз данных // Методы и модели искусственного интеллекта /Сб. научн. трудов семинара ЛРО РАИИУ А.К. Погодаев, В.В. Овчинников, Н.А. Тарасов - Липецк: ЛГТУ, 2003. С.131-140.

6. Погодаев А.К. Оптимизация запросов, содержащих кванторы общности и существования // Современные проблемы информатизации в технике и технологиях: Сб. трудов. Вып.7 / А.К. Погодаев, Н.А Тарасов - Воронеж: ЦЧКИ,2002.С18.

7. Блюмин С.Л. Прикладной подход к реляционному исчислению // Современные проблемы информатизации в технике и технологиях: Труды V Международной электронной научн. конфУ С.Л. Блюмин, А.К. Погодаев, НА Тарасов - Воронеж: ЦЧКИ, 2000. С.106.

8. Погодаев А.К. Преобразование выражений реляционной математики в SQL-запросы-В кн.: Современные проблемы информатизации в технике и технологиях: Труды V Международной электронной научн. конфУ А.К. Погодаев, Н.А. Тарасов - Воронеж: ЦЧКИ, 2000. С.126-127.

Подписано в печать 11.03.2004г. Формат 60x84 1/16. Бумага офсетная. Ризография. Печ. л. 1,0. Тираж 100 экз. Заказ № 169. Типография ЛГТУ 398600 Липецк, ул. Московская, 30.

f-57ß7

Введение.

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

1.1. Семантические модели представления предметной области.

1.2. Реляционная схема БД.

1.3 Семантические ограничения и интерфейс обращения в реляционных и объектно-реляционных системах.

1.4. Математические основы операций обработки информации.

Преобразование и оптимизация запросов.

Постановка цели и задач исследования.

2. Расширяемая структура данных информационной системы учета объектов региональной сети связи.

2.1. Система учета объемных показателей и структуры сети электросвязи.

2.2. Разработка расширяемой схемы базы данных.

2.3. Объектно-ориентированный и реляционный интерфейсы работы с данными.

2.4. Использование расширяемой модели в информационной системе для управления объектами сети связи.

2.5. Выводы.

3. Альтернативная формализация реляционного исчисления. Критерий оптимальности запроса в непроцедурной форме.

3.1. Альтернативная формализация реляционного исчисления.

3.2. Критерий оптимальности непроцедурной формы запроса.

3.3. Выводы.

4. Логическая оптимизация различных классов запросов в рамках реляционной модели.

4.1. Оптимизация класса запросов, содержащих операцию разности.

4.2. Оптимизация класса дизъюнктивных запросов.

4.3. Выводы.

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

5.1. Расширение структуры базы данных в системе "Связь-Глобальная".

5.2. Алгоритм оптимизации запросов разности в информационной системе "Связь-Глобальная".

5.3. Алгоритм оптимизации дизъюнктивных запросов в информационной системе "Связь-Глобальная".

5.4. Выводы.

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

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

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

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

Работа выполнена в соответствии с научным направлением ЛГТУ "Современные сложные системы управления".

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

Задачи исследования:

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Разработанные методы построения структуры данных и оптимизации запросов реализованы и внедрены при создании и расширении информационных систем "Липецкэлектросвязь" - филиала ОАО "ЦентрТелеком". Материалы по теме диссертации используются в Липецком государственном техническом университете при подготовке инженеров, бакалавров и магистров по специальностям "Автоматизированные системы обработки информации и управления" и "Прикладная математика".

Апробация работы. Основные положения работы докладывались и 6 обсуждались на международной научно-практической конференции «Теория активных систем» (Москва-2003), на международной научно-технической конференции «Современные сложные системы управления СССУ/НТС8'2003» (Воронеж-2003), на международной конференции «Программное обеспечение автоматизированных систем управления (8А8-2000)» (Липецк-2000), на семинаре Липецкого регионального отделения Российской ассоциации искусственного интеллекта «Методы и модели искусственного интеллекта» (Липецк-2003).

Положения работы поддержаны грантами по фундаментальным исследованиям:

- Министерством образования РФ - Г00 4.1-68 "Разработка теории оптимизации проектирования информационных систем";

- Российским фондом фундаментальных исследований - № 03-01-96487 "Оптимизация схем баз данных и запросов на основе теории преобразований реляционных выражений" и № 03-01-96487 "Формализация алгоритма оптимизации реляционных запросов ".

Публикации. По результатам исследования опубликовано 8 печатных работ. В [2] и [29] автором разработан аппарат альтернативной формализации реляционного исчисления; в [28] формализованы правила преобразования семантики реляционных выражений в 8С)Ь-запросы; в [I] предложено применение разработанного формального аппарата при построении информационных систем; в [3] и [27] разработаны алгоритмы оптимизации коррелированных и дизъюнктивных запросов на основе преобразований выражений реляционного исчисления; в [26] приведена разработанная методика построения структур баз данных; в [30] разработан программный комплекс для оптимизации запросов, проведен сравнительный анализ с известными алгоритмами.

Структура и объем работы. Диссертационная работа состоит из пяти глав, введения, заключения, библиографического списка из 108 наименований, приложений; содержит 130 страниц основного текста, 25 рисунков, 12 таблиц.

5.4. Выводы

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

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

ЗАКЛЮЧЕНИЕ

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

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

2. Реализованы объектно-ориентированный и реляционный интерфейсы доступа к хранилищу информации об объектах и классах в информационно-управляющих системах.

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

4. Разработаны формальные критерии оптимальности для классов запросов соединения, разности и объединения.

5. Разработаны алгоритмы оптимизации класса коррелированных запросов разности и дизъюнктивных запросов для повышения эффективности выполнения процедур обработки данных в рамках существующих информационно-управляющих систем. Алгоритмы позволяют существенно повысить скорость выполнения запросов данных классов.

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

1. Блюмин С.Л. Погодаев А.К., Тарасов H.A. Математическое обеспечение информационных технологий. Часть 1. Реляционная математика и базы данных: Учебное пособие. Липецк: ЛЭГИ, 2001. 75с.

2. Блюмин С.Л., Погодаев А.К., Тарасов H.A. Прикладной подход к реляционному исчислению // Современные проблемы информатизации в технике и технологиях: Труды V Международной электронной научной конференции Воронеж: ЦЧКИ, 2000 С 106.

3. Блюмин С.Л., Погодаев А.К., Тарасов H.A. Методы логической оптимизации запросов в информационных системах // Современные сложные системы управления CCCy/HTCS'2003: Сб. трудов международной научн.-техн.конф. 2т. Воронеж: ВГСАУ, 2003. С.361-364.

4. Грэй П. Логика, алгебра и базы данных. М.: Машиностроение 1989. 368с.

5. Дейт К. Дж. Введение в системы баз данных.: Пер. с англ. 6-е изд. — К.: Диалектика, 1998, 784 с.

6. Кузнецов Л.А., Блюмин С.Л., Погодаев А.К., Белопольский В.В. Разработка реляционных моделей данных для систем исследования технологии производства стали //Изв.вуз.Черная металлургия. 1993. N7. С.26-29.

7. Кузнецов Л.А., Погодаев А.К., Овчинников В.В. Оптимизация запросов для реляционных систем управления базой данных./Сб. научн. трудов молодых ученых ЛГТУ. Липецк: ЛГТУ, 1999. С.34-37.

8. Кузнецов Л.А., Погодаев А.К., Овчинников В.В. Метод организации базы данных металлургического производства //Вестник ЛГТУ-ЛЭГИ. -Липецк: ЛЭГИ, N2(6).2000. С.103-110.

9. Ю.Кузнецов Л.Л., Погодаев А.К., Овчинников В.В. Синтез схемы реляционной базы данных // Современные системы управления предприятием(С8ВС'2001): Сб. трудов международной научн.-техн.конф. -Липецк: ЛГТУ, 2001. С.92-96.

10. П.Кузнецов Л.А., Погодаев А.К., Овчинников В.В. Система оптимизации структуры базы данных//Вестник ЛГТУ-ЛЭГИ. Липецк: ЛЭГИ, Nl(7).2001. С.6-10.

11. Кузнецов Л.А., Погодаев А.К., Овчинников В.В. Оптимизация запросов к базам данных // Управление большими системами: Сборник трудов молодых ученых. Выпуск 4. М.: ИПУ РАН, 2003. С.27-34.

12. З.Кузнецов Л. А., Овчинников В.В., Погодаев А.К. Об алгоритме оптимизации схем баз данных // Теория активных систем /Труды международной научн.-практ.конф. М.: ИПУ РАН, 2003. Т.2. С.50-51.

13. Кузнецов С. Методы оптимизации выполнения запросов в реляционных СУБД. http://www.citforum.ru/database/articles/art 26.shtml.

14. Кульба В.В., Ковалевский С.С., Горгидзе И.А., Зайцев К.С., Карсанидзе Т.В., Шелков А.Б. Методы повышения эффективности и качества функционирования автоматизированных информационно-управляющих систем. М.: КомпьюЛог, 2001, 344с.

15. Мейер Д. Теория реляционных баз данных. Пер. с англ. М. К. Валиева и др.; -М.: Мир, 1987, 608 с.

16. Погодаев А.К. Метод моделирования схем реляционных баз данных // Сб. научн. трудов преподавателей и сотрудников, посвященный 30-летию132

17. НИС ЛГТУ. Липецк: ЛГТУ, 2003. С.99-103.

18. Погодаев А.К. Объектный подход при проектировании информационных систем //Изв. вуз. Черная металлургия. 2001. N11. С.57-59.

19. Погодаев А.К. Метод моделирования информационных схем в производственных системах управления //Вестник ЛГТУ-ЛЭГИ. -Липецк: ЛЭГИ, N2(10).2003. С.59-63.

20. Погодаев А.К., Батищев Р.В. Обработка данных на языке SQL в реляционных системах: Учебное пособие. Липецк: ЛГТУ, 2000. -63с.

21. Погодаев А.К., Дозоров В.В. Программное обеспечение автоматизированных систем. Разработка информационной структуры: Учебное пособие. Липецк: ЛЭГИ, 2002. -52с.

22. Погодаев А.К., Дозоров В.В. Программное обеспечение автоматизированных систем. Разработка приложений баз данных: Учебное пособие. Липецк: ЛЭГИ, 2002. -63с.

23. Погодаев А.К., Овчинников В.В., Тарасов H.A. Оптимальное проектирование схем баз данных // Методы и модели искусственного интеллекта /Сб. научн. трудов семинара ЛРО РАИИ. Липецк: ЛГТУ, 2003. С.131-140.

24. Погодаев А.К., Тарасов H.A. Оптимизация запросов, содержащих кванторы общности и существования // Современные проблемы133информатизации в технике и технологиях: Сб. трудов. Вып.7 Воронеж: ЦЧКИ, 2002. С. 18.

25. Погодаев А.К., Тарасов Н.А. Преобразование выражений реляционной алгебры в SQL-запросы // Современные проблемы информатизации в технике и технологиях: Труды V Международной электронной научной конференции Воронеж: ЦЧКИ, 2000 С 106.

26. Погодаев А.К., Тарасов Н.А. Роль логики высказываний и предикатов в реляционном исчислении // Международная научно-техническая конференция "Программное обеспечение автоматизированных систем управления" Липецк: ЛГТУ, 2000 - С 20-24.

27. Погодаев А.К., Тарасов Н.А. Оптимизация некоторых классов запросов в системах баз данных // Теория активных систем: Труды международной научн.-практ.конф. М.: ИПУ РАН, 2003. Т.2. С.64-65.

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

29. Уэлдон Дж. Администрирование баз данных. М.: Финансы и статистика, 1984, 207с.

30. Хаббард Дж. Автоматизированное проектирование баз данных. М.: Мир, 1984, 294с.

31. Abiteboul S., Hull R. IFO: a formal semantic database model // ACM Transactions on Database Systems, 12(4), 1987, pp. 525-565.

32. Aho A. V., Beeri C., Ulman J. D. The Theory of Joins in Relational Databases // ACM Transactions on Database Systems, 4(3), 1979.

33. Aho A.V., Sagiv Y., Ullman J.D. Efficient optimization of a class of relational expressions // ACM Transactions on Database Systems, 4(4), 1979.

34. Akoka J., Comyn-Wattiau I. Entity-relationship and object-oriented model automatic clustering // Data & Knowledge Engineering, 20(2), 1996, pp. 87-117.

35. Allen F. W., Loomis M. E. S., Mannino M. V. The Integrated Dictionary-Directory System //ACM Сотр. Surv, 14(2), 1982.

36. Analyti A., Spyratos N., Constantopoulos P. Deriving semantic information though property covering and inheritance // Data & Knowledge Engineering, 28(1), 1998, pp. 3-30.

37. Artale A., Franconi E., Guarino N., Pazzi L. Part-whole relations in object-centered systems: An overview, 20(3), 1996, pp. 347-384.

38. Babb E. Joined normal form: a storage encoding for relational databases // ACM Transactions on Database Systems, 7(4), 1982, pp. 588-614.

39. Bernstein P.A. Synthesizing third normal form relations from functional dependencies // ACM Transactions on Database Systems, 1(4), 1976, pp. 277-298.

40. Chakravarthy U.S., Grant J., Minker J. Logic-based approach to semantic query optimization // ACM Transactions on Database systems, 15(2), 1990, pp. 162-207.

41. Chaudhuri S. An Overview of Query Optimization in Relational Systems. -Microsoft Research, One Microsoft Way, 1999, Redmond, WA.

42. Chaudhuri S., Shim K. Optimization of queries with user-defined predicates // ACM Transactions on Database Systems, 24(2), 1999, pp. 177-228.

43. Chen P.P.S. A Preliminary Framework for Entity-Relationship Models // Entity-Relationship Approach to Information Modeling and Analysis, Saugus, Calif., 1981.

44. Chen P.P.S. The entity-relationship model — towards a unified view of data // ACM Transactions on Database Systems, 1(1), 1976, pp. 9-36.

45. Chiang R., Barron T., Storey V., Reverse engineering of relational databases: Extraction of an eer model from a relational database // Data & Knowledge Engineering, 12(2), 1994, pp. 107-142.

46. Codd E. A Data Base Sublanguage Founded on the Relational Calculus. Proc. 1971 ACM SIGFIDET Workshop on Data Description, Accès and Control.

47. Codd E. A Relational Model of Data for Large Shared Data Banks. CASM 13, №6 (June 1970).

48. Codd E. Derivability, Redundancy, and Consistency of Relations Stored in the Large Data Banks IBM Research Report, RJ599 (August 1969).

49. Codd E. F. Further Normalization of the Data Base Relational Model // Data Base Systems, Courant Computer Science Symposia Series 6, 1972.

50. Codd E. F. Recent Investigations into Relational Data Base Systems // Proc. IFIP Congress, Stockholm, Sweden, 1974.

51. Codd E. Relational Completeness of Data Base Sublanguages. Data Base Systems, Courant Computer Science Symposia Series, 1972, V 6, Englewood Cliffs, N.Y.: Prentice-Hall.

52. Codd E.F., Extending the database relational model to capture more meaning // ACM Transactions on Database Systems, 4(4), 1979, pp. 397-434.

53. Date C. J. A Normalization Problem // The Relational J, 4(2), 1992.

54. Date C. J. A Note to One-to-One Relationships // C. J. Date. Relational Database Writings 1985-1989, Addison-Wesley, 1990.

55. Date C. J. A Practical Approach to Database Design // C. J. Date. Relational Database: Selected Writings, Addison Wesley, 1986.

56. Date C. J. Entity/Relationship Modeling and the Relational Model // C. J. Date and Hugh Darwen. Relational Database Writings: 1989-1991, Addison-Wesley, 1992.

57. O.Date C. J. Will the Real Fourth Normal Form Please Stand Up? // C. J. Date and Hugh Darwen. Relational Database Writings 1989-1991, Addison-Wesley, 1992.

58. Date C.J., Fagin R. Simple conditions for quaranteeing higher normal forms in relational databases // ACM Transactions on Database Systems, 17(3), 1992, pp. 465-476.

59. Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif., 1987.-C. 197-208

60. Dayal, U., Goodman N., Kata R.H. An Extended Relational Algebra with Control Over Duplicate Elimination // Proc. ACM PODS 1982.

61. Dayal, U., Processing Queries With Quantifiers: A Horticultural Approach // Proc. ACM PODS 1983.

62. Elmasri R., Navathe S.B. Fundamentals of Database Systems. Benjamin Cummings, Redwood City, California, 1994.

63. Fargin R. Normal Forms and Relational Database Operators // Proc. 1979 ACM SIGMOD Intern. Conf. on Management of Data, Boston, Mass., 1979.

64. Fargin R. A normal form for relational databases that is based on domains and keys // ACM Transactions on Database Systems, 6(3), 1981, pp. 387-415.

65. Fargin R. Acyclic Database Schemes (of Various Degrees): A Painess Introduction // IBM Research Report RJ3800, 1983.

66. Fargin R. Multivalued dependencies and a new normal form for relational databases // ACM Transactions on Database Systems, 2(3), 1977.

67. Fargin R. Normal Forms and Relational Database Operators // Proc. 1979 ACM SIGMOD Intern. Conf. on Management of Data, Boston, Mass., 1979.

68. Fleming C. C., Von Halle B. Handbook of Relational Database Design, Addison-Wesley, 1989.

69. Ganski, R.A., Long, H.K.T. Optimization of Nested SQL Queries Revisited // Proc. of ACM SIGMOD, San Francisco, 1987.

70. Goldstein R.C., Storey V.C. Data abstractions: Why and how? // Data & Knowledge Engineering, 29(3), 1999, pp. 293-311.

71. Graefe G. The Cascades Framework for Query Optimization. In Data Engineering Bulletin. Sept. 1995.

72. Hall P., Owlett J., Todd S. J. P. Relations and Entities // Modeling in Data Base Management Systems, Amsterdam, Netherlands, 1975.

73. Hammer M. M., McLeod D. J. The Semantic Date Model: A Modeling Mechanism for Database Applications // Proc. 1978 ACM SIGMOD Intern. Conf. on Management of Data, Austin, Texas, 1978.

74. Health I. J. Unacceptable file operations in Relational Database // Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control. San Diego, Calif., 1971.

75. Hull R., King R. Semantic Database Modeling: Survey, Applications, and Research Issues // ACM Comp. Surv., 19(3), 1978.

76. Jarke M., Koch J. Query Optimization in Database Systems // ACM Comput. Surv.- 1984.- V 16, N 2.- C. 111-152

77. Kent W. A Simple Guide to Five Normal Forms in Relational Database Theory // CFCV, 26(2), 1983.

78. Kiessling W. SQL-Like and Quel-like correlation queries with aggregates revisited // UCB/BRL Memo 84/75, Electronics Research Laboratory, Univ. California, Berkeley (Sept. 1984)

79. Kim S.-K., Carrington D. A Formal Model of the UML Metamodel: The UML State Machine and Its Integrity Constraints // vol. 2272 of Lecture Notes in Computer Science, 2002, p. 497.

80. Kim W. On Optimizing an SQL-Like Nested Query // ACM Trans. Database Syst.- 1982.- V 7, N 3.- C. 443-469

81. Laleau R., Polack F. A Rigorous Metamodel for UML Static Conceptual Modelling of Information Systems // vol. 2068 of Lecture Notes in Computer Science, 2001, p. 402.

82. Levene M., Loizou G. Semantics for null extended nested relations // ACM Transactions on Database Systems, 18(3), 1993, pp. 414-459.

83. Lorentzos N.A., Manolopoulos Y. Functional requirements for historica and interval extensions to the relational model // Data & Knowledge Engineering, 17(1), 1995, pp. 59-86.

84. Maier D., Ullman J. D. Fragments of Relations // Proc. 1983 SIGMOD Intern. Conf. on Management of Data, San Jose, Calif., 1983.

85. Mannila H., Raiha K.-J. The Design of Relational Databases, Wokingham, UK, 1992.

86. Mok W.Y., Nh Y.-K., Embley D.W. A normal form for precisely characterizing redundancy in nested relations // ACM Transactions on Database Systems, 21(1), 1996, pp. 77-106.

87. Murahkrishna M, Dewitt D. Optimization of Multiple-Relation Multiple-Disjunct Queries // ACM Trans. Database Syst.- 1988. V 14, № 3 - C. 263-275

88. Paredaens J., Gucht D.V. Converting nested algebra expressions into flat algebra expressions // ACM Transactions on Database Systems, 17(1), 1992, pp. 65-93.

89. Peckham J., Maryanski F. Semantic Data Models // ACM Comp. Surv., 20(3), 1988.

90. Schmid H. A., Swenson J. R. On the Semantics of the Relational Data Base Model // Proc. 1975 ACM SIGMOD Intern. Conf. on Management of Data, San Jose, Calif., 1975.

91. Smith J. M. A Normal Form for Abstract Syntax // Proc. 4th Intern. Conf. on Very Large Data Bases, Berlin, FDR, 1978.

92. Smith J. M., Smith D. C. P. Database Abstractions: Aggregation // CACM, 20(6), 1977.

93. Smith J.M., Smith D.C.P. Database abstractions: aggregation and generalization // ACM Transactions on Database Systems, 2(2), 1977, pp. 105133.

94. Sundgren B. The Infological Approach to Data Bases // J. W. Klimbie and K. L. Koffeman (eds.). Data Base Management, New York, Elsevier Science, 1974.

95. Tansel A.U., Garnett L. On Roth, Korth, and Silberschatz's extended algebra and calculus for nested relational databases, 17(2), 1992, pp. 374-383.

96. Tasker D. Fourth Generation Data: A Guide to Data Analysis for New and Old Systems, Sydney, Australia, 1989.

97. Theorey T. J. Database Modeling and Design: The Entity-Relationship Approach, San Mateo, Calif.: Morgan Kaufmann, 1990.

98. Theorey T. J., Fry J. P. Design of Database Structures, Englewood Cliffs, 1982.

99. Wai Y.M., Embley D.W. Using NNF to transform conccptual data models to object-oriented database designs // Data & Knowledge Engineering, 24(3), 1998, pp. 313-336.

100. Zaniolo C. A new normal form for the design of relational database schemata // ACM Transactions on Database Systems, 7(3), 1982, pp. 489-499.

101. Beech D. A Foundation for Evolution from Relational to Object Databases // Schmidt, Ceri, Misskof. Extending Database Technology. New-York, N. Y.: Springer-Verlag, 1988.