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



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

ЗЫКИН Сергей Владимирович

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

05.13.17 - Теоретические основы информатики

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

Омск-2005

Работа выполнена в Омском Филиале Института Математики СО РАН им. академика С .Л. Соболева

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

Доктор технических наук Кузнецов С.Д.

Доктор технических наук Родионов A.C.

Доктор физико-математических наук Соколинский Л.Б.

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

Институт вычислительной математики и математической геофизики СО

Защита диссертации состоится 6 декабря 2005 г. в 14.00 часов на заседании Совета Д 219.005.02 при Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики» Министерства Российской Федерации по связи и информации по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного университета телекоммуникаций и информатики (СибГУТИ) по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

Отзывы на автореферат просьба высылать по адресу: 630102, г. Новосибирск, ул. Кирова, 86, заместителю декана ИВТ И.И. Резван.

Автореферат разослан 26 октября 2005 г.

Ученый секретарь

РАН

Диссертационного Совета, к.т.н.

И.И. Резван

Общая характеристика работы

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

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

Вкладом автора является разработка и исследование ряда специализированных моделей данных и метода межмодельных отображений для автоматизации построения пользовательских приложений. По предложенному методу построены универсальная модель таблицы соединений и модель семантической трансформации, которые позволяют получить реализацию программного обеспечения для работы пользователей с фазовыми диаграммами, электронными таблицами и т.д.. Разработана математическая модель фазовой диаграммы и алгоритмы расчета характеристик с ее использованием. Для всех представленных моделей проведено достаточно подробное их исследование. Автором разработано программное обеспечение базы данных по фазовым диаграммам, использованное в ИНХ СО РАН. Компонент этого программного обеспечения - система управления файлами, была использована в других программных разработках: комплекс программ для анализа радиосетей передачи информации, архивная система. На основе полученных результатов по межмодельным преобразованиям был разработан инструментарий для автоматической генерации пользовательских приложений с представлением данных в виде электронных таблиц.

Научную новизну работы образуют перечисленные ниже основные результаты: .

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

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

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

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

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

ритмы работы с ней были использованы в ИНХ СО РАН для исследования моделей физико-химических соединений и формирования информационной базы по фазовым диаграммам. Технология построения таблиц соединения и "семантическая трансформация "использовались при формировании пользовательских приложений для организации учебного процесса в ВУЗе на примере СибАДИ (г. Омск). Результаты работы используются в лекционных курсах для студентов математического факультета Омского госуниверситета.

Апробация. Результаты работы доложены на конференциях и семинарах, среди которых:

Пятая всесоюзная школа: "Применение математических методов для описания и изучения физико-химических равновесий". - Новосибирск: СО АН СССР, 1985.

Пятая научно-практическая конференция "Информатика и вычислительная техника в учебном процессе и управлении". - Омск: ОмГПИ, 1988.

Шестая научно-практическая конференция "Новые информационные технологии в учебном процессе и управлении". - Омск: ОмГПИ, 1989.

Доклад на семинаре Института прикладной информатики под председательством Ю.П. Дробышева и с участием сотрудников СКТБ при ИК HAH Украины. - Киев, 1993.

Конференция "Информационные системы в науке - 95". - Москва, 1995.

Международная конференция "ADBIS'95". - Москва, 1995.

Международная конференция "Проблемы оптимизации и ее приложения". - Омск, 1997.

Доклад на семинаре Института систем информатики им. А.П. Ершова СО РАН под председательством Поттосина И.В. - Новосибирск, 1998.

Международная конференция ИНПРИМ-2000. - Новосибирск, 2000.

Международная конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова. - Новосибирск, 2001.

Доклад на научно-исследовательском семинаре "Автоматизация программирования "Московского государственного университета (факультет ВМиК) под руководством Шура-Бура М.Р., Москва, 2003.

Публикации. По теме диссертационной работы опубликовано 26 работ, из них: статьи в центральных журналах - 7, статьи в сборниках СО РАН - 5, статьи в местных изданиях - 2, доклады на международных конференциях - 6, тезисы доклада на конференциях - 4, препринты - 2.

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

библиография - 105 наименований.

Содержание работы

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

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

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

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

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

M,D,F,P>,

где М - логическая модель (схема) данных; D - совокупность допустимых состоянии базы данных; F - набор операции для модели М\ Р - совокупность предикатов, ограничивающих допустимые состояния D; М и D в сс^ вокупности являются носителем системы. ^

Модель П будем считать моделью корпоративной информационной системы (исходной), а fi' =< M',D',F\P' > - специализированной (целевой). Для достижения поставленных целей необходимо построение отображения

П Q'.

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

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

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

Предложенный метод построения отображения состоит из пяти этапов:

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

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

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

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

4. Формирование образов операций преобразования целевой модели. В процессе работы с представлением модели О' пользователь формирует последовательность команд /', которая переводит модель ГУ из состояния <1'й € Д' в'состояние € Исполняющая среда (программное обеспечение) должна сформировать соответствующую совокупность команд /, которая необходима для перевода модели из состояния в,ц € в состояние с€ И у Указанные преобразования состояний должны удовлетворять^ условию коммутативности:

<1ц СЦт —^ <£}т Оц —► аа —>

Другими словами, в состояние можно перейти двумя различными способами, но результат должен быть один и тот же. Сформулированное условие показывает, что основой для формирования / является алгоритм А1д. При этом, задача формирования / является обратной относительно А1д.

5. Формирование образов операций преобразования исходной модели. Модификация состояния модели П может быть выполнена из другого приложения, что потребует изменения состояния модели Для этого должна быть сформирована последовательность команд /', которая выполнит необходимые преобразования в представлении модели 0!. При этом задача формирования /' является прямой относительно А1д и условие коммутативности примет следующий вид:

