close

Вход

Забыли?

вход по аккаунту

?

bd000100846

код для вставкиСкачать
На правах рукописи
З Ы К И Н Сергей Владимирович
г
Разработка и исследование моделей данных
и средств организации взаимодействия пользователей
с информационными ресурсами
05.13.17 - Теоретические основы информатики
Автореферат
диссертации на соискание ученой степени
доктора технических наук
Омск-2005
Работа выполнена в Омском Филиале Института Математики
СО Р А Н им. академика С.Л. Соболева
Официальные оппоненты:
Доктор технических наук Кузнецов С. Д.
Доктор технических на)тс Родионов А.С.
Доктор физико-математических наук Соколинский Л.Б.
Ведущая организация:
Институт вычисл1ггельной математики и математической геофизики СО
РАН
Защита диссертации состоится 6 декабря 2005 г. в 14.00 часов на
заседании Совета Д 219.005.02 при Государственном образовательном
учреждении высшего профессионального образования «Сибирский госу­
дарственный университет телекоммуникаций и информатики» Министер­
ства Российской Федерации по связи и информации по адресу: 630102,
г. Новосибирск, ул. Кирова, 86.
С диссертацией можно ознакомиться в библиотеке Сибирского государ­
ственного университета телекоммуникаций и информатики (СибГУТИ)
по адресу: 630102, г. Новосибирск, ул. Кирова, 86.
Отзывы на автореферат просьба высылать по адресу: 630102, г. Но­
восибирск, ул. Кирова, 86, заместителю декана ИВТ И.И. Резван.
Автореферат разослан 26 октября 2005 г.
Ученый секретарь
Диссертационного Совета, к.т.н.
(/L4/-
И.И. Резван
IrfoT
^У^^'^З/
Общая характеристика работы
Актуальность проблематики построения специализированных моделей
данных обусловлена возрастающим количеством информационных ресур­
сов, имеютцих различное описание и представление, что создает множество
технических и организационных проблем при использовании этих ресурсов.
Построение отображения этих ресурсов (канонические модели: реляцион­
ные, сетевые, иерархические, объектные, объектно-реляционные, функци­
ональные и т.д.) в специализированные модели (табличные, гиперкубиче­
ские, темпоральные, семантическая трансформация, таблицы соединений,
графические и т.д.) позволяет избавить пользователя от многих рутинных
операций по обработке информации: сбору, структуризации, компоновке, перекодафовке и т.д., если пользователю приходится это делать многократно
с информацией, имеющий стандартизованный набор моделей ее описания
и представления. При наличии специализированной модели имеется воз­
можность создания инструментария, с использованием которого приложе­
ния формируются без привлечения средств программирования.
Целью данной работы является разработка моделей представления ин­
формационных ресурсов для автоматизации процесса формирования поль­
зовательских приложений.
Вкладом автора является разработка и исследование ряда специали­
зированных моделей данных и метода межмодельных отображений для ав­
томатизации построения пользовательских приложений. По предложенно­
му методу построены универсальная модель таблицы соединений и модель
семантической трансформации, которые позволяют получить реализацию
программного обеспечения для работы пользователей с фазовьши диаграм­
мами, электронными таблицавли и т.д.. Разработана математическая модель
фазовой диаграммы и алгоритмы расчета характеристик с ее использовани­
ем. Для всех представленных моделей проведено достаточно подробное их
исследование. Автором разработано программное обеспечение базы данных
по фазовым диаграммам, использованное в ИНХ СО РАН. Компонент этого
программного обеспечения - система управления файлами, была использо­
вана в других программных разработках: комплекс программ для анализа
радиосетей передачи информации, архивная система. На основе полученных
результатов по межмодельным преобразованиям был разработан инстру­
ментарий для автоматической генерации пользовательских приложений с
представлением данных в виде электронных таблиц.
Н а у ч н у ю новизну работы образую! Л|е1уч;|1и1шныи icm^ основньге ре­
зультаты:
вНБДИОТСКА.
{
Cf
'■Г^М
о»
1. Разработан новый подход к построению интерфейса между пользова­
тельским приложением и централизованными информационными ресурсаг
ми. Для этого предлагается разработка специализированных моделей дан­
ных, которые,с одной стороны^позволяют формировать схему пользователь­
ского приложения, с другой сторонь!, обеспечивают фунгащонально полный
интерфейс с информационными ресурсами. Эти модели занимают второй
промежуточный уровень между приложениями и информационными ресур­
сами. Основой для реалЕсзации данного подхода является методы межмо­
дельных коммутативньк преобразований.
2. Построена новая модель данных "Таблица соединений"и получено
обобщение модели "Семантическая трансформация". На основе исследовзг
ния этих моделей разработаны алгоритмы, явл5нощиеся основой инструмен­
тария для автоматической генерации широкого класса пользовательских
приложений. Разработана методика получения оценки мощности реализа­
ции таблицы соединений при условии, что исходная схема содержит произ­
вольное количество отношений и произвольное количество обшдх атрибу­
тов. Разработан алгоритм эвристической оптимизации запросов к данным,
представленным в виде совместно хранимых отношений, в том числе, и в
виде таблицы соединений.
3. Разработана модель пользовательского представления графической
информации специального вида, предназначенная для работы с фазовы­
ми диаграммами физико-химических соединений. На основе исследования
свойств этой модели разработаны алгоритмы формирования представления
графической информации и расчета основных характеристик. Рассмотрен­
ный математический аппарат позволяет использовать в алгоритмах погреш­
ности измерений совместно с аппроксимацией поверхностей.
Методы исследования. При выполнении работы использовались мето­
ды коммутативных межмодельных преобразований, теория проектирования
реляционных схем. При построении пользовательской модели фазовой диа­
граммы и разработке соответствующих алгоритмов применена прикладная
топология, используемая в машинной графике, и теория аппроксимации.
Практическая значимость. Разработанные специализированные мо­
дели данных: "таблица соединений", "семантическая трансформация"и мо­
дель описания графической информации могут быть использованы раз­
работчиками инструментальньа средств формирования пользовательских
приложений. Кроме того, предложенная методика формирования специзг
лизированных моделей на основе межмодельного отображения может быть
использована при создании инструментария для работы с разнотипньпли
информационны!** ресурсами. Мебель описания фазовых диаграмм и алго.
.
,
.
« J
.„
^
.
4
ритмы работы с ней были использованы в ИНХ СО РАН для исследования
моделей физико-химических соединений и формирования информационной
базы по фазовым диаграммам. Технология построения таблиц соединения и
"семантическая трансформация "использовались при формировании поль­
зовательских приложений для организации учебного процесса в ВУЗе на
примере СибАДИ (г. Омск). Результаты работы используются в лекцион­
ных курсах для студентов математического факультета Омского госунивер­
ситета.
Апробация. Результаты работы доложены на конференцияк и семина­
рах, среди которых:
Пятая всесоюзная школа: "Применение математических методов для
описания и изучения физико-химических равновесий". - Новосибирск: СО
А Н СССР, 1985.
Пятая научно-практическая конференция "Информатика и вычисли­
тельная техника в учебном процессе и управлении". - Омск: ОмГПИ, 1988.
Шестая научно-практическая конференция "Новые информационные
технологии в учебном процессе и управлении". - Омск: ОмГПИ, 1989.
Доклад на семинаре Института прикладной информатики под председэг
тельством Ю.П. Дробышева и с участием сотрудников С К Т В при И К НАН
Украины. - Киев, 1993.
Конференция "Информационные системы в науке - 95". - Москва, 1995.
Международная конференция "ADBIS'95". - Москва, 1995.
Международная конференция "Проблемы оптимизации и ее приложе­
ния". - Омск, 1997.
Доклад на семинаре Института систем информатики им. А.П. Ершова
СО РАН под председательством Поттосина И.В. - Новосибирск, 1998.
Международная конференция ИНПРИМ-2000. - Новосибирск, 2000
Международная конференция, посвященная 90-летию со дня рождения
Алексея Андреевича Ляпунова. - Новосибирск, 2001.
Доклад на научно-исследовательском семинаре "Автоматизация про­
граммирования "Московского государственного университета (факультет
ВМиК) под руководством Шура-Бура М.Р, Москва, 2003.
Публикации. По теме диссертационной работы опубликовано 26 работ,
из них: статьи в центральных журналах - 7, статьи в сборниках СО РАН - 5,
статьи в местных изданиях - 2, доклады на международных конференциях
- 6, тезисы доклада на конференциях - 4, препринты - 2.
Структура и объем работы. Диссертационная работа состоит из пре­
дисловия, введения, восьми глав основного содержания, заключения, списка
литературы и описания четырех приложений. Объем работы - 245 страниц,
библиография - 105 наименований.
Содержание работы
В предисловии рассматриваются актуальность, цель, научная новизна,
практическая значимость, апробация работы, а также перечислены приме­
ненные методы исследования и опубликованные работы.
Во введении рассматривается проблема технологии создания приложе­
ний для работы с информационньши ресурсами. Общепризнанным решени­
ем этой проблемы является требование наличия в инструментальных средах
компонентов, позволяющих генерировать приложения с минимальньш при­
влечением средств программирования.
Во введении приведен обзор работ, связанных с исследованием моделей
данных, ориентированньк на пользовательских представлений данных с
использованием преобразований и интеграции неоднородных информаци­
онных ресурсов. Для слабоструктурированных моделей данных анализи­
руются работы, в которых в качестве исходного представления использу­
ется формат X M L , для сильноструктурированных моделей - реляционное
представление. Анализируются модели поликубического и гиперкубическо­
го представления данных.
Для решения проблемы формирования пользовательского представления
данных предлагается использование аппарата коммутативных межмодель­
ных отображений.
В общем случае модель информационной системы {модель данных) мо­
жет быть представлена в терминах алгебраических систем:
n=<M,D,F,P>,
где М - логическая модель (схема) данных; D - совокупность допустимых
состоянии базы данных; F - набор операции для модели М; Р - совокуп­
ность предикатов, ограничиваюпщх допустимые состояния Z?; Л/ и £> в со­
вокупности являются носителем системы.
Модель П будем считать моделью корпоративной информационной систе­
мы (исходной), а П' =< M',D',F',P'
> - специализированной (целевой).
Для достижения поставленных целей необходимо построение отображения
П => П'.
В основу построения отображения положен метод преобразования дан­
ных, основанный на свойстве коммутативности.
Поскольку пользовательское приложение может иметь доступ только к
части данных, то построение отображения осложняется отсутствием биективности между состояниями исходной и целевой модели. Поэтому в ка­
честве основы построения межмодельного отображения выбран алгоритм
построения представления целевой модели по текущему представлению це­
левой модели. Этот алгоритм позволяет решить проблему установления со­
ответствия между состояниями исходной и целевой моделями и является
основой для обоснования корректности последующих построений. Предло­
женная в данной работе методика построения отображения без особых из­
менений может быть использована для случаев, когда целевой моделью яв­
ляются: а) модель описания физического представления данных; б) пользо­
вательская модель (внешняя схема) данных; в) модель описания интегри­
рованных информационных ресурсов, являющихся исходными для пользо­
вательской модели данных.
В первой главе предложен метод построения отображения между мо­
делями данных, в основу которого положен алгоритм построения пред­
ставления целевой модели загрузки представления целевой модели данных.
Предварительно обсуждаются проблемы установления соответствия между
состояниями моделей данных и вводится понятие обобщенных состояний,
между которыми устанавливается биективность.
Предложенный метод построения отображения сосаюит из пяти эталов:
1. Формирование схемы целевой модели с использованием язьпса описаг
ния данных (ЯОД) для фиксации состава и структуры логического уровня
целевой модели. Во многом эта проблема решается за счет возможностей
выбранной инструментальной системы, в рамках которой предполагается
работа с целевой моделью.
2. Разработка алгоритма построения представления целевой модели А1д,
который должен стать основой для построения и обоснования корректно­
сти последующих шагов. Следствием этого являются основные требования
к алгоритму: 1) наименьшая топологическая сложность алгоритма (в смыс­
ле цикломатической меры Мак-Кейба), 2) однозначность интерпретации его
предложений (операторов). Требование оптимальности для основного алго­
ритма должно быть отвергнуто, если оно противоречит предыдущим двум
требованиям. При необходимости может быть разработана оптимальная
версия алгоритма А1д алгоритма загрузки и доказана его эквивалентность
основному. В завершении для алгоритма А1д строится область опредатения.
3. Определение образов ограничений целостности. Для исходной модели
данных Q, может быть задана совокупность ограничений: функциональные
и многозначные зависимости, зависимости соединений, ссылочная целост-
ность и т.д. Все они в совокупности определяют допустимые состояния дан­
ных и переходы между ними для исходной модели С1. Поскольку алгоритм
А1д определяет образы состояний модели П для модели Q', то соответству­
ющие образы для ограничений на допустимые состояния и переходы также
определяются этим алгоритмом.
4. Формирование образов операций преобразования целевой модели. В
процессе работы с представлением модели СИ пользователь формирует по­
следовательность команд /', которая переводит модель О,' из состояния
d[i € D[ в состояние rfj„ е D'^ Исполняющая среда (программное обес­
печение) должна сформировать соответствующую совокупность команд /,
которая необходима для перевода модели П из состояния rf,( £ Dj в состоя­
ние djm € Dj. Указанные преобразования состояний должны удовлетворять
условию коммутативности:
<к —• djm
J
(hi
Alg
,t
» dii
f
* djm
rf
> £fj^,
Другими словами, в состояние d'^^ можно перейти двумя различными спосо­
бами, но результат должен быть один и тот же. Сформулировалное условие
показывает, что основой для формирования / является алгоритм А1д. При
этом, задача формирования / является обратной относительно А1д.
5. Формирование образов операций преобразования исходной модели. Мо­
дификация состояния модели П может быть выполнена из другого приложе­
ния, что потребует изменения состояния модели Q'. Для этого должна быть
сформирована последовательность команд /', которая вьшолнит необходи­
мые преобразования в представлении модели П'. При этом задача форми­
рования /' является прямой относительно А1д и условие коммутативности
примет следующий вид:
F ; « ^ ) = Alg{U{d,,)).
Во второй главе вводится в рассмотрение новая модель данных - табли­
ца соединений (б'-таблица). Схематически б'-таблица может быть представ­
лена в следующем виде. Рассмотрим отображения типа "соединение": Ry,
i?2, ■■■iRk —^ {S,l), где S - схема отношения, определенная на всем множе­
стве атрибутов Ai, А2, —,Ап- Рассмотрим принцип формирования кортежей
t € S, где S - реализация схемы отношения S.
Определение. Соединение Ri ii R2 ^ ... i^ R^ будем называть существу­
ющим, если для совокупности схем Л,, i = l,fc существует хотя бы одна
упорядоченная последовательность Ri, Rz, ..., Rk такая, что
j
»=i
Рассмотрим существующие соединения для всевозможных сочетаний из
^ по m реализаций г^, т = 1,к. Для каждого кортежа и каждого су­
ществующего соединения сформируем кортеж t по следующим правилам:
t[Aj] = u[Aj], если атрибут Aj принадлежит соединению, и t[Aj] = етр
в противном случае. Каждому кортежу поставим в соответствие битовый
вектор l{t) = {li{t),l2{t),...,lk{t)), гдеlj{t) — 1, если реализацияг_, схемы R-j
участвует в текущем соединении, и /^(i) = О в противном случае.
Определение. Кортеж t & s является менее определенным или равным
кортежу i' е 5, когда для любого атрибута Л, выполнено: если *[Л,] ^ f [Л,],
то t[A^ = етпр и lj{t) < 10), j = 1, А;. В этом случае будем писать: t -^tf.
PaccMorpeinioe определение частичного порядка означает то, что кортеж
f содержит в себе все менее определенные либо равные кортежи. Следова­
тельно, для завершения построения s необходимо из 5-таблицы удалить все
менее определенные кортежи.
Для 5-таблицы рассмотрен и доказан ряд полезных свойств, в том числе
единстветшость представления в виде 5-таблицы. Самым важным является
следующее свойство.
Определение. Проекция 7!:R^^,RJ^,...,RJ^{S) есть совокухшость кортежей
и[Х], определенных на множестве атрибутов X = U™^ Rj^, где для каж­
дого и[Х] существует кортеж t £ s такой, что и[Х\ — t[X] и l.,.{t) = 1,
г = l,m.
Свойство. Для любого существующего соединения отношений Дд, Rj^,
...,Rjm> где т= 1,к, выполнено:
^Л "^ Rh ^ - «^ Щт = ''■д^„Д„,..,Л,;„(«)То есть, операция естественного соединения множества реляционных отно­
шений эквивалентна одной операции проекции на 5-таблице.
На основании предложенной технологии построения специализирован­
ных моделей рассмотрены все этапы построения 5-таблицы. В предположе­
нии полной определенности реляционной модели П приводится формальная
схема модели П'. Разработан алгоритм первоначальной загрузки 5-таблицы,
который удовлетворяет требованиям простоты и однозначной интерпрета^
ции операторов. Рассмотрены образы ограничений целостности для функ­
циональных, многозначных зависимостей и ссылочной целостности данных.
Для 5-таблицы введены традиционные табличные операции: дополнение,
удаление и модификация кортежей. Однако, непосредственные изменения
в 5-тсиблице невозможны, поскольку это может разрушить ее структуру и
ограничения целостности данных. Решением данной проблемы является вы­
деление подкортежей, соответствуюцщх отношениям исходной модели, и их
"перезагрузка"в существуюшую 5-таблицу в соответствии с алгоритмами
последнего этапа построения отображения.
Для случая, когда данные в исходной модели могут быть изменены дру­
гим приложением, разработаны образы операций преобразования реляци­
онной базы данных для 5-таблйцы. В качестве операций преобразования
исходной модели данных использован классический набор преобразования
реляционных таблиц: добавление кортежа и[НЦ к реализации г^ схемы Я , ,
удаление кортежа и[Ег] и модификация кортежа «[/?,] —> и'[Л,].
Для каждой операции преобразования исходной модели данных разра­
ботан соответствуюищй алгоритм преобразования 5-таблицы. Для каждо­
го алгоритма приведено доказательство его корректности, то есть эквива­
лентности нового представления 5-таблицы представлению, которое будет
сформировано алгоритмом первоначальной загрузки из нового состо5шия
исходной (реляционной) модели данных. Все алгоритмы преобразования Sтаблицы имеют квазилинейное количество итераций относительно количе­
ства кортежей в 5-таблице. Причем, линейная составлягош;ая в оценке мо­
жет быть заменена логарифмической, если использовать вспомогательные
индексные файлы (просмотр 5-таблицы заменяется поиском необходимых
кортежей по индексному файлу).
Особо необходимо отметить свойство, которое характеризует операцию
естественного соединения для произвольных схем баз данных, в том числе
и циклических.
Определение. Пусть для и[Щ и кортежа t £ s сформировано множесгво
Tj - совокупность беспрепятственно склеиваемых отношений Нщ. а для кор­
тежа f €. S, t ^ t", сформировано множество Т^,. Допустим, что существует
схема Rm, такая, что:
1) Дт € Ту,
2)НтППф1Ц;
3)t[R^nT^]y^iflR,nnn];
4) не существует кортежа t" € s, для которого определено Т} и tf'[Rm nTi,] =
tf\Rmr\%]. В этом случае схему Rm будем считать критической, поскольку
ее наличие в Tj препятствует образованию кортежа для соединения, состо­
ящего из Яг и совокупности схем из Tj \ Rm и Гц.
Лемма. Схема Rj^ тогда и только тогда может быть критической, когда
10
существует последовательность R,, Д^,, R-,^,..., Rj„, R,,n> 2,\ < q <п, где
соседние элементы последовательности имеют непустое пересечение друг с
другом, а не соседние элементы последовательности Д^,, й^, ..., Л^„ имеют
пустое пересечение друг с другом.
Рассмотренная технология представления, описания и обработки данных
в виде 5-таблицы предназначена не только для создания модели описания
информационных ресурсов при разработке активных пользовательских при­
ложений, юаимодействующих с корпоративной базой данных , но и для мо­
дели данных физического уровня, что рассматривается в следующих гла­
вах. Рассмотренная в работе 5-таблица является основой для формирова­
ния пользовательских представлений, аналогичных электронным таблицам,
поликубическим представлениям и т.п. Проведенные исследования свойств
5-таблицы являются полезными для других представлений, например - по­
лусоединений для циклических схем реляционной базы данных, поскольку
их общей основой является операция соединения.
В третьей главе рассматривается методика получения оценки мощности
реализации s. Поскольку в основу S-таблицы положена операция естествен­
ного соединения, то анализируются известные методики для оценки мощ­
ности результата этой операции. Задача оценивания мощности s возникает
на этапе проектирования физической организации БД, когда, как прави­
ло, отсутствует информация о распределении значений атрибутов. Поэто?лу
при получении среднего значения мощности 5 использовано предположе­
ние о равномерности - равной вероятности появления любого возможного
значения атрибута. Кроме того, при обобщении оценки на произвольное ко­
личество общих атрибутов и произвольное количество отношений потребу­
ются предположения о статистической независимости значений атрибутов
в каждом отношении и независимости значений общих атрибутов в различ­
ных отношениях.
Предварительно рассмотрена оценка мощности s для двух отношений Ri
и Дг- Пусть |i?i| = Л^1, |i?2l — Щ- мощности отношений, X = i?i П i?2 7^ 0
- совокупность общих атрибутов для RiVL R2,ki- мощность X в оселме Ri,
^2 - мощность X ь R2 , к - мощность X в соединении R\ м ^2- В общем
случае выполнены соотношения: к < ki, к < hi^ ki < Ni т к^ < N^. Даг
лее предположим, что X содержит один атрибут, либо один обобщенный
атрибут, то есть пока не будем рассматривать мощности отдельных атрибу­
тов в X. JIRK построения оценки \S\ - мопщости 5-таблицы воспользуемся
схемой генерации реализаций схем Ri и Дг, при этом, к общих значений
общего атрибута X должны присутствовать в каждой реализации Й! и Дг,
ki значений общего атрибута должны присутствовать в каждой реализаг
и
щи Ri, i = 1,2. Это предположение позволит формально (количественно)
сохранить функциональные зависимости, если таковые есть.
Результирующее соотношение для оценки:
i5i='^-('.-*)^-(*=-*)f.
где первое слагаемое - мощность соединения, а второе и третье - мощность
остатков соединения.
С использованием схемы генерации реализаций Л,, основанной на соче­
таниях с повторениями, была построена функция распределения случайной
величины - мощности s.
Рассмотрена оценка мопщости s для двух отношений - Ri w Яг, когда
множество X = RiD R2 состоит из т атрибутов, т > 2. Это становится
актуальным, если нет возможности получить экспертную оценку величин
fci, ^2 иfcдля X, как для обобщенного атрибута. Кроме того, при обобщении
на множество отношений потребуется разбиение обобщенных атрибутов на
подмножества. Пусть X = {Ai, Ai, ..., Am), тогда
m
m
J-1
J=l
K--Y[4A,),i = l,2, k = Y[k{A,),
где kt{Aj) - моищость атрибута Aj в схеме i?,, k{Aj) - мощность атрибута
AJ в соединении i?i x Яг, то есть количество обшдх значений атрибута Aj в
реализациях схем RX'KRI- Для формального (количественного) сохранения
функциональных и многозначньк зависимостей должно быть выполнено:
K{Aj) < N„ k{Aj) < kt{Aj), г = 1,2, J = l,m. Оценка мощности s в этом
случае равна:
Величина Z'^ зависит от распределения выбранной комбинации значений по
реализациям Я , , и для различных схем генерации реализаций величина 2,'
будет различной. После выбора наиболее адекватной схемы генерации было
получено соотношение:
Zi
Ti
ik + Ni-2)\{h-iy.
__
kj-l
(k + Ni - iy.{ki - 2)!
ki + N,-l-
Далее рассматривается обобщение оценки |5| на множество отношений
Ri, Яз, ..., Я„- Использование метода последовательного присоединения
схем отношений не гарантирует свойства симметричности оценки мощности
12
соединения, то есть изменение последовательности присоединения отноше­
ний в общем случае приводит к другому значению оценки, хотя результат
операции соединения не зависит от последовательности присоединения от­
ношений В работе предлагается новый подход, основой которого является
декомпозиция.
Из способа формирования 5-таблицы следует, что оценка может быть
представлена в следующем виде:
|^1 = ЕЕ'5('и,/)>
m=l 1{т)
где 1{т) - совокупность номеров отношений, являющаяся сочетанием без по­
вторений по го элементов из множества / = {1,2,..., п}, (Э(/(тп), /) - оценка
мощности остатка от соединения i?ji м i?jj м ... м Д^^, j, е 1{т), или
среднее количество кортежей соединения, не являющихся подчиненными
другим кортежам в 5.
Используя предыдущие результаты,имеем:
Q{l{m),I) = \S(l(m}\x Д
Д^И),
где
рпг ,,_кт){г)-к{ХМгп)))
ft{^l{m)j
—
7
,
ТГ.
1
Щт){г)
г
к(ХМт)))г'{Хг{1{т)))
ГТ
Щ„-){г)
7fi
Ti
при XI(/(TO)) ^ 0, И P^{l{m)) = 1 при Xi{l{m)) = 0, кцуп){г) - мощность ат­
рибутов X,(Z(m)) в соединении S{l{m)), к{Хг{1{т))) - мохцность атрибутов
Xi{l{m)) в соединении S{l{m) Ui),
Z'iXilim)))
k{l{m)Ui)-l
Ti
k,il{m)Ui)
+
N,-l'
Из предположения о статистической независимости атрибутов следует:
*i(m)(i)=
к{Хг{т))=
П
J]
МЛ. К»")).
к(А„1(т)иг).
Л;еХ,(г(т))
Отметим, что раздельное суммирование по остаткам позволяет оценить
реальный объем внешней памяти, необходимый для хранения данных, так
как отказ от хранения пустых значений атрибутов приводит к переменной
13
длине записей в таблице s. Подставив перед каждой оценкой остатка длину
его записи, получим оценку объема внешней памяти.
В четвертой главе рассматривается проблема оптимизации запросов к
базам данных, в которых используются специализированные модели для
представления данных на физическом уровне. Существуют два основных
направления оптимизации запросов: а) логическая оптимизация запросов;
б) физическая оптимизация выполнения запросов. Предложенный в дис­
сертационной работе подход ориентирован на физическую оптимизацию, с
использованием оценочных функций, и специализированные способы пред­
ставления данных, прежде всего в виде 5-таблицы.
Рассматривается подмножество запросов, которые могут быть формали­
зованы в виде "универсального"реляционного запроса:
Tcx{(rc{Ri к Ri»
... к Rk)),
где 7г, (т, м - операции проекции, селекции и соединения; X - совокупность
атрибутов в результирующей таблице; С - логическое вьфажение над атри­
бутами.
Предположим, что среда хранения и обработки данных - распределенная
база данных на нескольких серверах, связанных между собой достаточно
скоростными каналами. Далее рассматривается схема базисного алгоритма
итерирования (БАИ) для последовательности отношений: Ri,R2,...-,Rk; Д
- область просмотра отношения R, в соответствии с ограничениями С и
текущими ограничениями из отношений Rj, j < i.
Обозначим: (^(1,2,...,fc;I) - стоимость итерирования последовательности
отношений Ri, R2,..., Rk на сервере с номером I, ф{1,2,..., к; I) - стоимость
формирования результата итерирования на сервере /. Обпще затраты ите­
рирования определяются суммой: <р+'ф, где if - включает в себя количество
операций ввода и затраты на передачу исходных данных на сервер I, ф количество операций вывода на севере /.
Далее рассматривается алгоритм квазиоптимального плана реализации
запроса. Для выбора последовательности совместного итерирования отно­
шений используется соотношение:
Viijl О + ^^(i. j ; О -* rnin{{i,j; I)}.
Пара отношений R,, Rj может быть дополнена другими отношениями, воз­
можно предварительно итерированными, если это сокращает суммарную
оценку количества операций ввода, вывода и передачи данных.
Алгоритм имеет квадратичные затраты на поиск квазиоптимальной схе­
мы, что является вполне приемлемым при сравнении скорости работы про­
цессора и скорости передачи данных. Альтернативный подход, требуюпщй
14
максимального сокращения промежуточных результатов на начальных ите­
рациях: ii/<p -^ min, приводит к передаче значительных по объему проме­
жуточных результатов по сетям связи.
Вычисление функций ^-л-ф осуществляется на основе статистики, фор­
мируемой в процессе эксплуатации баз данных. Достаточно эффективной
методикой сбора статистики является интервальное оценивание распределе­
ния атрибутов: (iV,fc,d, {о,-, bi, ЛГ,}, г = 1,..., п), где N - мощность отношения
(количество кортежей) s R,k- мощность атрибута (количество различных
значений в Л, d - минимальная разница между различными значениями
атрибута, п - количество интервалов, а, - нижняя граница интервала, Ь, верхняя граница интервала, iV, - количество значений атрибута в интервале
(aj, Ьг). Величины fend могут быть получены экспертным способом. Коли­
чество различных значений на интервале может быть получено по формуле:
ki = kNi/N. Корректировка данного значения может быть выполнена с ис­
пользованием величины d:fc,< l-b (Ь, — ai)/d.
Для задачи последовательного итерирования под управлением оценоч­
ных функций и для реализации множественного доступа к данньш наиболее
целесообразно представление компоненты запроса С в виде дизьюнктивной
нормальной формы (ДНФ):
с^ = \/Л^'я
где C,j = <атри6ут><операция><атрибут>,
либо Сг^ = <атрибут><операция><константа>.
Далее рассматривается стема реализации ограничений С в процессе ите­
рирования отношений с использованием свойств ДНФ. Обозначим через
г результат итерирования запроса, Г2 = Ri х R2 х ■■■ х Rk, fi = ас(г2),
^0 = T^xin)Теорема. Б А И и схема реализации ограничений корректно формируют
результирующее отношение: г = го.
Пусть в запросе указано несколько Д,, принадлежащих одной 5-таблице,
либо одному кластеру (ORACLE), либо одно и то же отношение несколько
раз присутствует в запросе под различными расширенными именами. Такие
отношения назовем совместно хранимыми. При реализации запроса в этих
условиях чаще всего более целесообразно только один раз просматривать
5-таблицу, кластер, либо дублированное отношение.
При генерации схемы итерирования очередным выбранным отношением
является Rj, для которого не итерированными и совместно хранимыми яв­
ляются отношения iJjj, Яг,,..., Л^. Для каждого Л,,, s = 1,р, осуществляем
15
проверку. Бели для Rj и Л,, заданы условия естественного соединения и
они хранятся совместно в 5-тайлице либо в кластере, то Д,^ дополняется к
схеме итерирования без генерации нового результирующего отношения. В
противном случае, генерация нового результирующего отношения для Л,,
целесообразна, если: ip{in] I) < ip{ig, I), где Rm - результат итерирования Д,..
Далее вместо Я , , используется RmПредставление С в виде ДНФ позволяет естественным образом объ­
единить выполнение совокупности запросов. Одновременное появление
нескольких запросов чаще всего обусловлено подготовкой одного документа,
где одни и те же данные должны быть обработаны при различных ограни­
чениях. В этом случае запросы объединяются в группы, имеюпще общие
отношения. Сначала оптимизируется и вьптолняется каждая группа запро­
сов по общим отношениям при X = U^^i^i и С = V^LjCj, где п - количество
запросов в группе, X , и С,- - вьфажения г-го запроса. После исчерпания обцщх отношений группы распадаются на подгруппы и т.д.. Процесс распада
завершается формированием результирующих отношений, каждое из кото­
рых является ответом на отдельный запрос. Далее рассматривается подход
к совместной реализации запросов, которые поступают в произвольные мо­
менты времени.
В пятой главе рассматривается математическая модель графических
данных специального вида и алгоритхаг для работы с этой моделью.
Рассмотрена реализация модели для представления фазовых диаграмм в
координатах: давление Р, температура Г, состав, определяемый для тькомпонентной системы с помощью п — 1 значений мольных долей х,: г-го
компонента, г = 1, п — 1. Области на фазовой диаграмме соответствуют на­
хождению вещества (системы) в каком-либо состоянии (твердое, жидкое,
газообразное и т.д.), границы между областями соответствуют переходу из
одного состояния в другое. Такая информация перед использованием долж­
на пройти процедуры сбора, экспертизы и согласования.
Программное обеспечение информационной системы по фазовым диа­
граммам состоит из нескольких частей.
1. Пакет прикладных программ, предназначенный для решения конкрет­
ных прикладных задач в области химии, материаловедения и т.д.
2. Программы обработки запросов к информационной системе, которые
преобразуют значения зтхравляющих параметров, заданных в запросе в лег­
ко понятном пользователю виде, в значения переменных и массивов, кото­
рые используются в работе пакета прикладных программ.
3. Система управления файлами. Эта часть программного обеспечения
предназначена для записи, чтения, сортировки и поиска необходимой ин16
формации на внешних запоминающих устройствах Э В М . Кроме этого, име­
ется набор сервисных процедур, предназначенных для сжатия, анализа и
удаления данных.
4. Программы обработки исходного документа, подготовленного в специ­
альном виде. Эти программы осуществляют перевод исходного документа
во внутримашинное представление с выявлением ошибок, допущенных при
заполнении документа.
Математическое описание фазовых равновесий должно удовлетворять
следующим физико-химическим принципам.
1. Элемент размерности г, г = 1, тг, ограничен элементами размерности г—
1, г —2,..., О, принадлежащих исходному элементу и одновременно соседним
элементам той же размерности. Для реализации этого принципа введены
номера элементов и для каждого элемента размерности г — 1 указываются
номера элементов размерности г, которым он принадлежит.
2. Сзтцествует два класса точек: а) точки, через которые граница должна
пройти точно; б) точки, для которых граница проходит в пределах погреш­
ности измерения данных точек. Построение границы по этим классам точек
осуществляется при помощи алгоритма смешанной аппроксимации.
3. Элементы (границы) размерности п — 1, п — 2, ..., 1 не должны содер­
жать ложных экстремумов и точек перегиба.
4. Стыковка элементов (поверхностей), аппроксимируемых раздельно,
осуществляется таким образом, чтобы их продолжение принадлежало эле­
менту большей размерности, для которого исходные элементы не являются
граничными.
Известны различные способы графического представления реальных
объектов. Для математического описания фазовых диаграмм целесообраз­
но использование аппроксимаций функциональных зависимостей, описывав
юпщх разграничители фаз и гетерогенных областей.
Пусть .£" Евклидово пространство размерности п с ортогональным ба­
зисом ei, 62, ..., е„. Скалярное произведение и норма в Е^ определяются
обычным образом:
а,ЬеЕ^,
а = (oi,аг,...,Оп), b = (6i,62,...,b„),
п
(а,Ь) = J ^ a , b „ ||а|| = (о,а),
где Oj, 6„ г = 1, п - действительные числа.
В пространстве Е^ рассмотрим области Cl„i = 1,М,где N конечно.
17
Свойство.
N
Свойство.
п,пп^ = Гу, i,j = TJ^,i^j,
где Г,J замкнутая вполне ограниченная область в Е^ размерности п-1,п-2,
..., 1, 0. Существуют пары индексов (г, j ) , ддя которых Г у = 0, Причем, Г^
таковы, что любое замкнутое связное множество, имеющее непустое пере­
сечение с более чем одной областью П,, обязательно будет иметь непустое
пересечение с какой-либо границей Г^^-.
Каждая Г,; у^ 0 задается с некоторой погрешностью Ду, где Ду связная
п-мерная замкнутая вполне ограниченная область в £J" и Гу С Ду.
Пусть
г.. = и п;,
91
где границам Г'] соответствуют однозначные и непрерывные функции Af
91 = 1, k{i,j), которые в совокухгности задают границу Гу раздела областей
Q, и П_,. В силу однозначности A'j возможна следующая конкретизахщя ин­
дексов i и j. Пусть нижний первый индекс i является номером области,
соответствующей большим значениям х^ относительно Г^, а нижний вто­
рой индекс j - номер области, соответствующий меньшим значениям i j j .
Каждой границе FfJ поставим в соответствие тройку {i,j, qi).
Далее вводятся вспомогательные определения, рассматриваются и дока­
зываются свойства модели, полезные при обосновании корректности модели
и алгоритмов.
Теорема. Среди областей П „ г = 1,7V, имеется одна и только одна об­
ласть fijo неограниченная в Е^ при п > 2.
Теорема. Все области П,, г = 1, Л^, кроме неограниченной fijo, являются
компактными, а область П,о - локально компактна.
Рассмотрим для Ffj включающий прямоугольник /^'. задаваемый от­
резками [Qj,af], af < af, для г'-той компоненты ж, вектора х = (х^, хг, ...,
Хп) € Е". Причем, если х € Tf^, то х е /^'. Вообще говоря, существует це­
лое семейство 5 ( Р ' ' ) включающих прямоугольников для I^j. Однако будем
рассматривать минимальный из них i^', для которого разности af - QJ,
г = l7n, минимальны. В силу замкнутости и ограниченности Г^ все а] и
af существуют и конечны. Введем в рассмотрение ось L в Е", задаваемую
точкой х" £ Е" и вектором конечных приращений 0 = (/3i, 02, —, Рп) по
18
каждой координате
Ь = {хй Еп\х = 1° + а/3, a£R,
а> 0}.
Причем, существует г, для которого Д Ф 0. Ось L может иметь непустое
пересечение с i ^ ' , L{i,j,qi) = ЬП Р^>. Очевидно, что L{i,j,qi) замкну­
то и ограничено, если L(i,j,qi) ф 0. Рассмотрим множество M''(i,j,qi) с
HiJ^Qi), состоящее из А; точек х^^\ х^-^\ ..., х^*), где х'^^ и х ^ - конщ>1 от­
резка L{i,j, qi). Множество M''{i,j, qi) образует разбиение L{i,j, gi) на fc-1
интервалов одинаковой длины: Цх^'^ - х^*~^Ц\ — Цх^'''^^ — х^'^Ц, г = 2,fe- 1,
где к > 2 конечное целое число.
Определение. Область fij будем называть к - размытой, если вьшолнено:
L(t,j,^^0, Lfl(n,\U^y)^«''
тогда
где г и gi принимают все значения из существующих троек {i,j, 51) и (j, г, gi)
с фиксированным номером г области Г2,.
Полуютом оценку величины к.
Прямоугольник Р^^ в Е" задается парой векторов: а^ = {а\, al, ..., а^),
а^ = («1, с^,..., oj). Ясно, что максимальная длина отрезка L{i,j, qi) равна
\\а^ - аЧ|. Обозначим через ГДг^ границу области Аг; и Гу = т т Ц Г у Т^гЛТеорема.
* > ! ! 2 i : ^ + i.
Гу
Важное свойство к - размытых областей:
Теорема. Если область П, являетсяfc- размытой, то она является (fc+1)
- размытой.
Далее представлены алгоритмы для работы с графическими данными
для рассмотренной модели. Базисным является алгоритм, определяющий
номер области Q, по фиксированной точке х", где х" £ Q„ причем точка х"
может принадлежать нескольким областям, если она лежит на границе.
Основная идея алгоритма заключается в последовательной проверке
неравенств:
■^vj/
-^и-
Ajp"
Af^^-'-^'-Hx') < x t , < А^р ^-^(х%
19
где p' = 1, p" = 0; 5^ и g^' такие, что разность между правой и левой частями
неравенств минимальна.
На последнем шаге строится последовательность:
<п = ^V:M') - 4. -' <г = ^tiM') - <■
Если в этой последовательности нет нулевьк элементов, то из нее выби­
раются наибольшие отрицательные элементы а^^,^ может быть несколько,
и наименьшие положительные а^'^ . При этом возможны следующие ситуа­
ции: 1) все элементы последовательности положительны или отрицательны,
а также, если в последовательности нет ни одного элемента, то решением
алгоритма будет г" номер неограниченной (внешней) области; 2) в последо­
вательности найдены элементы a?'j^ и а^'^. Среди них выбираем такие, что
Is = jp, и этот номер будет решением алгоритма. Если в последовательно­
сти имеются нулевые элементы, то все индексы iaj при них дадут решение
алгоритма, т.е. номера областей, для которых точка х° является граничной.
Определим оператор проекции Wi^ вдоль координаты х/^, который явля­
ется матрицей п х п, на главной диагонали которой стоят единицы, кроме
строки li- Все остальные элементы матрицы нулевые.
Лемма. Элемент af присутствует в последовательности тогда и только
тогда, когда Wi^x° € Пц.
Определим множество S = {х е E^\Wi^x - Wijx"}.
Лемма. Множество S П Ff^' может иметь не более одной точки, причем,
если / е 5 П r g , то a;J^ = А%[о:!).
Теорема. Индекс г будет решением алгоритма тогда и только тогда,
когда х" е fi,.
Аналго вычислительных затрат алгоритма показал, что верхняя граница
оценки сложности алгоритма линейно зависит от количества всех элемен­
тов, описывающих фазовую диаграмму.
Следуюпщй алгоритм определяет границы области в заданном направле­
нии. Он позволяет определить предельную точку области П,- в направлении
оси L, где L задается фиксированной точкой х" € fi, и вектором относи­
тельных приращений /?. Рассмотрим схему вычисления интервала /у.
с^ — х"
а* = тах[0, lim * , ' ] , 5 = 1,п, t = 1,2 ;
/,_+о р, + п,
{
al = al и al = а, для Д > О,
a j = о^ и а^^а]
для /?з < 0.
20
Получен набор интервалов {a],al), s = ТТп, для прямоугольника /^' и
фиксированной оси L. Интервал из набора будет считаться пустым, если
а] > а^. Причем й* е (aj, б^), если a j конечно, t = 1,2. Тогда
«=1
Используя определение для /3, нетрудно показать, что интервал /?' будет
конечным или пустьш и а > О для а £ Ц^.
Обозначим:
^ ( i , J , g i ) = {х € S " I rr = а ; Ч а;9, а 6 /«■},
Ui,j,q{) = L[\P!;.
Теорема. L{i,j,qi)
=X{i,j,qi).
Идея алгоритма заключается в том, что для каждой тройки (г, j, qi), соот­
ветствующей поверхности Af^{x), строится отрезок L{i,j,qi), который раз­
бивается наfc— 1 равных отрезков. Таким образом определяются к точек
(концы отрезков). Для этих точек определяется область, которой каждая из
них принадлежит. При этом свойство А; - размытости гарантирует обнару­
жение перехода в другую область Ц , если ось L{i,j, qi) имеет непустое пе­
ресечение областью fij без погрешности определения ее границ. После опре­
деления двух точек, ближайших к обнаруженной границе и находяпркся в
различных областях, точка пересечения с границей уточняется дихотоми­
ей, поскольку на данном интервале пересечение оси L{i,j,qi) с границей
единственно.
Теорема. Алгоритм в пределах погрешности находит граничную точку
X области 0,р такую, что норма \\х — х"]! минимальна.
Другой подход, основанный на "шагании"вдоль оси L, для фазовьк диа­
грамм имеет оценку количества итераций N2 < Ю^, тогда как предложен­
ный алгоритм имеет оценку N\ < 10^.
Далее рассматриваются алгоритмы построения функций Л ^ для аппрок­
симации границ Vfj. Для этих целей традиционно используются задачи ин­
терполяции и сглаживания функциональньк зависимостей, заданных в виде
таблиц экспериментальных точек. Однако, есть приложения, где неприем­
лемо раздельное использование чисто интерполяционных или чисто слаживаюпщх сплайн-функций. Например, обработка и представление фазовых
диаграмм. Каждая поверхность на фазовой диаграмме содержит два ти­
па точек: 1) внуаренние точки, измеренные с большой погрешностью, 2)
граничные точки, измеренные, как правило, с высокой точностью и, кроме
21
того, по физическому смыслу задачи несколько поверхностей должны пе­
ресечься в граничных точках. Ясно, что при сглаживании эти точки могут
исчезнуть с фазовой диаграммы. Применение интерполяции невозможно изза низкой точности измерения внутренних точек. Поэтому в данной работе
рассматривается постановка задачи смешанной аппроксимации: построение
аппрокси^шрующей конструкции, которая одно множество точек интерпо­
лирует, а другое - сглаживает.
Определим гильбертовы пространства: X ~ пространство аппроксими­
рующих функций; Zi - пространство интерполируемых данных, Z2 - про­
странство сглаживаемьк данных, Y - функциональное пространство, содер­
жание которого в последствии будет ясно. F — Y х Z2, где х - декартово
произведение.
Рассмотрим также линейные операторы: Ai : X —> Zi, А2 ■ X -^ Z2,
Т : X -^Y, L : X -^ FjT.e. L = [Т, Лг]. Лг и Лг - операторы следа функции
ю Х,Т - энергетический оператор, скалярное произведение и норма в X,
Y, Zi, Z2 определяются обычным образом. В F:
{f\f)F
= Cc{y\y'')Y + {zlzl)z,,
\\ffF^[fJ)F,
где /1 = [у\zll р = (7/2,4]; f\ f\ feF;y\y'eY;
Введем в рассмотрение множество Iz С X:
(1)
z^z\ e Z2; a > 0.
Iz = {xe X\AiX = zu zx € Z i } .
Задача смешанной аппроксимации запишется в следующем виде:
Фа(<7) = 1шпФ„(2;) = mina||Ti|l^ + ЦЛгх - ^гЩ,,
(2)
где а & Iz - искомое решение.
Используя (1),легко показать, что
Фа((т) = min|jLx-a||f,
xelz
где а = [9у, ^2] ^ F, 9у ~ нулевой элемент пространства Y.
Определим ядра операторов N{T) = {х е Х\Тх = ву}, N{Ai) = {ж €
X\Aix - вг,}, N{A2) -={хе Х\Л2Х = вг,}, N{L) = {х е X\Lx = вр}, где
^у> ^Zi, dz^, Sp нулевые элементы пространств У, Zi, Z2, F, соответственно,
причем ^f = [0у,9гг]Теорема. Если множества TN{Ai) и A2N{Ai) замкнуты в простран­
ствах У и ^2 соответственно, 7^ т^ 0 и N{T) П N{Ai) П ^{Лг) = {9х}, то
сплайн а, решение задачи (2), существует и единственен.
22
Пусть X конечномерное функциональное пространство с линейнонезависимым базисом ш\, Ш2, -.-, Шп на О.где П - замкнутая ограниченная
односвязная область в iT".
п
В этом случае z = ^ atW,(;t), t £ О.. Запишем задачу (2) в следующей
форме:
1=1
Aix = zi,
(3)
a\\Tx\^^\\A2X-Z2fz^-^rmrL.
(4)
После некоторых преобразований задача (3) - (4) запишется в следующем
виде:
Фа(а) = а(Та, а) + (Ма, а) - lij^, о)Л+11^2111, + (Л, ЛГа - Л ) -+ min,
где Л п - мерный вектор множителей Лагранжа.
Условия минимума этого функционала запишутся в виде блочной систе­
мы линейных алгебраических уравнений:
а Т Ч Д^
А^
Ti
О
)
(
:
)
=
(
!
)
■
где Ai = \к.
Дла реализации алгоритма в виде программного обеспечения было опре­
делено:
к+1
А+1
т
4=1
»m=l
J=l
х=ад=5:...х:а..,...^п*г'"'-
(5)
Назовем Р*(<) полиномом специального вида, т.к. наивысшая степень его
равнаfem,однако, вдоль каждой координаты он имеет степень к.
В области П, в соответствии с операторами А\ и Лз, заданы два набора
точек ii = {tf,
3 = ТЖ},
h = {tf, j = ТЖ}.
Обозначим через щ полиномы обычного вида в Д"* степени I.
Теорема. Задача (2) однозначно разрешима на полиномах вида (5) то­
гда и только тогда, когда не существует полинома 7r,_i ^ О, для которого
вьшолнено равенство
;r,-i(t^')) = О, t^^&tiUt2.
Традиционной является постановка задачи кубической сплайн - интерпо­
ляции и кубической сплайн - аппроксимации со сглаживанием одномерных
функциональных зависимостей. Выбранные в этих алгоритмах "естественные"граничные условия: равенство нулю вторых производных на концах,
23
обуславливают его эффективность по времени счета и по используемой опе­
ративной памяти. Однако они существенно ограничивают класс объектов,
модель которых может быть построена с использованием алгоритма. В дан­
ной работе рассматривается алгоритм, для которого два дополнительных
условия задаются в виде равенства первых или вторых производных произ­
вольным значениям в произвольных точках области аппроксимации и даже
за ее пределами. При отсутствии информации о производных можно задать
более "слабые"ограничения: непрерывность третьей производной во втором
и предпоследнем узлах, что делает сплайн более гибким, чем при использо­
вании "естественных"граничных условий. Кроме того, два дополнительных
условия могут быть заданы в любой комбинации друг с другом.
В разработанном алгоритме использованы традиционные соотноше­
ния для аппроксимирующей конструкции. Заданы три вектора: х =
{х1,Х2,---,х^) - узлы аппроксимации, / = (Л,/г, --T/N) - значения функ­
ции в узлах, Д / = (Д/i, Д/г,..., Д/iv) погрешность измерения функции в
узлах. Для X е [xj~i,Xj] сплайн имеет вид
5p(s) = -sj-i-^j^ +
Ь—щ—+
и.
где j = 2,ЛГ, Sj значение второй производной сплайна в j - ом узле,
hj = Xj-Xj-i,yj = Sp{xj). Для заданной конструкции являются непрерывньши исходная функция и вторая производная. Условия стьжовки первой
производной в з^лах запишутся в виде системы линейных уравнений
g
^J I -; ^J+i + f^3 _ Уз+1 -УзVj - Уз-\
У]-I
6
3
/ij+i
hj
j = 2,N-l,
Дополнив полученные соотношения условиями непрерывности первой
производной в узлах, получим
Bs = Ay + R,
(6)
где В и А ~ квадратные трехдиагональные (за исключением первой и по­
следней строки) матрицы, R - вектор значений для дополнительных усло­
вий.
24
При решении задачи интерполяции имеем у = f, что позволяет постро­
ить Sp{x) из соотношения (б). При сглаживании у =^ f, поэтому использу­
ется следующ,ее:
Ijy
'Pip) = (1 -;') Е ^\f- +pJ{Sp"ix)fdxmm,
^
;//■
ччО
.
где 0 < p < 1.
После дифференцирования и подстановки соотношения s = B~^{Ay-\-R)
получим систему линейных уравнений в матричном виде:
ipD+{l-p){B-'AfLB-'A)y
= pfD + il-p)iB-'AfLB-'R,
=
(7)
где D - диагональная, а L - трехдиагональная матрицы.
На основании решения систем уравнений (7) и (6) можно определить
Sp{x). В пакете программ реализован режим повторного входа, позволя­
ющий быстрее получить решение для различных значений параметра р и
вектора А / .
В шестой главе рассматриваются проблемы построения моделей пользо­
вательского представления данных и построения отображения базы данньк
реляционного типа в пользовательское представление. На примере техноло­
гических потребностей информационной системы по фазовым диаграммам
подробно рассмотрены два вида преобразований (отображений).
Преобразование 1 (П1). Л* = aji - значения aji атрибута Aj становятся
атрибутами нового отношения. В работах Цаленко М.Ш. такое преобразо­
вание названо семантической трансформацией и рассмотрен образ функци­
ональной зависимости, левой частью которой являются ключевые атрибуты
отношения.
Преобразование 2 (П2). Я,* = Ri-Aj - отношение R, преобразуется во
множество отношений, в каждом из которых на атрибут А^ накладьгоается
ограничение типа равенство и этот атрибут удаляется из результирующих
отношений.
В соответствии с предложенным методом построения отображения для
П1 получены результаты по всем пяти шагам этого метода. Пусть R - ис­
ходное отношение базы данных; г, - кортеж в реализации г исходного отно­
шения, i = l,N; X - множество атрибутов из R, остающихся без изменения
в результирующем отношении; Y - множество атрибутов из R, значения
которых становятся именами атрибутов в результирующем отношении; Z
25
- множество атрибутов из R, области определения значений (домены) ко­
торых, дополненные пустым значением, распределяются между доменами
вновь введенных атрибутов. Причем атрибуты Y и Z отсутствуют в резуль­
тирующем отношении, X nY = ^, X П Z =^ $, Y П Z = 9, X UY и Z = R.
Правило построения схемы представления:
Sch{R) = {X, Y, Z} =Ф SchiR*) = {X, Dom{Y) х { Z } } ,
где Sch - схема описания отношения, R* - результирующее отношение, Вот
- множество допустимых значений атрибутов, х - декартово произведение,
D(m{Y) = DamiYi) х Dam{Y2) х ..., Fj € У, | Dam(Y) |= М, | {Z} \= L,
I - I - мощность множества.
Для построения представления г* разработан алгоритм первоначальной
загрузки. Максимальная сложность данного алгоритма по количеству итеN- 1
ращ1й: N{~
L).
Важным свойством рассмотренного алгоритма является: если какое-либо
значение r'[y.Zp^] Ф етпр, то г*[у.2р] ф етпр, р — \,L, если какое-либо
значение г*[у, 2pJ = етр, то r'ly.Zp] — етр, p = l,L.
Теорема. Для произвольной реализации г схемы R отношение г* суще­
ствует тогда и только тогда, когда г удовлетворяет функциональной зави­
симости XY -+ Z.
Далее рассматриваются правила преобразования зависимостей. Для них
необходимо показать, что ограничения введенные для г* являются доста­
точными для вьшолнения исходных ограничений для г.
Пусть V' С V - множества атрибутов, если выбран атрибут VQ € V, то
VQ ^ V', множество V' может быть пустым. Определим, что пустые значеьшя
не равны друг другу.
Теорема. Пусть г произвольная реализация схемы Я , удовлетворяющая
функциональной зависимости, в правой части которой атрибут Хо, тогда:
1. (FXX). Если X' -> Хо удовлетворяет г', то X' —»• XQ удовлетворяет г.
2. (FYX). Ек;ли для произвольных строк г*, Г2 € г* из условия г*[?Я-2р,] Ф
етр, Tl[y2.Zj^] ф етр, где у{ С у1; t/j С j/^; у{,2/2 ^ Оот{У') и j/i = г^,
следует гЦХо] = Г2[Хо], тогда У -> Хо удовлетворяет г.
3. (FZX). Если из условия rl[y{.Zp^] = r2[y2-Zp^], i = 1,1, Zp^ € Z' для
произвольных строк г1,Г2 € г*, следует г'[Хо] = Г2[Хо], тогда Z' -* XQ
удовлетворяет г.
Очевидно, что функциональные зависимости с более сложной левой ча­
стью (комбинации атрибутов из X , У и Z) и атрибутом Хо в правой
26
части, будут вьфажены в образе г* в виде конъюнкции ограничений 1 3. Пусть и' = X' UY' и Z', зависимость U' -* Хо будет иметь образ
< FXX > к< FYX > & < FZX >. Если какое-либо множество X, Y или
Z пусто, то соответствующее ограничение считается вьшолненным.
Далее рассмотрены аналогичные утверждения для других функциональ­
ных зависимотей и встроенных многозначных зависимостей.
Для операций преобразования представления должны быть выполнены
условия коммутативности. То есть совокупность кортежей г, должна быть
такой, что результат перехода в новое состояние г* должен совпадать с ре­
зультатом работы рассмотренного алгоритма с входным новым состоянием
г.
Семантика отношения г* такова, что в нем допустимы следующие опера­
ции:
1. Дополнение значений Zp в существующие строки.
2. Модификация значений Zp.
3. Удаление значений Zp.
4. Дополнение новой строки для ввода значений Zp.
Остальные преобразования г* либо являются следствием перечисленньк,
либо не имеют смысла.
Функции образов операций преобразования исходной модели для этого
преобразования вьшолняет алгоритм первоначальной загрузки.
Для построения отображения П2 достаточно выделить две группы атри­
бутов: X гУ,тдеК
= ХиУиХПУ
= 9. Пусть X = {Хг \ г =- T~N} множество атрибутов, на которые накладываются ограничения типа равенство^и они удаляются из результирующих отношений, и У = {У^ | j = 1, М]
- множество атрибутов, остающихся в новом отношении в качестве атрибу­
тов.
Правило формирования схемы образов Щ:
Sch{R) = {Х,У}
=» 8сН{Щ) = Sch{R.XlXlX},)
Sch{R) = { Х , У } =^ Зск(Щ) = Sch{R.XlXlXl)
Sch{R) = {X,Y}
= {¥},
= {¥},
=!> Sch{Rl) = Sch{R.X^.X^.XJi) = {Y},
где X' - выражение, эквивалентное Xj = xy, x,j € Dom{Xj). Количество
отношений - образов для данного преобразования равно L = Вотп{Х).
27
Формирование реализации образа достаточно использования операций
реляционной алгебры:
г,* = згг(<тя(г)),
N
где 7г - проекция, а - селекция, F; = Д ( Х , = х;,-)»=1
Далее рассмотрены образы в г* функциональных и встроенньос много­
значных зависимостей.
Кроме того, важными являются следующие свойства. Обозначим: V' =
V\X, где V - произвольное множество атрибутов, X - ранее определенное
множество атрибутов. Положим, что значение кортежа на пустом множе­
стве атрибутов есть константа: i[0] = const.
Теорема. Если функциональная зависимость W —* S удовлетворяет г,
то зависимость W —>■ S' удовлетворяет любому образу Г;*.
Теорема. Если встроенная многозначная зависимость W —>-+ S{T) удовлетюряет гяХ C,W,TO зависимость W —*-* S'(T') удовлетворяет любому
отношению г,'.
Замечание. В качестве г может быть использоващтаблица соединений з.
Причем, не все отношения исходной базы данных должны участвовать в его
формировании, а только необходимые для приложения.
Седьмая глава посвящена вопросам реализации программного обеспе­
чения информационной системы по фазовым диаграммам. В ней рассмотрень1 спецификации на систему, являющиеся результатом многолетней par
боты над прикладной областью. В главе представлены: общая структу­
ра программного обеспечения и этапы обработки информации; програм­
мы обработки исходной информации; система управления файлами; меха­
низм управления прикладньпии программами; внутримашшшое представле­
ние документа для фазовой диаграммы; специализированный язьж запро­
сов. Обсуждены вопросы независимости, модифицируемости, мобильности
и напрвление дальнейшего развития системы.
В восьмой главе обсуждаются основные принципы построения про­
граммного обеспечения, которое реализует технологию межмодельных пре­
образований данных и является инструментальной средой для автомати­
ческой генерации пользовательских проиложений с использованием элек­
тронных таблиц. В главе рассмотрены аспекты реализации инструментария,
важные не только для существуюпщх программ, но и для всех последующих
их версий с расширенным набором пользовательских моделей данных.
В заключении предложено развернутое изложетгае основных научных
результатов. Дальнейшее развитие данной тематики предполагается в сле28
дующих направлениях: 1) разработка новых моделей данных, 2) разработ­
ка новых алгоритмов межмодельных преобразований данных. Для созда­
ния гиперкубического представления данных таблица соединений явллется
слиппсом универсальной, для этого достаточно использовать частный слу­
чай: модель данных "Таблица ограниченных связями соединений", что поз­
волит избавиться от необходимости указания отношений, участвующих в со­
единении, при генерации приложения, и вычислять эти отношения по атри­
бутам (координатам гиперкуба) с использованием связей на схеме данных.
Кроме того, обобщение модели гиперкуба на случай списка значений и таб­
лицы значений в одной ячейке исходного гиперкуба позволит существенно
расширить область применения рассмотренной в работе технологии. Новые
алгоритмы преобразований становятся актуальными при массовой загрузке
значений из пользовательского представления данных в исходную базу дан­
ных (в работе рассмотрены образы операций при модификации единичных
значений). Все это потребует формулировки новых условий существования
представлений и тщательного исследования свойств моделей и алгоритмов.
В качестве приложений рассмотрены следующие разработки: 1) паке­
ты программ по смешанной аппроксимации; 2) сценарий работы системы
FazDiagr; 3) сценарий использования мастер-форм для генерации приложе­
ний; 4) архив-СМ.
Список публикаций по теме диссертации
[1] Дробьппев Ю.П., Зыкин С В . Идентификация областей ограниченных
п-арньаш поверхностями// Системы и методы анализа данных. - Ново­
сибирск: В Ц СО А Н СССР, 1984. - С. 53 - 58.
[2] Дробьппев Ю.П., Зыкин С В . Программное и математическое обеспече­
ние базы данных фазовых диаграмм (БДФД)// Применение математиче­
ских методов для описания и изучения физико-химических равновесий.
Т. 1. - Новосибирск: ИНХ СО А Н СССР, 1985. - С. 177 - 181.
[3] Дробьппев Ю.П., Зыкин С В . Алгоритмы и программное обеспечение miформационной системы по фазовым диаграммам// Автометрия. - 1986.
- N 1. - С. 47 - 53.
[4] Зыкин С В . Алгоритм определения предельной точки области в задан­
ном направлении// Стрзтстуры и анализ данных. - Новосибирск: В Ц СО
А Н СССР, 1985. - С. 91 - 100.
[5] Зыкин С В . Смешанная аппроксимация// Математические модели пред­
ставления информации и задачи обработки данных. - Новосибирск: ВЦ
СО АН СССР, 1986. - С 72 - 79.
[6] Зыкин С В . Программное обеспечение для автоматизированных инфорь
мационно - вычислительных систем// Информатика и вычислительная
техника в учебном процессе и управлении. - Омск: ОмГПИ, 1988. - С.
177 - 178.
[7] Зыкин С В . Вопросы подготовки специалистов в области информатики//
Новые информационные технологии в учебном процессе и управлении.
- Омск: ОмГПИ, 1989. - С 131 - 132.
[8] Зыкин С В . и др. Комплекс программ для анализа радиосетей переда­
чи информации// Системы моделирования в радиотехнике и связи. Новосибирск: В Ц СО АН СССР, 1989. - С. 77 - 78.
[9] Зыкин С В . Алгоритмы аппроксимации табличных функциональных за­
висимостей// Системы моделирования в радиотехнике и связи. - Ново­
сибирск: В Ц СО А Н СССР, 1989. - С. 107 - 113.
[10] Зыкин С В . Архив - СМ: Препринт/ ВЦ СО АН СССР. N 848. - Ново­
сибирск. 1989. -13 с.
[и] Зыкин С В . Отображение типа "Соединение"реляционной модели дан­
ных в списковую модель физического уровня описания данных: Пре­
принт/ В Ц СО АН СССР. N 902.. - Новосибирск. 1990. - 28 с.
[12] Зьшин С В . Оценка мощности списка для отображения типа "частичное
соединение"// Кибернетика и системный анализ, 1993. - N 6. - С. 142 152.
[13] Косяков B.PI., Зыкин С В . , Малахов Д.В. Согласование данных по фа­
зовым равновесиям. 1. Основы метода// Ж Ф Х . - 1989, - Т. LXIH. - N 2.
- С. 329 - 333.
[14] Косяков В.И., Зыкин С В . , Малахов Д.В. Согласование данных по фазо­
вым равновеси5ш. 2. Участок ликвидуса системы: RbNOz — Sr{NOz)i/1
Ж Ф Х . - 1989. - Т. L X n i . - N 3. - С. 525 - 527.
[15] Зыкин С В . Отображение реляционной модели данных в списковую мо­
дель типа "частичное соединение"// Информационные системы в науке
- 95. - М.: Фазис, 1995. - С 49 - 50.
30
[16] Зыкин С В . Технологии информационного обеспечения процесса приня­
тия решений// Проблемы оптимизации и ее приложения. - Омск: ОмГУ,
1997. - С. 76 - 78.
[17] Зыкин С В . Формирование пользовательского представления реляцион­
ной базы данных с помощью отображений// Программирование. -1999.
- N 3. - С. 70 - 80.
[18] Зыкин С В . Метод межмодельных отображений в базах данных. Ново­
сибирск: ИНПРИМ-2000. - Ч . 2. - С 163.
[19] Зыкин С В . Разработка прикладных программ для баз данных// Ма­
тематические структуры и моделирование. Вьга. 7. - Омск: ОмГУ, 2001.
- С 139 - 156.
[20] Зьшин С В . Соответствие состояний реализащи исходной и целевой мо­
делей данных// Международная конференция, посвященная 90-летшо со
дня рождения Алексея Андреевича Ляпунова. - Новосибирск, 2001. - С
237 - 241.
[21] Зыкин С В . Построение отображения реляциокной базы данных в спис­
ковую модель данных// УСиМ. - 2001. - N 3. - С 42 - 63.
[22] Зыкин С В . , Кукин А.В. Построение математической модели учебного
процесса для долгосрочного планирования// Математические структу­
ры и моделирование. Вып. 10. - Омск: ОмГУ, 2002. - С. 77 - 86.
[23] Зьпаш С В . Инструментальные средства разработки приложений для
работы с базами данных// Материалы V Международной научнотехнической конференции "Динамика систем, механизмов и мапшн". Омск: ОмГТУ, 2004. Кн. 1. - С 376 - 380.
[24] Зыкин С В . Создание приложений на основе межмодельньк преобразо­
ваний данных// Материалы П1 Международного технологического кон­
гресса "Военная техника, вооружение и технологии двойного примене­
ния". - Омск: ОмГУ, 2005. - Ч . П. - С. 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.
31
З Ы К И Н Сергей Владимирович
Разработка и исследование моделей данных
и средств организации взаимодействия пользователей
с информационными ресурсами
05.13.17 — Теоретические основы информатики
Автореферат
диссертации на соискание ученой степени
доктора технических наук
Подписано в печать 03.10.2005. Формат60х841/16.
Печ.л. 2,0. УЧ.-ИЗД.Л. 2,0. Тираж 100 эю. Заказ 451.
Издательство
ОмГУ
644077, Омск-77, пр. Мира, 55-а
1121045
РНБ Русский фонд
2006-4
19705
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 559 Кб
Теги
bd000100846
1/--страниц
Пожаловаться на содержимое документа