Во второй главе вводится в рассмотрение новая модель данных - таблица соединений (¿"-таблица). Схематически ¿'-таблица может быть представлена в следующем виде. Рассмотрим отображения типа "соединение": Яг, Яг, —,Як (£■, где 5 - схема отношения, определенная на всем множестве атрибутов А\у Л2, ...,ЛП. Рассмотрим принцип формирования кортежей 4 6 5, где 5 - реализация схемы отношения Б.

Определение. Соединение К\ м Яг и ... и Я* будем называть существующим, если для совокупности схем Я*, г = 1, к существует хотя бы одна

упорядоченная последовательность R\, R2, ..., Rk такая, что

з _

»=1

Рассмотрим существующие соединения для всевозможных сочетаний из к по т реализаций г,-, т = 1, к. Для каждого кортежа и каждого существующего соединения сформируем кортеж t по следующим правилам: t[Aj] — u[Aj], если атрибут Aj принадлежит соединению, и t[Aj\ = етр в противном случае. Каждому кортежу поставим в соответствие, битовый вектор l(t) = (¿i(t), i2(i), где l3(t) — 1, если реализация rj схемы Rj

участвует в текущем соединении, и lj(t) = 0 в противном случае.

' Определение. Кортеж t € s является менее определенным или равным кортежу f е 5, когда для любого атрибута А{ выполнено: если t[Ai] ф t'[Aij, то t[Ai] — етр и lj(t) < lj(f), j = 1, к. В этом случае будем писать: t -< t'.

Рассмотренное определение частичного порядка означает то, что кортеж t' содержит в себе все менее определенные либо равные кортежи. Следовательно, для завершения построения s необходимо из 5-таблицы удалить все менее определенные кортежи.

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

Определение. Проекция ^Rh,Rj2,...,Rjm(s) есть совокупность кортежей определенных на множестве атрибутов X = Uili > гДе Для каждого и[Х\ существует кортеж t £ s такой, что upf] = £[Х] и Ij^t) — 1, г — 1,т.

Свойство. Для любого существующего соединения отношений Rjlt Rj2, ...,Rjmi где т — 1,к, выполнено:

Rh и Rj2 и ... и Rjm = -KRh>Rj2,...tR.m{s).

^То есть, операция естественного соединения множества реляционных отношений эквивалентна одной операции проекции на 5-таблице.

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

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

Для случая, когда данные в исходной модели могут быть изменены другим приложением, разработаны образы операций преобразования реляционной базы данных для ¿'-таблицы. В качестве операций преобразования исходной модели данных использован классический набор преобразования реляционных таблиц: добавление кортежа u[J?i] к реализации схемы Ri, удаление кортежа и модификация кортежа —*

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

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

Определение. Пусть для и кортежа tes сформировано множество Tj - совокупность беспрепятственно склеиваемых отношений Rm, а для кортежа t' € s, t Ф t', сформировано множество Tv. Допустим, что существуем схема Rm, такая, что: 1) Rm е Ту,

4) не существует кортежа t" 6 s, для которого определено Tj и t!'[Rmf\Tv) = ¿'[Я™ П Tv}. В этом случае схему Rm будем считать критической, поскольку ее наличие в Tj препятствует образованию кортежа для соединения, состоящего из Ri и совокупности схем из Tj \ R^ и Tv.

Лемма. Схема Rjq тогда и только тогда может быть критической, когда

существует последовательность Я{, Л^, Л/2,..., Я^, Я*, п > 2, 1 < д < п, где соседние элементы последовательности имеют непустое пересечение друг с другом, а не соседние элементы последовательности Л^, Я^, ..., Л^ имеют пустое пересечение друг с другом.

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

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

Предварительно рассмотрена оценка мощности 5 для двух отношений Я\ ^и Л2. Пусть \Ях\ = N1, \Я2\ ~ N2 - мощности отношений, X = Я\ П Л2 ф 0 - совокупность общих атрибутов для Л\ и Л2у к\ - мощность X в схеме Я\, к2 - мощность X в Я2 , к - мощность X в соединении Я\ N Я2. В общем случае выполнены соотношения: к < к\, к < к2, к\ < и к2 < АГ2. Далее предположим, что X содержит один атрибут, либо один обобщенный атрибут, то есть пока не будем рассматривать мощности отдельных атрибутов в X. Для построения оценки |5| - мощности 5-таблицы воспользуемся схемой генерации реализаций схем Я\ и Я2, при этом, к общих значений общего атрибута X должны присутствовать в каждой реализации и Л2, кг значений общего атрибута должны присутствовать в каждой реализа-

ции Я*, г = 1,2. Это предположение позволит формально (количественно) сохранить функциональные зависимости, если таковые есть. Результирующее соотношение для оценки:

где первое слагаемое - мощность соединения, а второе и третье - мощность остатков соединения.

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

Рассмотрена оценка мощности 5 для двух отношений - Я1 и Яг, когда множество X = Ях П Яг состоит из т атрибутов, т > 2. Это становится актуальным, если нет возможности получить экспертную оценку величин к\, ¡¿2 и к для X, как для обобщенного атрибута. Кроме того, при обобщении на множество отношений потребуется разбиение обобщенных атрибутов на подмножества. Пусть X — {Л1, Лг, Ат}, тогда

171 тп

¿ = 1,2, * = П^')'

¿«1 3=1

где Ач(Л^) - мощность атрибута Л^- в схеме Я{, А; (Л.,) - мощность атрибута в соединении Я1 и Яг, то есть количество общих значений атрибута Aj в реализациях схем Я1 и Яг. Для формального (количественного) сохранения функциональных и многозначных зависимостей должно быть выполнено: к{(А]) < Л7,-, /с(Л;) < к{(А]), г = 1,2, у = 1 ,т. Оценка мощности 5 в этом случае равна:

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

г[ = (к{ + К - 2)!(/^ - 1)! = ^ - 1 Тг (кг + Щ-1)\(кг-2)\ к{ + Щ - 1'

Далее рассматривается обобщение оценки ¡¿Ч на множество отношений Яь Яг, ..., Яп. Использование метода последовательного присоединения схем отношений не гарантирует свойства симметричности оценки мощности

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

Из способа формирования 5-таблицы следует, что оценка может быть представлена в следующем виде:

т-11(т)

где 1{тп) - совокупность номеров отношений, являющаяся сочетанием без повторений по 771 элементов из множества I = {1,2,..., n}, Q(l(m), I) - оценка мощности остатка от соединения Rjx и Rj2 м ... м Rjm, ji 6 l{m), или среднее количество кортежей соединения, не являющихся подчиненными другим кортежам в s.

Используя предыдущие результаты, имеем:

Q(l(m),I) = \ЩЩ\х Д Щ1{т)),

где

рп( „ _ kl{m)(i) - ЦХМт))) , к(ХМ™)))г'(ХМт))) г[ { )} ~ к1(т)(г) + kl{m)(i) Г,

при Х{(1(т)) т^ 0, и Pi(l(m)) = 1 при Xi(l(m)) — 0, k^m)(i) - мощность атрибутов Xi(l(m)) в соединении S(l(m)), к(Х{(1(т))) - мощность атрибутов Xi(l(m)) в соединении S(l(m) U г),

Z'(Xi(l(m))) ki(l(m) U г) — 1

Т{ кх(1(т) и г) + Л^ — 1"

^ Из предположения о статистической независимости атрибутов следует:

кцт)(г)= П

А^Хг{Цт))

к(Х{{т)) = Д ¿(А,-,г(т)иг).

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

длине записей в таблице 5. Подставив перед каждой оценкой остатка длину его записи, получим оценку объема внешней памяти.

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

Рассматривается подмножество запросов, которые могут быть формализованы в виде "универсалыюго"реляционного запроса:

тг*(«гс(Д1 * * ... * Як)),

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

Предположим, что среда хранения и обработки данных - распределенная база данных на нескольких серверах, связанных между собой достаточно скоростными каналами. Далее рассматривается схема базисного алгоритма итерирования (БАИ) для последовательности отношений: Я\, -■•> Як', Д- область просмотра отношения Я,- в соответствии с ограничениями С и текущими ограничениями из отношений Я], з < г.

Обозначим: </?(1,2,..., /с; I) - стоимость итерирования последовательности отношений Я\, Н.2,..., Як на сервере с номером I, ф( 1,2,..., к] I) - стоимость формирования результата итерирования на сервере I. Общие затраты итерирования определяются суммой: <р+ф, где у? - включает в себя количество операций ввода и затраты на передачу исходных данных на сервер I, ф -количество операций вывода на севере I.

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

Ч>{г,3\1) + Ф(1,гЛ) тгп{(г,У;/)}.

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

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

максимального сокращения промежуточных результатов на начальных итерациях: ф/(р —► min, приводит к передаче значительных по объему промежуточных результатов по сетям связи.

Вычисление функций <р и тр осуществляется на основе статистики, формируемой в процессе эксплуатации баз данных. Достаточно эффективной методикой сбора статистики является интервальное оценивание распределения атрибутов: (N, к, d, {а,-, 6», iVj, % = 1,..., п), где N - мощность отношения (количество кортежей) в Я, к - мощность атрибута (количество различных значений в R, d - минимальная разница между различными значениями атрибута, п - количество интервалов, а* - нижняя граница интервала, 6* -верхняя граница интервала, Ni - количество значений атрибута в интервале (a.i,bi). Величины к и d могут быть получены экспертным способом. Количество различных значений на интервале может быть получено по формуле: ki = kNi/N. Корректировка данного значения может быть выполнена с использованием величины d: ki <1 + (b{ ~ ai)/d.

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

n ki »=i ]=1

где Cij — <атрибут><операция><атрибут>, либо Cij — <атрибут><операция><константа>.

Далее рассматривается схема реализации ограничений С в процессе итерирования отношений, с использованием свойств ДНФ. Обозначим через т результат итерирования запроса, Г2 — Ri х Яг х ••• х Я*, П = acfa),

Теорема. БАИ и схема реализации ограничений корректно формируют }результирующее отношение: г = г0.

Пусть в запросе указано несколько Я», принадлежащих одной S-таблице, либо одному кластеру (ORACLE), либо одно и то же отношение несколько раз присутствует в запросе под различными расширенными именами. Такие отношения назовем совместно хранимыми. При реализации запроса в этих условиях чаще всего более целесообразно только один раз просматривать ¿-таблицу, кластер, либо дублированное отношение.

При генерации схемы итерирования очередным выбранным отношением является Rj, для которого не итерированными и совместно хранимыми являются отношения Rii,Ri2,Rip. Для каждого Rit, s — осуществляем

проверку. Если для и Щ, заданы условия естественного соединения и они хранятся совместно в ¿"-таблице либо в кластере, то Я^ дополняется к схеме итерирования без генерации нового результирующего отношения. В противном случае, генерация нового результирующего отношения для Я*, целесообразна, если: <р(т; I) < где Я™. - результат итерирования Я»,.

Далее вместо Яг-4 используется Ят.

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

В пятой главе рассматривается математическая модель графических данных специального вида и алгоритмы для работы с этой моделью. Рассмотрена реализация модели для представления фазовых диаграмм в координатах: давление Р, температура Т, состав, определяемый для п-компонентной системы с помощью п — 1 значений мольных долей х^ г-го компонента, г = 1, п — 1. Области на фазовой диаграмме соответствуют нахождению вещества (системы) в каком-либо состоянии (твердое, жидкое, газообразное и т.д.), границы между областями соответствуют переходу из одного состояния в другое. Такая информация перед использованием должна пройти процедуры сбора, экспертизы и согласования.

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

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

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

3. Система управления файлами. Эта часть программного обеспечения предназначена для записи, чтения, сортировки и поиска необходимой ин-

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

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

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

1. Элемент размерности г, г = 1, п, ограничен элементами размерности г— 1,г —2,...,0, принадлежащих исходному элементу и одновременно соседним элементам той же размерности. Для реализации этого принципа введены номера элементов и для каждого элемента размерности г — 1 указываются номера элементов размерности г, которым он принадлежит.

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

3. Элементы (границы) размерности п — 1, п — 2, ..., 1 не должны содержать ложных экстремумов и точек перегиба.

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

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

Пусть Еп Евклидово пространство размерности п с ортогональным базисом е\, ег, е„. Скалярное произведение и норма в Еп определяются обычным образом:

где а,-, &г-, г = 1,п - действительные числа.

В пространстве Еп рассмотрим области г = 1, ЛГ, где N конечно.

а,Ье Еп, а = (ах, <22,..., ап), Ь = (&ь Ь2,Ьп),

п

Свойство.

ЛГ 1=1

Свойство.

П,- Л О,- = Г,,, г, 3 = "ЦТ/, г

где замкнутая вполне ограниченная область в Еп размерности п—1, п—2, ..., 1, 0. Существуют пары индексов (г,]), для которых Г,у = 0, Причем, Гу таковы, что любое замкнутое связное множество, имеющее непустое пересечение с более чем одной областью П^ обязательно будет иметь непустое пересечение с какой-либо границей Гу.

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

Пусть

г* = и Г3>

91

где границам Г?] соответствуют однозначные и непрерывные функции Л?],

= 1, /г(г, которые в совокупности задают границу Гу раздела областей

и П,. В силу однозначности Л?] возможна следующая конкретизация индексов г и Пусть нижний первый индекс г является номером области, соответствующей большим значениям х^ относительно Гу, а нижний второй индекс з - номер области, соответствующий меньшим значениям х^. Каждой границе Г?- поставим в соответствие тройку (г, у, д{}.

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

Теорема. Среди областей ¡¡7», г = 1, имеется одна и только одна область Г),о неограниченная в Еп при п > 2.

Теорема. Все области Г2,, г = 1, ТУ, кроме неограниченной Г^о, являются компактными, а область П,о - локально компактна.

Рассмотрим для Г^- включающий прямоугольник Ру, задаваемый отрезками [а,1, а?], а} < а?, для г-той компоненты Х{ вектора х — (х\, Х2, ..., хп) € Еп. Причем,

если х 6 Г§, то х € Ру1 ■ Вообще говоря, существует целое семейство включающих прямоугольников для Г^. Однако будем рассматривать минимальный из них Р?1, для которого разности а? — а-, х = 1, п, минимальны. В силу замкнутости и ограниченности Г?] все а} и а? существуют и конечны. Введем в рассмотрение ось Ь в Еп, задаваемую точкой х° Е Еп и вектором конечных приращений ¡3 = (¡3\, (З2, •■•> А») но

каждой координате

L = {х € Еп\х = х° + aß, aeR, а> 0}.

Причем, существует г, для которого Д- 0. Ось L может иметь непустое пересечение с J^1, L(i,j, qi) — L Г) Очевидно, что L(i,j,qi) замкнуто и ограничено, если q\) ^ 0. Рассмотрим множество Mk(i,j,q\) С L(i,j,qi), состоящее из к точек ..., х^к\ где я*1) и х^ - концы от-

резка L(i,j, qi). Множество Mk(i>j, q{) образует разбиение L(i,j, qx) на к — 1 интервалов одинаковой длины: — ' = — х^||, г = 2, /с — 1,

где к > 2 конечное целое число. _ Определение. Область f2j будем называть к - размытой, если выполне-™но:

■ (ij)

тогда

где i и q\ принимают все значения из существующих троек (г, j, qx) и (j, г, qx) с фиксированным номером г области £2». Получим оценку величины А;.

Прямоугольник Р* в Е71 задается парой векторов: а1 = (aj, а\, а*), а2 = Ясно, что максимальная длина отрезка Дг, j,<ji) равна

||а2 — а1||. Обозначим.через ГДу границу области Аи ry = min ЦГ^- —

ГД«||.

Теорема.

\а2 — а1'

fc> ^-Ü- + 1.

гу

Важное свойство к - размытых областей:

Теорема. Если область является к - размытой, то она является (&+1) размытой.

Далее представлены алгоритмы для работы с графическими данными для рассмотренной модели. Базисным является алгоритм, определяющий номер области по фиксированной точке х°, где я0 € причем, точках0 может принадлежать нескольким областям, если она лежит на границе.

Основная идея алгоритма заключается в последовательной проверке неравенств:

оу - х1п - лчр"

(х°) < х1_г < (х°),

< ^ <

где p' = 1, p" — 0; cfn и такие, что разность между правой и левой частями неравенств минимальна.

На последнем шаге строится последовательность:

<43, - - «f,.-. «S. - -

Если в этой последовательности нет нулевых элементов, то из нее выбираются наибольшие отрицательные элементы af*^их может быть несколько, и наименьшие положительные а^. При этом возможны следующие ситуации: 1) все элементы последовательности положительны или отрицательны, а также, если в последовательности нет ни одного элемента, то решением! алгоритма будет г° номер неограниченной (внешней) области; 2) в последовательности найдены элементы af*^ и af'jp. Среди них выбираем, такие, что is — jP, и этот номер будет решением алгоритма. Если в последовательности имеются нулевые элементы, то все индексы inj при них дадут решение алгоритма, т.е. номера областей, для которых точка х° является граничной.

Определим оператор проекции W\x вдоль координаты xix, который является матрицей п х га, на главной диагонали которой стоят единицы, кроме строки 1\. Все остальные элементы матрицы нулевые.

Лемма- Элемент a?j присутствует в последовательности тогда и только тогда, когда W^x0

Определим множество S={a;€ En\Wixx — W^x0}.

Лемма. Множество S П Tfj может иметь не более одной точки, причем, если х' е 5 П Г§, то x'h = Af^x1).

Теорема. Индекс i будет. решением алгоритма тогда и только тогда, когда ж0 € fit.

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

Следующий алгоритм определяет границы области в заданном направлении. Он позволяет определить предельную точку области ft» в направлении оси L, где L задается фиксированной точкой х° € П» и вектором относительных приращений ß. Рассмотрим схему вычисления интервала .

а« _ хо _

&l = max[0, lim 5 'j, s = 1, n, t = 1,2 ;

h—*+0 ps -+- Ii

{

ai = äi и al = öt23 для ß, > 0, — и öt23 — äl для ßs < 0.

Получен набор интервалов (а], а*), 5 = 1, п, для прямоугольника Р?> и фиксированной оси Ь. Интервал из набора будет считаться пустым, если а* > а*. Причем. € (а*, а^), если а\ конечно, ¿=1,2. Тогда

Используя определение для (3, нетрудно показать, что интервал /?? будет конечным или пустым, иа>0 для а € /у. Обозначим:

Теорема. О =

Идея алгоритма заключается в том, что для каждой тройки (г, <?х), соответствующей поверхности строится отрезок Цг,,7,91), который разбивается на к — 1 равных отрезков. Таким образом определяются к точек (концы отрезков). Для этих точек определяется область, которой каждая из них принадлежит. При этом, свойство к - размытости гарантирует обнаружение перехода в другую область Qj, если ось Ь(г, имеет непустое пересечение областью % без погрешности определения ее границ. После определения двух точек, ближайших к обнаруженной границе и находящихся в различных областях, точка пересечения с границей уточняется дихотомией, поскольку на данном интервале пересечение оси 1) с границей единственно.

Теорема. Алгоритм в пределах погрешности находит граничную точку х области такую, что норма |[х — минимальна.

Другой подход, основанный на "шагании"вдоль оси для фазовых диаграмм имеет оценку количества итераций N2 < 109, тогда как предложен-^^гый алгоритм имеет оценку N1 < 103.

Далее рассматриваются алгоритмы построения функций для аппроксимации границ Г']. Для этих целей традиционно используются задачи интерполяции и сглаживания функциональных зависимостей, заданных в виде таблиц экспериментальных точек. Однако, есть приложения, где неприемлемо раздельное использование чисто интерполяционных или чисто слаживающих сплайн-функций. Например, обработка и представление фазовых ' диаграмм. Каждая поверхность на фазовой диаграмме содержит два типа точек: 1) внутренние точки, измеренные с большой погрешностью, 2) граничные точки, измеренные, как правило, с высокой точностью и, кроме

п

Х&ь яг) = {х е ЕГ I я = + ар, а €

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

Определим гильбертовы пространства: X - пространство аппроксимирующих функций; - пространство интерполируемых данных, - пространство сглаживаемых данных, У - функциональное пространство, содержание которого в последствии будет ясно. Р — У х 2Г2, где х - декартово произведение.

Рассмотрим также, линейные операторы: А\ : X —> £"1, А2 : X —► Т : X —* У, Ь : X —* Г, т.е. Ь — [Т, А2]. А\ и Ач - операторы следа функции из X, Т - энергетический оператор, скалярное произведение и норма в X, У, ¿?1, /?2 определяются обычным образом. В Р:

(/1,/2)р = «(У1,У2)у + (г21,г22Ьа, ||/|& = (/,/)*•, (1)

где /1 = [у1, га1], /2 = [у2, *22]; Д /2, / € Г; у\у2 е У; г2\ € а > 0.

Введем в рассмотрение множество С X:

12 = {хе Х\А\х = ги гх € гх].

Задача смешанной аппроксимации запишется в следующем виде:

Фа(а) = ппп Фа(х) = пнпа||Тх||у- + \\А2х - х2\\\, (2)

хе1г хе/г

где сг Е — искомое решение.

Используя (1), легко показать, что

Фв(<т) = шт — аЦ^,

х 6/г

где а = [ву, г2] € Р, 9у ~ нулевой элемент пространства У.

Определим ядра операторов И^Г) — {х е Х\Тх = 9у}, N^1) =. {а: € Х\А1Х = 921}, ЩА2) = {хе Х\А2х = 02з}, ЩЬ) = {хе Х\Ьх = где ву, Вгх, нулевые элементы пространств У, 2а, Р, соответственно,

причем ^ = [0У,

Теорема. Если множества ТМ(Аг) и Л2ЛГ(Л1) замкнуты в пространствах К и ¿Г2 соответственно, ^ 0 и 7У(Т) Г) //(Л1) П = {0*}, то сплайн <т, решение задачи (2), существует и единственен.

Пусть X конечномерное функциональное пространство с линейно-независимым базисом и>2, и>п на Г2,где - замкнутая ограниченная односвязная область в Л.т.

п

В этом случае х — ^^»ОО» * € П. Запишем задачу (2) в следующей

1=1

форме:

А\Х = ¿1; (3)

|2 —> ПШ1. (4)

После некоторых преобразований задача (3) - (4) запишется в следующем виде:

Фв(а) = а(Та, а) + (Ца, а) - 2(Тг, а)+

где Л п - мерный вектор множителей Лагранжа.

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

аГ + Лз Ах Ах

где Ах =

Дла реализации алгоритма в виде программного обеспечения было определено:

к+1 &+1 то

® = = £ - £ *»<»".<« (5) »1=1 »т=1 3=1

Назовем полиномом специального вида, т.к. наивысшая степень его равна кт, однако, вдоль каждой координаты он имеет степень к.

В области П, в соответствии с операторами А\ и Л2, заданы два набора точек ¿1 = з = 17Ж}, Ь = (4У), з = МЪ}-

Обозначим через 7Г/ полиномы обычного вида в Пт степени I. Теорема. Задача (2) однозначно разрешима на полиномах вида (5) тогда и только тогда, когда не существует полинома 7гд_х ф 0, для которого выполнено равенство

■Кд-г(Ьи)) = 0, ¿и) € ¿1 и <2.

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

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

В разработанном алгоритме использованы традиционные соотношения для аппроксимирующей конструкции. Заданы три вектора: х = {х\,х-2,---,хм) ~ узлы аппроксимации, / = (Л, /2, 1ы) - значения функции в узлах, Д/ = (Д/ь Д/г,Д/лО погрешность измерения функции в узлах. Для х € [з^-ьж,-] сплайн имеет вид

где ] = 2, Л/", значение второй производной сплайна в ; - ом узле, = х^—х^-х, уз = Для заданной конструкции являются непрерыв-

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

^ | с + ^ _ У}+1 ~ Уз Уз ~ Уз-1 3 6 3 3 . Щ '

3 = 2,N-1,

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

Вз = Лу + Я, (б)

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

При решении задачи интерполяции имеем у = /, что позволяет построить из соотношения (б). При сглаживании у^/, поэтому используется следующее:

mm,

где 0 < р < 1.

После дифференцирования и подстановки соотношения я = В~1(Ау + Л) получим систему линейных уравнений в матричном виде:

где D - диагональная, a L - трехдиагональная матрицы.

На основании решения систем уравнений (7) и (6) можно определить Sp{x). В пакете программ реализован режим повторного входа, позволяющий быстрее получить решение для различных значений параметра р и вектора А/.

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

Преобразование 1 (П1). = ají - значения ají атрибута Aj становятся атрибутами нового отношения. В работах Цаленко М.Ш. такое преобразование названо семантической трансформацией и рассмотрен образ функциональной зависимости, левой частью которой являются ключевые атрибуты отношения.

Преобразование 2 (П2). R* — Ri-Aj - отношение Ri преобразуется во Щрлножество отношений, в каждом из которых на атрибут Aj накладывается ограничение типа равенство и этот атрибут удаляется из результирующих отношений.

В соответствии с предложенным методом построения отображения для П1 получены результаты по всем пяти шагам этого метода. Пусть R - исходное отношение базы данных; г,- - кортеж в реализации г исходного отношения, i = 1, N; X - множество атрибутов из R, остающихся без изменения в результирующем отношении; У - множество атрибутов из R, значения которых становятся именами атрибутов в результирующем отношении; Z

(pD+{ 1 - p)(B-1A)TLB~1A)y = = pfD + (1 - р) (B~lA)TLB~lR,

(7)

- множество атрибутов из R, области определения значений (домены) которых, дополненные пустым значением, распределяются между доменами вновь введенных атрибутов. Причем, атрибуты У и Z отсутствуют в результирующем отношении, X Г\У = Ф, X П Z = У П Z — X иУ U Z = R.

Правило построения схемы представления:

Sch(R) = {X, У, Z} Sch(R') = {X, Dam{y) х {Z}},

где Sch - схема описания отношения, R* - результирующее отношение, Dom

- множество допустимых значений атрибутов, х - декартово произведение, Dom(Y) = Dom{Yx) х Dom(Y2) х ..., Ys € У, | Вот(У) |= М, | {Z} |= Ь^ 1 • | - мощность множества. "

Для построения представления т* разработан алгоритм первоначальной

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

,T/N — 1 радий: N(—---L).

Важным свойством рассмотренного алгоритма является: если какое-либо значение r\[y.ZpJ ф emp, то r\[y.Z^[ ф emp, р — 1, L, если какое-либо значение г {[у, ZPi] = emp, то r{[y.Zp] = emp, р = 1, L.

Теорема. Для произвольной реализации г схемы R отношение г* существует тогда и только тогда, когда г удовлетворяет функциональной зависимости ХУ —+Z.

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

Пусть V' С V - множества атрибутов, если выбран атрибут Vq € V, то Vo g V', множество V' может быть пустым. Определим, что пустые значения не равны друг другу.

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

1. (FXX). Если X' —> Xq удовлетворяет г*, то X' —+ Xq удовлетворяет г.

2. (FYX). Если для произвольных строк г*, т2 € г* из условия r{[y[.ZpJ ф emp, r*2[y2.ZP2\ ф emp, где у[ С ^ С у2- G Dom (У) и = следует = г^рГо], тогда У —* Х0 удовлетворяет г.

3. (FZX). Если из условия r{[y{.ZpJ = r2[y2-Zp^, i — 1,1, ZPi e Z' для произвольных строк r{,r2 € г*, следует т\[Х0] = г^Хо], тогда Z' —> Х0 удовлетворяет г.

Очевидно, что функциональные зависимости с более сложной левой частью (комбинации атрибутов из X, У и Z) и атрибутом Xq в правой

части, будут выражены в образе г* в виде конъюнкции ограничений 1 -3. Пусть V = X' и У и ¿Г', зависимость V —► Ха будет иметь образ < ЕХХ > к < ЕТХ > & < РгХ >. Если какое-либо множество X, У или 2 пусто, то соответствующее ограничение считается выполненным.

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

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

Семантика отношения г* такова, что в нем допустимы следующие опера-^^ции:

1. Дополнение значений Zv в существующие строки.

2. Модификация значений

3. Удаление значений Zp.

4. Дополнение новой строки для ввода значений

Остальные преобразования г* либо являются следствием перечисленных, либо не имеют смысла.

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

Для построения отображения П2 достаточно выделить две группы атри-

бутов: X и У", где Л = ХиУиХПУ = 0. Пусть X = {Х( | » = 1,ЛГ} -

множество атрибутов, на которые накладываются ограничения типа равенство, и они удаляются из результирующих отношений, и У = {У} — М} - множество атрибутов, остающихся в новом отношении в качестве атрибутов.

Правило формирования схемы образов Щ:

где X] - выражение, эквивалентное — хц € Иот^ХКоличество отношений - образов для данного преобразования равно Ь = Лот(Х).

= {X, У} БсЦЩ) = SchiR.Xl.Xi.Xlf) = {У} = {Х,У} = SchiR.Xl.Xl.Xl) = {У}

5сЛ(Я) = {Х,У} 5с/г(Я2) = 5сЬ(ЯХ[.Х}.Х^) = {У},

Формирование реализации образа достаточно использования операций реляционной алгебры:

rf = 7rr(aF((r)),

N

где 7Г - проекция, а - селекция, Fi= Д [Х{ = хц).

г-1

Далее рассмотрены образы в г* функциональных и встроенных многозначных зависимостей.

Кроме того, важными являются следующие свойства. Обозначим: V' — V \ X, где V - произвольное множество атрибутов, X - ранее определенное множество атрибутов. Положим, что значение кортежа на пустом множестве атрибутов есть константа: ¿[0] = const. 4

Теорема. Если функциональная зависимость W —> S удовлетворяет г, то зависимость W' —* S' удовлетворяет любому образу rf.

Теорема. Если встроенная многозначная зависимость W —w S(T) удовлетворяет гяХ С W, то зависимость W' —S'(T') удовлетворяет любому отношению rf.

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

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

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

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

дующих направлениях: 1) разработка новых моделей данных, 2) разработка новых алгоритмов межмодельных преобразований данных. Для создания гиперкубического представления данных таблица соединений является слишком универсальной, для этого достаточно использовать частный случай: модель данных "Таблица ограниченных связями соединений", что позволит избавиться от необходимости указания отношений, участвующих в соединении, при генерации приложения, и вычислять эти отношения по атрибутам (координатам гиперкуба) с использованием связей на схеме данных. Кроме того, обобщение модели гиперкуба на случай списка значений и таблицы значений в одной ячейке исходного гиперкуба позволит существенно расширить область применения рассмотренной в работе технологии. Новые ^ алгоритмы преобразований становятся актуальными при массовой загрузке ™ значений из пользовательского представления данных в исходную базу данных (в работе рассмотрены образы операций при модификации единичных значений). Все это потребует формулировки новых условий существования представлений и тщательного исследования свойств моделей и алгоритмов.

В качестве приложений рассмотрены следующие разработки: 1) пакеты программ по смешанной аппроксимации; 2) сценарий работы системы FazDiagr; 3) сценарий использования мастер-форм для генерации приложений; 4) архив-СМ.

Список публикаций по теме диссертации

[1] Дробышев Ю.П., Зыкин C.B. Идентификация областей ограниченных n-арными поверхностями// Системы и методы анализа данных. - Новосибирск: ВЦ СО АН СССР, 1984. - С. 53 - 58.

[2] Дробышев Ю.П., Зыкин C.B. Программное и математическое обеспечение базы данных фазовых диаграмм (БДФД) // Применение математиче-

^^ ских методов для описания и изучения физико-химических равновесий, ф Т. 1. - Новосибирск: ИНХ СО АН СССР, 1985. - С. 177 - 181.

[3] Дробышев Ю.П., Зыкин C.B. Алгоритмы и программное обеспечение информационной системы по фазовым диаграммам// Автометрия. - 1986. - N 1. - С. 47 - 53.

[4] Зыкин C.B. Алгоритм определения предельной точки области в заданном направлении// Структуры и анализ данных. - Новосибирск: ВЦ СО АН СССР, 1985. - С. 91 - 100.

[5] Зыкин C.B. Смешанная аппроксимация// Математические модели представления информации и задачи обработки данных. - Новосибирск: ВЦ СО АН СССР, 1986. - С. 72 - 79.

[6] Зыкин C.B. Программное обеспечение для автоматизированных информационно - вычислительных систем// Информатика и вычислительная техника в учебном процессе и управлении. - Омск: ОмГПИ, 1988. - С. 177 - 178.

[7] Зыкин C.B. Вопросы подготовки специалистов в области информатики// Новые информационные технологии в учебном процессе и управлении.

- Омск: ОмГПИ, 1989. - С. 131 - 132.

[8] Зыкин C.B. и др. Комплекс программ для анализа радиосетей переда^^ чи информации// Системы моделирования в радиотехнике и связи. -Новосибирск: ВЦ СО АН СССР, 1989. - С. 77 - 78.

[9] Зыкин C.B. Алгоритмы аппроксимации табличных функциональных зависимостей/ / Системы моделирования в радиотехнике и связи. - Новосибирск: ВЦ СО АН СССР, 1989. - С. 107 - 113.

[10] Зыкин.C.B. Архив - СМ: Препринт/ ВЦ СО АН СССР. N 848. - Новосибирск. 1989. - 13 с.

[11] Зыкин C.B. Отображение типа "Соед1шение"реляционной модели данных в списковую модель физического уровня описания данных: Препринт/ ВЦ СО АН СССР. N 902.. - Новосибирск. 1990. - 28 с.

[12] Зыкин C.B. Оценка мощности списка для отображения типа "частичное соединение"// Кибернетика и системный анализ, 1993. - N 6. - С. 142 -152.

[13] Косяков В.И., Зыкин C.B., Малахов Д.В. Согласование данных по фазовым равновесиям. 1. Основы метода// ЖФХ. - 1989, - T. LXIII. - N

- С. 329 - 333.

[14] Косяков В.И., Зыкин C.B., Малахов Д.В. Согласование данных по фазовым равновесиям. 2. Участок ликвидуса системы: RbNOz — Sr{NOz)il/ ЖФХ. - 1989. - T. LXIII. - N 3. - С. 525 - 527.

[15] Зыкин C.B. Отображение реляционной модели данных в списковую модель типа "частичное соединение"// Информационные системы в науке

- 95. - М.: Фазис, 1995. - С. 49 - 50.

[16] Зыкин C.B. Технологий информационного обеспечения процесса принятия решений// Проблемы оптимизации и ее приложения. - Омск: ОмГУ, 1997. - С. 76 - 78.

[17] Зыкин C.B. Формирование пользовательского представления реляционной базы данных с помощью отображений// Программирование. - 1999. - N 3. - С. 70 - 80.

[18] Зыкин C.B. Метод межмодельных отображений в базах данных. Новосибирск: ИНПРИМ-2000. - Ч. 2. - С. 163.

[19] Зыкин C.B. Разработка прикладных программ для баз данных// Математические структуры и моделирование. Вып. 7. - Омск: ОмГУ, 2001.

! - С. 139 - 156.

[20] Зыкин C.B. Соответствие состояний реализации исходной и целевой моделей данных// Международная конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова. - Новосибирск, 2001. - С. 237 - 241.

[21] Зыкин C.B. Построение отображения реляционной базы данных в списковую модель данных// УСиМ. - 2001. - N 3. - С. 42 - 63.

[22] Зыкин C.B., Кукин A.B. Построение математической модели учебного процесса для долгосрочного планирования// Математические структуры и моделирование. Вып. 10. - Омск: ОмГУ, 2002. - С. 77 - 86.

[23] Зыкин C.B. Инструментальные средства разработки приложений для работы с базами данных// Материалы V Международной научно-технической конференции "Динамика систем, механизмов и машин". -Омск: ОмГТУ, 2004. Кн. 1. - С. 376 - 380.

[24] Зыкин C.B. Создание приложений на основе межмодельных преобразований данных// Материалы III Международного технологического конгресса "Военная техника, вооружение и технологии двойного применения". - Омск: ОмГУ, 2005. - Ч. II. - С. 66 - 69.

[25] Zykin S.V. Relation queries execution under the estimators control. - M.: ADBIS'95, 1995. - V. 2. - P. 52 - 55.

[26] Zykin S.V. Generation of User View for a Relational Database by Mappings// Programming and Computer Software. - V. 25. - N. 3. - 1999. -P. 173 -183.

ЗЫКИН Сергей Владимирович

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

05.13.17 — Теоретические основы информатики

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

Подписано в печать 03.10.2005. Формат 60x84 1/16. Печ.л. 2,0. Уч.-изд.л. 2,0. Тираж 100 экз. Заказ 451.

Издательство ОмГУ 644077, Омск-77, пр. Мира, 55-а

Предисловие

Введение

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

1.1. Формирование схемы целевой модели.

1.2. Разработка алгоритма построения представления целевой модели.

1.3. Определение образов ограничений целостности.

1.4. Формирование образов операций преобразования целевой модели.

1.5. Формирование образов операций преобразования исходной модели.

2. Модель данных "Таблица соединений"

2.1. Логическая структура ¿"-таблицы

2.2. Формирование начального состояния ¿-таблицы.

2.3. Ограничения целостности для 5-таблицы.

2.4. Операции преобразования 5-таблицы.

2.4.1. Дополнение кортежа r[S] к 5-таблице s.

2.4.2. Удаление кортежа r[S] из 5-таблицы s

2.4.3. Замещение кортежа r[iL>] в S-таблице s кортежем г'[5]

2.5. Образы операций преобразования РБД.

2.5.1. Дополнение кортежей.

2.5.2. Удаление кортежей.5G

2.5.3. Модификация кортежей.

2.5.4. Некоторые замечания по модификации 5-таблицы G 2.6. Выводы по таблице соединений.

3. Оценка мощности реализации таблицы соединений

3.1. Оценка мощности 5-таблицы для двух отношений и одного общего атрибута.

3.2. Оценка мощности 5-таблицы для двух отношений и множества общих атрибутов.

3.3. Оценка мощности 5-таблицы для множества отношений

3.4. Замечания по использованию таблицы соединений

4. Выполнение реляционных запросов для специализиро

Ф ванных моделей представления данных

4.1. Подход к построению схемы выполнения запроса.

4.2. Схема реализации запросов на специализированных моделях

4.3. Замечания к схеме реализации запросов.

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

5.1. Описание диаграммы состояний

5.2. Математическая модель диаграммы состояния.

• 5.2.1. Выбор способа представления диаграмм состояния

5.2.2. Математическое описание диаграмм состояния

5.3. Алгоритм идентификации областей

5.4. Алгоритм определения границы области в заданном направлении

5.5. Алгоритмы смешанной аппроксимации

5.6. Замечания к модели диаграмм состояния.

6. Структурные преобразования табличного представления данных

6.1. Построение преобразования 1.

6.1.1. Правило построения схемы представления

6.1.2. Алгоритм построения представления г* со схемой

6.1.3. Условия существования представления г*.

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

6.1.5. Операции преобразования представления.

6.2. Построение преобразования 2.

6.2.1. Правило формирования схемы образов Щ.

6.2.2. Формирование реализации образа. ф 6.2.3. Правила преобразования зависимостей

6.2.4. Операции манипулирования данными.

6.3. Замечания для преобразований.

7. Информационная система по фазовым диаграммам

7.1. Общая структура программного обеспечения и этапы обработки информации.

7.2. Программы обработки исходной информации.

7.3. Система управления файлами (СУФ)

7.4. Управление прикладными программами.

4 7.5. Язык запросов

7.6. Обсуждение реализации системы.

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

8.1. Общие функции программного обеспечения.

8.2. Организация интерфейса между исполняющими средами

8.3. Обсуждение реализации программного обеспечения

Актуальность темы

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

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

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

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

Цель работы

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

Научная новизна

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

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

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

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

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

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

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

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

Модель описания диаграмм состояния и алгоритмы работы с ней были использованы в ИНХ СО РАН для исследования моделей физико-химических соединений и формирования информационной базы по диаграммам состояния. Технология построения таблиц соединения и "семантическая трансформация"использовались при формировании пользовательских приложений для организации учебного процесса в ВУЗе на примере СибАДИ (г. Омск).

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

Апробация

Результаты работы доложены на конференциях и семинарах, среди которых:

Пятая всесоюзная школа: "Применение математических методов для описания и изучения физико-химических равновесий". - Новосибирск: СО АН СССР, 1985.

Пятая научно-практическая конференция "Информатика и вычислительная техника в учебном процессе и управлении". - Омск: ОмГПИ,

1988.

Шестая паучио-практическая конференция "Новые информационные технологии в учебном процессе и управлении". - Омск: ОмГПИ,

1989.

Доклад на семинаре Института прикладной информатики под председательством Ю.П. Дробышева и с участием сотрудников СКТБ при ИК HAH Украины. - Киев, 1993.

Конференция "Информационные системы в науке - 95". - Москва, 1995.

Международная конференция "ADBIS'95". - Москва, 1995.

Международная конференция "Проблемы оптимизации и ее приложения". - Омск, 1997.

Доклад на семинаре Института систем информатики им. А.П. Ершова СО РАН под председательством Поттосина И.В. - Новосибирск, 1998.

Международная конференция ИНПРИМ-2000. - Новосибирск, 2000.

Международная конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова. - Новосибирск, 2001.

Доклад на научно-исследовательском семинаре "Автоматизация программирования"Московского государственного университета (факультет ВМиК) под руководством Шура-Бура М.Р., Москва, 2003.

Публикации

По теме диссертационной работы опубликовано 26 работ, из них: статьи в центральных журналах - 7, статьи в сборниках СО РАН - 5, статьи в местных изданиях - 2, доклады на международных конференциях - 6, тезисы доклада па конференциях - 4, препринты - 2.

Введение

Проблема использования информационных ресурсов была сформулирована основоположником реляционной модели данных - Е. Коддом с соавторами [87]: ". обладание большой корпоративной БД имеет маленькое значение, если конечные пользователи ие имеют возможностей легко синтезировать необходимую информацию из этих запасов (складов) данных". Эта ситуация обусловлена тем, что весь сервис работы с информационными ресурсами создается прикладными программистами и, как следствие, необходимая информация к моменту ее получения перестает быть актуальной.

Понимание этой проблемы вынуждает разработчиков программного обеспечения информационных систем дополнять свои продукты соответствующим инструментарием. Примером для сильиострук-турированных моделей данных могут служить разработки: Oracle Express, InfoVizor и т.д., для слабоструктурированных: Netscape, Internet Explorer и т.д. Эти системы обладают широким спектром возможностей: быстрое создание форм для просмотра и редактирования данных, создание отчетов с возможностью расчета интегральных характеристик, вплоть до построения диаграмм, и т.д. Однако создание инструментария осложняется отсутствием формализованных моделей пользовательских данных и, как следствие, необходимо программировать интерфейсы при преобразовании данных из одного представления в другое. Об оперативном предоставлении информации пользователю в этом случае не может быть и речи.

Широко известны канонические модели данных: реляционные, сетевые, иерархические, объектные, объектио-реляциопиые и т.д. Их использование позволяет наиболее полно реализовать принцип независимости данных при построении схемы базы данных. Над этими моделями трудилось огромное количество исследователей, в том числе Чарльз

Бахмаи и Эдгар Кодд, получившие в свое время премию Тьюринга соответственно за сетевую и реляционную модели данных. В настоящее время ведутся активные исследования в области построения моделей пользовательского представления данных (табличные, гиперкубические, темпоральные, семантическая трансформация, таблицы соединений, графические и т.д.) с использованием преобразований и интеграции неоднородных информационных ресурсов. Множество публикаций посвящено проблеме использования представления данных в формате XML, например [48, 50, 51, 76, 77] и др. В этих работах слабоструктурированное представление данных используется в качестве исходного. Поскольку XML является достаточно стандартизованным, то появляется возможность построения преобразований и интеграции данных, как это сделано в работах [51, 76, 77].

В данной работе в качестве исходной используется реляционная модель, относящаяся к сильноструктурированным моделям. Наиболее популярны для этого класса поликубические и гиперкубические модели, предназначенные для аналитической работы с данными [40, 47, 65, 78, 83, 89, 91, 97] и др. В большинстве работ авторы не приводят формальное описание пользовательских моделей, ограничиваясь примерами. Это затрудняет анализ этих моделей и соответствующего им инструментария. Однако, общая ситуация такова. Реляционные модели признаются наиболее универсальными (в силу своих свойств), то есть по реляционному представлению можно сформировать любое другое. Это нельзя сказать про поликубичсские и гиперкубические модели, например, при необходимости формирования другого гиперкуба пригодной исходной моделью будет только реляционная. Особое внимание авторы обращают на скорость работы приложений, хотя это не всегда оправдано. Можно потратить значительные усилия и время на разработку приложения, которое с течением времени может оказаться не актуальным. В этом случае эффективнее быстрое формирование приложений.

Соответствующая технология и является результатом исследований, рассмотренных в данной работе.

Результаты построения пользовательского представления информации (поликубические и гиперкубические) в последующем могут быть использованы в рамках других моделей: регрессионных, деревьев решений, кластеризации и т.д. В данной работе рассматривается проблема преобразования информации к графическому виду па примере диаграмм состояния физико-химических соединений. Известно множество моделей описания и представления графической информации [1, 8, 27, 63] и т.д. Проблему графического представления диаграмм состояний одними из первых начали решать в МГУ [52, 98]. В последствии этой проблемой занялись и в других учреждениях, в том числе и в ИНХ СО РАН. В рамках проекта банка данных по свойствам материалов электронной техники (БнД СМЭТ) автором данной работы было получено обобщение известных результатов на случай многомерных диаграмм состояния. Эта модель в последствии использовалась при анализе и согласовании экспериментальных данных.

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

1) быстрое формирование приложения без привлечения языка программирования;

2) сформированное приложение должно содержать функции редактирования данных: дополнение, удаление и модификацию;

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

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

Таким образом, для создания инструментария необходима разработка специализированной пользовательской модели данных и, как следствие, для удовлетворения перечисленных требований к инструментарию между специализированной моделью данных и универсальной моделью данных должно быть установлено некоторое соответствие. Наилучшим способом установления этого соответствия является построение между ними межмодельного отображения, удовлетворяющего условию коммутативности. Это условие успешно было использовано в работах [15, 40]. Существенным отличием в данной работе является то, что между состояниями исходной и целевой моделей данных отсутствует взаимнооднозначное соответствие.

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

Обобщая проблематику использования специализированных моделей, можно предложить схему, представленную на рисунке 1, где —» -потоки сообщений, запросов, данных и т.д.; БД - база данных, БЗ - база знаний, ТД - текстовые данные, ГД - графические данные, СПИ - средства передачи информации (каналы ввода-вывода ЭВМ, общая шина, локальные сети, региональные сети и глобальные сети), ПП - пользовательское представление (электронные таблицы, текстовые и гипертекстовые процессоры, средства мультимедиа и т.д.).

Рис. 1: Схема межмодельных преобразований

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

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

Модель П будем считать исходной, а С1' =< М', ГУ, Р\ Р' >- целевой (специализированной). Следовательно, необходимо построение отображения : а => п'.

В [15] предложен следующий подход к построению преобразований: ф: й ГУ, где / - произвольное подмножество Р. Требования к отображениям:

1) взаимнооднозначное соответствие состояний хранимой информации (ф - биективно);

2) обеспечение коммутативности диаграммы отображения логических моделей информации и ограничений целостности,

М,Р) В о Ф

М', Р')

В' где стрелки без обозначений символизируют соответствующие семантические функции языков описания данных (ЯОД);

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

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

В^В Г

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

Заключение

Основные научные результаты

На защиту выносятся следующие научные положения.

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

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

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

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

Под руководством Зыкина C.B. была подготовлена и защищена кандидатская диссертация Чанышевым О.Г. "Ассоциативная модель реального текста и ее применение для автогенерации баз знаний о связях", в которой была предложена модель полнотекстовых данных для автореферировапия и автоиндексирования информационных ресурсов.

1. Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения. М.: Мир, 1972. - 316 с.

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

3. Бойко В.В., Савинков В.М. Проектирование информационной базы автоматизированной системы на основе СУБД. М.: Финансы и статистика, 1982. - 174 с.

4. Василенко В.А. Теория сплайн функций. - Новосибирск: НГУ, 1978. - 65 с.

5. Василенко В.А. Сплайн функции. Теория, алгоритмы, программы. - Новосибирск: Наука, 1983. - 215 с.

6. Василенко В.А., Ковалков М.В., Зюзип A.B. Сплайн функции и цифровые фильтры. - Новосибирск: ВЦ СО АН СССР, 1984. - 156 с.

7. Вейнеров О.М., Самохвалов Э.Н. Разработка САПР: В 10 кн. Кн. 4. Проектирование баз данных САПР. М.: Высшая школа, 1990. -144 с.

8. Гилой В. Интерактивная машинная графика. М.: Мир, 1981. - 380 с.

9. Де Бор К. Практическое руководство по сплайнам. М.: Радио и связь, 1985. - 304 с.

10. Дейт К. Введение в системы баз данных. М: Диалектика, 1998. -782 с.

11. Джексон Г. Проектирование реляционных баз данных для использования с микроЭВМ. М.: Мир, 1991. - 256 с.

12. Диго С.М. Проектирование баз данных. М.: Финансы и статистика, 1988. - 212 с.

13. Замулип А. В. Типы данных в языках программирования и базах данных. Новосибирск: Наука, 1987. - 150 с.

14. Замулип A.B. Системы программирования баз данных и знаний. -Новосибирск: Наука, 1990. 352 с.

15. Калипиченко J1.A. Методы и средства интеграции неоднородных баз данных. М.: Наука, 1983. - 423 с.

16. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. В 3 т. Т. 3. М.: Мир, 1978. - 844 с.

17. Кокорева J1.B., Малашинин И.И. Проектирование банков данных.- М.: Наука, 1984. 256 с.

18. Кульба В.В.,Ковалевский С.С., Косяченко С.А., Сиротюк В.О. Теоретические основы проектирования оптимальных структур распределенных баз данных. М.: СИНТЕГ, 1999. - 660 с.

19. Лавров С.С., Гончарова М.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971. - 160 с.

20. Лорап П.-Ж. Аппроксимация и оптимизация. М.: Мир, 1975. -496 с.

21. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. М.: Наука, 1965. - 520 с.

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

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

24. Наумов А.Н., Вендров A.M., Иванов В.К. Системы управления базами данных и знаний. М.: Финансы и статистика, 1991. - 352 с.

25. Ныомен У., Спрулл Р. Основы интерактивной машинной графики.- М.: Мир, 1976. 576 с.

26. Озкархап Э. Машины баз данных и управление базами данных. -М.: Мир, 1989. 696 с.

27. Понтрягии JI.C. Основы комбинаторной топологии. М.: Наука, 1976. - 136 с.

28. Попов A.A. Программирование в среде СУБД FoxPro 2.0. М.: Радио и связь, 1994. - 350 с.

29. Разумов О.С. Организация данных в вычислительным системах. -М.: Статистика, 1978. 184 с.

30. Роженко А.И. Абстрактная теория сплайнов. Новосибирск: НГУ, 1999. - 176 с.

31. Сигиор Р., Стегман Михаэль О. Использование ODBC для доступа к базам данных. М.: БИНОМ, 1995. - 384 с.

32. Солтоп Дж. Динамические информационно справочные системы.- М: Мир, 1979. 557 с.

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

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

35. Флорес И. Структуры и управление данными. М.: Финансы и статистика, 1982. - 318 с.

36. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и производстве. М.: Мир, 1982. - 304 с.

37. Хаббард Ж. Автоматизированное проектирование баз данных. -М.: Мир, 1984. 293 с.

38. Херш Дж., Херш К. Работа с ORACLE версии 6.0. М.: Мир, 1993.- 464 с.

39. Хисамутдипов В.Р., Авраменко B.C., Легопьков В.И. Автоматизированная система информационного обеспечения разработок. М.: Наука, 1980. - 207 с.

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

41. Цикритзис Д. Модели данных. М.: Финансы и статистика, 1985.- 343 с.

42. Четвериков В.Н., Ревупков Г.И., Самохвалов Э. Базы и банки данных. М.: Высшая школа, 1987. - 248 с.

43. Шаймардапов Р.Б. Моделирование и автоматизация проектирование структур баз данных. М.: Радио и связь, 1984. - 120 с.

44. Шомье Ж. Банки данных: Использование электронной вычислительной техники. М.: Энергоиздат, 1981. - 70 с.

45. Шуроков В.В. Обеспечение сохранности информации в системах обработки данных. М.: Финансы и статистика, 1985. - 224 с.

46. NetWare SQL. Getting started. 1992. 141 p.1. Статьи

47. Армстронг Р. Семь этапов оптимизации производительности хранилища данных// Открытые системы. 2002. - N 1.

48. Бабенко Л.П. Информационная поддержка повторного использования в программной инженерии на базе UML// Кибернетика и системный анализ. 2003. - N 1. - С. 74 - 82.

49. Базы данных: достижения и перспективы на пороге 21-го столетия// Под ред. А. Зильбершатца, М. Стоунбрейкера, Д. Ульмана. -СУБД. 1996. N 3.

50. Горшкова Е.А., Новиков Б.А. Использование диаграмм состояний и переходов для моделирования гипертекста// Программирование.- 2004. N 1. - С. 64 - 70.

51. Грипев М.Н., Кузнецов С.Д. UQL: Язык запросов к интегрированным данным в терминах UML// Программирование. 2002. - N 4. -С. 9 - 19.

52. Дектярев С.А., Воронин Г.Ф. Применение сплайнов в термодинамике растворов// Математические проблемы фазовых равновесий.- Новосибирск: Наука. 1983. - С. 53 - 83.

53. Дробышев Ю.П., Одиянко Б.Н. Анализ изображения по его модели// Развитие и использование аэрокосмических методов изучения природных явлений и ресурсов. Новосибирск: ИГГ СО АН СССР.- 1979. С. 83 - 95.

54. Дробышев Ю.П., Зыкин C.B. Идентификация областей ограниченных n-арными поверхностями// Системы и методы анализа данных.- Новосибирск: ВЦ СО АН СССР. 1984. - С. 53 - 58.

55. Дробышев Ю.П., Зыкип C.B. Программное и математическое обеспечение базы данных фазовых диаграмм (БДФД)// Примеиение математических методов для описания и изучения физико-химическихравновесий. T. 1. Новосибирск: ИНХ СО АН СССР, 1985. - С. 177 -181.

56. Дробышев Ю.П., Зыкин C.B. Алгоритмы и программное обеспечение информационной системы по фазовым диаграммам// Автометрия. 1986. - N 1. - С. 47- 53.

57. Ершов А.П., Ильин В.П. Пакеты программ, как методология решения прикладных задач// Пакеты прикладных программ. М.: Наука. - 1982. С. 4 -18.

58. Зыкин C.B. Алгоритм определения предельной точки области в заданном направлении// Структуры и анализ данных. Новосибирск: ВЦ СО АН СССР. - 1985. - С. 91 - 100.

59. Зыкин C.B. Смешанная аппроксимация// Математические модели представления информации и задачи обработки данных. Новосибирск: ВЦ СО АН СССР. - 1986. - С. 72 - 79.

60. Зыкип C.B. Программное обеспечение для автоматизированных информационно вычислительных систем// Информатика и вычислительная техника в учебном процессе и управлении. - Омск: ОмГПИ. - 1988. - С. 177 - 178.

61. Зыкин C.B. Вопросы подготовки специалистов в области информатики// Новые информационные технологии в учебном процессе и управлении. Омск: ОмГПИ. - 1989. - С. 131 - 132.

62. Зыкип C.B. и др. Комплекс программ для анализа радиосетей передачи информации// Системы моделирования в радиотехнике и связи. Новосибирск: ВЦ СО АН СССР. - 1989. - С. 77 - 78.

63. Зыкип C.B. Алгоритмы аппроксимации табличных функциональных зависимостей// Системы моделирования в радиотехнике и связи. Новосибирск: ВЦ СО АН СССР. - 1989. - С. 107 - 113.

64. Зыкин C.B. Оценка мощности списка для отображения типа "частичное соединение"// Кибернетика и системный анализ. 1993. - N 6. - С. 142 - 152.

65. Зыкин C.B. Формирование пользовательского представления реляционной базы данных с помощью отображений// Программирование. 1999. - N 3. - С. 70 - 80.

66. Зыкин C.B. Разработка прикладных программ для баз данных// Математические структуры и моделирование. Вып. 7. Омск: Ом-ГУ. - 2001. - С. 139 - 156.

67. Зыкип C.B. Соответствие состояний реализации исходной и целевой моделей данных// Международная конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова. Новосибирск. - 2001. - С. 237 - 241.

68. Зыкип C.B. Построение отображения реляционной базы данных в списковую модель данных// Управляющие системы и машины. -2001. N 3. - С. 42 - 63.

69. Зыкип C.B., Кукин A.B. Построение математической модели учебного процесса для долгосрочного планирования// Математические структуры и моделирование. Вып. 10. Омск: ОмГУ. - 2002. - С. 77 -86.

70. Зыкин C.B. Инструментальные средства разработки приложений для работы с базами данных// Материалы V Международной научно-технической конференции "Динамика систем, механизмов и машин". Омск: ОмГТУ, 2004. Кп. 1. - С. 376 - 380.

71. Зыкин C.B. Создание приложений на основе межмодельпых преобразований данных// Материалы III Международного технологического конгресса "Военная техника, вооружение и технологии двойного применения". Омск: ОмГУ, 2005. - Ч. II. - С. 66 - 69.

72. Косяков В.И., Зыкип С.В., Малахов Д.В. Согласование данных по фазовым равновесиям. 1. Основы метода// Журнал Физической Химии. 1989, - Т. LXIII. - N 2. - С. 329 - 333.

73. Косяков В.И., Зыкин С.В., Малахов Д.В. Согласование данных по фазовым равновесиям. 2. Участок ликвидуса системы: RbNOs — Sr(NOzh// Журнал Физической Химии. 1989. - Т. LXIII. - N 3. -С. 525 - 527.

74. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД// Программирование. 1989. - N 6. - С. 46 - 59.

75. Кузнецов С.Д. Выработка оптимальных планов выполнения запросов в реляционных СУБД// Программирование. 1990. - N 2. - С. 28 - 43.

76. Новак Л.Г., Кузнецов С.Д. Канонические формы схем XML// Программирование. 2003. - N 5. - С. 65 - 80.

77. Осипов М.А., Мачульский О.Л., Калиниченко Л.А. Отображение модели данных XML в объектную модель языка СИНТЕЗ// Программирование. 2000. - N 4. - С. 23 - 30.

78. Педерсеп Т.Б., Йенсен К.С. Технология многомерных баз данных// Открытые системы. 2002. - N 1.

79. Упольников С.А. Алгоритмы конструирования моделей трехмерных объектов на ЭВМ// Машинная графика и ее приложения. -Новосибирск: ВЦ СО АН СССР. 1983. - С. 115 - 135.

80. Ходоровский В.В. К вопросу нормализации отношений в реляционных базах данных// Программирование. 2002. - N 1. - С. 55 -71.

81. Хорошевский В.Г. Организация стохастически оптимального функционирования большемасштабных распределенных вычислительных систем// Информационные технологии и вычислительные системы. 2001. - N 2/3. - С. 30 - 39.

82. Хорошевский В.Г., Мамойленко С.Н. Стратегии стохастически оптимального функционирования распределенных вычислительных систем// Автометрия. 2003. - Т. 39. - N 2. - С. 81 - 91.

83. Чаудхури С., Дайал У., Гаити В. Технология баз данных в системах поддержки принятия решений// Открытые системы. 2002. - N 1.

84. Bell DA, Ling DHO, McClean S. Pragmatic Estimation of Join Sizes and Attribute Correlations// IEEE Int. Conf. of Data Engineering. -1989. P. 76 - 84.

85. Chao T-J, Egyhazy С J. Estimating Temporary File Sizes in Distributed Relational Database Systems// IEEE Int. Conf. of Data Engineering. -1986. P. 4 - 12.

86. Christodoulakis S. Estimating Blok Transfer and Join Sizes// Proc. of Annual Meeting ACM SIGMOD, San Jose. - 1985.

87. Codd E.F. , Codd S.B. , Salley C.T. Providing OLAP to User-Analist: An IT Mandate. E.F. Codd S Associates. - 1993.

88. Epstein R., Stonebraker M. Analysis of Distributed Database Processing Strategies// Proc. of 6th Int. Conf. on VLDB, Montreal.- 1980. P. 92 - 101.

89. Pedersen T.B., Jensen C.S., Dyreson C.E. A Foundation for Capturing and Querying Complex Multidimensional Data// Information Systems.- V. 26. N. 5. - 2001 .

90. Selinger PG, Astrahan MM, Chamberlin DD, Lorie RA, Price R. Access Path Selection in a Relation Database Management System// Proc. of ACM-SIGMOD int. Conf. on Management of Data. 1979. - P. 23 - 34.

91. Vassiliadis P., Sellis Т.К. A Survey of Logical Models for OLAP Databases// ACM SIGMOD Record. V. 28. N. 4. - 1999.

92. Zykin S.V. Relation queries execution under the estimators control. -M.: ADBIS'95. 1995. - V. 2. - P. 52 - 55.

93. Zykin S.V. Generation of User View for a Relational Database by Mappings// Programming and Computer Software. V. 25. - N. 3. -1999. - P. 173 - 183.1. Тезисы докладов

94. Зыкин С.В. Отображение реляционной модели данных в списковую модель типа "частичное соединение"// Информационные системы в науке 95. - М.: Фазис, 1995. - С. 49 - 50.

95. Зыкин С.В. Технологии информационного обеспечения процесса принятия решений// Проблемы оптимизации и ее приложения. -Омск: Ом ГУ, 1997. С. 76 - 78.

96. Зыкин С.В. Метод межмодельных отображений в базах данных. Новосибирск: ИНПРИМ-2000. Ч. 2. - С. 163.1. Диссертации

97. Бабапов A.M. Теория семантически значимых отображений и ее применение для проектирования реляционных баз данных: Дис. на соискание ученой степени кандидата технических наук. Томск, 2004. - 179 с.

98. Дектярев С.А. Развитие методов расчета термодинамических свойств двойных сплавов с использованием диаграмм состояний: Дис. на соискание ученой степени кандидата химических наук. -М., 1980. 139 с.1. Препринты

99. Алексеев A.C. и др. Функциональное математическое обеспечение обработки изображений: Препринт/ ВЦ СО АН СССР. N 410. Новосибирск, 1983. - 24 с.

100. Зыкин C.B. Архив СМ: Препринт/ ВЦ СО АН СССР. N 848. -Новосибирск. 1989. - 13 с.

101. Зыкин C.B. Отображение типа "Соединение"реляциопиой модели данных в списковую модель физического уровня описания данных: Препринт/ ВЦ СО АН СССР. N 902. Новосибирск 1990. - 28 с.

102. Зыкин C.B. Базы данных. Методические указания для выполнения индивидуальных заданий. ОмГУ, 1999. - 23 с.

103. Ковалков A.B. Об одном алгоритме построения сплайнов с дискретными ограничениями типа неравенств: Препринт/ ВЦ СО АН СССР. N 385. Новосибирск, 1983. - 14 с.

104. Одинцов Б.Е. Средства отображения семантических моделей в среде баз данных^ РКП 88-84503. Киев: ИК, 1988. - 18 с.1. Электронные издания

105. Зыкип C.B. Межмодельные отображения в базах данных. Омск: ОмГУ, 2000, http://newasp.omskreg.ru/db/index.html