стр. 1
(всего 2)

СОДЕРЖАНИЕ

>>

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


УДК 004.82




Варламов Олег Олегович




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




05.13.01 - Системный анализ, управление и обработка информации
(в оборонной и гражданской технике)




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




Москва - 2003
2

Работа выполнена в Московской академии рынка труда и информационных
технологий (МАРТИТ).



Научный консультант: академик РАН, доктор технических наук, профессор Каляев
Анатолий Васильевич.




Официальные оппоненты:
член-корреспондент РАН, доктор технических наук, профессор Хорошевский
Виктор Гаврилович,
доктор технических наук, профессор Афанасьев Валерий Николаевич,
доктор технических наук, профессор Богатырев Владимир Ильич.



Ведущая организация - Институт проблем информатики РАН.



Защита состоится "16" октября 2003 г. в 14.00 часов на заседании диссертационного
Совета Д 850.001.01 при Московской академии рынка труда и информационных
технологий (МАРТИТ) по адресу: 121351, г. Москва, ул. Молодогвардейская, д. 46,
корп. 1, телефон (095) 149-86-38.


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



Автореферат разослан "5" июня 2003 г.



Ученый секретарь
диссертационного совета, профессор Чересов Ю.И.

? О.О. Варламов, 2003
3

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

Актуальность темы. Одной из основных проблем, решаемых при создании
автоматизированных систем обработки информации (АСОИ), в целом, и программно-
аппаратных комплексов (ПАК) оперативной диагностики (ОД) в частности, является
обеспечение, в условиях их непрерывного функционирования, адаптации
программно-аппаратных средств для эффективного и оперативного решения сложных
задач. Анализ актуальных научных проблем создания АСОИ показал, что
необходимо, прежде всего, решить следующие две взаимосвязанные проблемы.
Первая проблема - это создание интерактивных самоорганизующихся баз данных
(БД) и знаний, на основе которых возможно создание программного обеспечения
АСОИ. Отметим, что, так как фактически в "базах знаний" хранятся правила,
процедуры и отношения объектов, то вместо термина "знания" будем применять
термин "правила". Подчеркнем, что особую актуальность решению первой проблемы
придает то, что в последнее время теория баз данных оказывает определяющее
воздействие на многие смежные области. Например, БД используются при создании
перспективных ЭВМ, что определяет место и роль второй научной проблемы:
создание теоретических основ адаптивного синтеза информационно-вычислительных
конфигураций (ИВК) АСОИ. Основное направление решения данной проблемы - это
создание систем адаптивного синтеза (САС) самоорганизующихся конфигураций
АСОИ. Две эти проблемы решают на разных уровнях: на уровне программного
обеспечения (первая) и на уровне аппаратных средств (вторая), фактически одну и ту
же проблему - создание самоорганизующихся АСОИ (ПАК ОД).
Системный анализ задач, которые необходимо решить как для создания
самоорганизующихся баз данных и правил (СБДП), так и для построения САС ИВК,
показал их взаимозависимость, поэтому обе эти проблемы в совокупности образуют
одну крупную научную проблему. Следовательно, разработка теоретических основ
создания СБДП и САС ИВК для построения самоорганизующихся программно-
аппаратных комплексов оперативной диагностики (СПАКОД) является актуальной
крупной научной проблемой. Решение этой новой проблемы имеет важное
хозяйственное значение для целого ряда областей (медицины, экономики,
юриспруденции, анализа чрезвычайных ситуаций, метеорологии и др.). Отдельные
наиболее сложные задачи этих областей могут быть отнесены к классу ресурсоемких
научно-практических задач оперативной диагностики. Как правило, это уникальные
задачи, решение которых носит эмпирический характер и требует научно-
4

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


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

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


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


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

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


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


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

3. Адаптивность синтеза ИВК обусловлена уникальностью каждой диагностической
задачи, необходимостью учета ранее разработанных конфигураций, быстротой
создания и старения программных и аппаратных средств. Исходные данные для
синтеза ИВК и решения задач, могут быть в различных форматах представления
данных и знаний, но их необходимо хранить в едином структурированном
унифицированном пространстве представления данных и правил.
4. Для обеспечения эволюционного развития комплексов оперативной диагностики
предложено на программном уровне ввести СБДП, а на аппаратном - САС ИВК.
5. Для создания САС ИВК предложены принципы их построения и применения.
6. Для создания СБДП проведено обобщение СПД моделей данных путем
применения пятиуровневых одномерных таблиц представления данных и
предложены основы построения многомерного информационного динамического
пространства унифицированного представления данных и правил.
7. Для обеспечения эволюционности логической обработки информации создан
метод обработки данных на основе применения интерактивной
самоорганизующейся логической сети правил, управляемой потоком данных.
8. Для повышения быстродействия обработки информации разработаны: метод
"графового" поиска маршрута логического вывода; квадратичной сложности
методы поиска минимального разреза (максимального потока) двухполюсных и
многополюсных сетей; линейной сложности матричный метод поиска маршрута
логического вывода на сети правил.
9. Для повышения параллельности и оперативности обработки информации
разработан метод распараллеливания потокового множественного доступа к
общей базе данных в условиях недопущения взаимного искажения данных.
10. Для повышения быстродействия единично-инкрементного суммирования чисел
разработан и запатентован новый метод (способ) суммирования чисел.


Практическая ценность работы определяется тем, что:
1) основы создания СБДП и принципы построения и применения САС ИВК
обеспечивают возможность создания самоорганизующихся программно-
аппаратных комплексов оперативной диагностики;
2) основы создания СБДП позволяют адаптивно и своевременно наращивать объем
хранимой информации и обрабатывать ее с применением интерактивной
эволюционной логической сети правил, управляемой потоком данных, что
повышает интеллектуальные способности АСОИ;
8

3) интерактивная самоорганизующаяся логическая сеть, управляемая потоком
данных, объединяет обработку известных данных на основе известных правил и
осуществляет обучение, изменение системы правил, что обеспечивает
эволюционное развитие всей компьютерной системы в целом;
4) методы поиска маршрута логического вывода и минимального разреза позволяют
снизить вычислительную сложность поиска маршрута логического вывода до
квадратичной;
5) методы поиска минимального разреза позволяют снизить сложность поиска
минимального разреза (максимального потока) двухполюсных и многополюсных
сетей с кубической до квадратичной;
6) метод алгоритмической минимизации количества процедур и устройств для
единично-инкрементного суммирования чисел позволяет перейти от степенной к
линейной зависимости количества операций сложения от разрядности чисел;
7) матричный метод поиска маршрута логического вывода позволяет снизить
сложность поиска маршрута логического вывода до линейной;
8) интерактивная самоорганизующаяся логическая сеть позволяет распараллелить
логическую обработку потока данных;
9) метод распараллеливания потокового множественного доступа к общей БД
реализует максимальное быстродействие (без накопления времени задержки)
обработки данных;
10) предложенные основы и методы в совокупности позволяют повысить
эффективность разработки, эксплуатации и модернизации компьютерных систем
(АСОИ) за счет оптимизации синтеза конфигураций по критерию отношения
реальной производительности к стоимости;
11) предложенные основы и методы в совокупности позволят уменьшить время
решения сложных задач за счет общего повышения производительности
адаптивных ЭВМ относительно традиционных, в среднем за период
эксплуатации, на половину разности производительности следующих и
современных поколений ЭВМ (не менее чем в 50 раз);
12) предложенные научные основы, принципы и рекомендации совместно с
применением ЭВМ с программируемой архитектурой, разрабатываемых под
руководством академика РАН Каляева А.В., в совокупности позволят повысить
реальную производительность адаптивных самоорганизующихся ЭВМ вдвое, т.е.
относительно пиковой мощности обычных ЭВМ с 10-30 % до 50-70 %;
9

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


Основные результаты диссертационной работы получены автором единолично
(без соавторов). Эти результаты реализованы, внедрены и используются в
Государственном научно-исследовательском испытательном институте проблем
технической защиты информации Гостехкомиссии России, Таганрогском
радиотехническом университете (ТРТУ), Академии налоговой полиции ФСНП
России, ОАО "НИИ СуперЭВМ", ОАО "НИИ ВК им. М. А. Карцева" и др. Получен
патент на изобретение.


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


Публикации. Основные научные результаты диссертации опубликованы в
35 научных работах, из них: 2 монографии, 20 статей, 1 патент, 12 докладов.


Структура и объем диссертации. Диссертация состоит из введения, семи
разделов, заключения и списка литературы из 352 наименований. Она содержит
307 страниц текста, 16 таблиц, 43 рисунка.
10

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


Во введении обосновывается актуальность крупной научной проблемы,
проанализирован научный уровень создания АСОИ, сформулированы цель и задачи
исследования, дан краткий обзор содержания диссертации, перечислены полученные
новые научные результаты и приведены сведения о практической ценности работы.


В первом разделе рассмотрена проблема создания самоорганизующихся БД и
правил для синтеза комплексов оперативной диагностики, сформулирована проблема
адаптивного синтеза информационно-вычислительных конфигураций. Понятие
"самоорганизующиеся комплексы оперативной диагностики" не является строго
определенным термином, но их БД должны быть эволюционными. Действительно
эволюционной может быть только БД с изменяемой структурой данных.
Традиционные структурированные модели данных БД предназначены для
автоматизации обработки данных в таких предметных областях, структура описания
данных которых фиксирована. При изменении концептуальной модели предметной
области проектирование структуры БД необходимо фактически делать заново.
Существуют неструктурированные модели данных, но для них характерны другие
недостатки, связанные со сложностью реализации высокоскоростной обработки
данных. Кроме того, наличие структуры представления данных позволяет проводить
систематизацию данных, ассоциативную обработку, а многомерность значительно
ускоряет обработку любых массивов. К структурированным моделям данных
относятся реляционные, сетевые, иерархические модели, модель "сущность-связь", а
к неструктурированным - гипертекст, символьная модель и др. Отметим, что если
принято различать два типа данных: структурированные и неструктурированные, то
самоорганизующиеся базы данных можно отнести к новому типу представления
данных с изменяемой структурой. Такая структура обладает возможностью
эволюционного наращивания, а при необходимости и кардинального изменения, даже
в условиях непрерывности функционирования системы.
Проблема адаптивного синтеза информационно-вычислительных
конфигураций. В настоящее время синтез конфигураций новых поколений ЭВМ
приобретает особую актуальность, что обусловлено постоянно возрастающими
потребностями решения различных диагностических задач. Кроме того, актуальность
создания именно адаптивных ЭВМ обусловлена необходимостью постоянной
модернизации АСОИ в условиях непрерывности их функционирования. Современные
11

ЭВМ могут содержать тысячи вычислительных блоков, одновременная замена
которых требует больших финансовых и временных затрат. Создание адаптивных
ЭВМ позволит изменить процесс проектирования многопроцессорных
вычислительных систем, а также обеспечит возможность наращивания и проведения
поэтапной модернизации модулей ЭВМ в условиях эксплуатации. В настоящее время,
в области создания суперЭВМ возникло противоречие, которое состоит в том, что для
любой задачи наиболее эффективными являются специализированные устройства, но
их производство оказалось в новых условиях экономически нецелесообразным.
Поэтому, теперь ЭВМ собирают из множества унифицированных модулей,
производимых различными фирмами. Более того, можно самостоятельно собрать
суперЭВМ и одна из них уже вошла в 2001 году в "TOP-500".
Актуальность проблемы адаптивного синтеза ИВК обусловлена изменением
принципов создания ЭВМ; уникальностью каждой задачи; необходимостью обучения
и учета, ранее разработанных
вариантов конфигураций;
быстротой создания, развития и
старения программных и
аппаратных средств.
Современное развитие
Рис. 1.
науки и техники позволяет из
унифицированных комплектующих на
ИНФОРМАЦИЯ

необходимый для решения задачи период
МОДЕЛИ
времени собрать неоднородную ЭВМ,
КЛАССОВ МОДЕЛИ ИВК
САС
которая после решения этой задачи
ЗАДАЧ
ИВК
может быть адаптирована для решения
других задач (рис. 1). Методы синтеза
АДАПТАЦИЯ
отдельных ЭВМ известны, но проблема
адаптивного синтеза конфигураций ЭВМ
ОЦЕНКА
ЗАДАЧИ КОНФИГУРАЦИЯ ЭВМ
не решена. Для проектирования
ИВК

адаптивных ЭВМ необходимо создать
систему адаптивного синтеза
ЗАКАЗЧИК
РЕШЕНИЕ
информационно-вычислительных
Рис. 2.
конфигураций (САС ИВК) (рис. 2). В
САС ИВК должна оперативно накапливаться информация о решаемых задачах и
существующих компонентах ИВК. САС ИВК должна быть многопроцессорной
12

самоорганизующейся неоднородной АСОИ, в которой можно в условиях
эксплуатации добавлять, изменять и удалять любые модули, средства и данные.
Отметим, что особый интерес, с точки зрения адаптации ЭВМ под различные
классы задач, представляют разрабатываемые под руководством академика РАН
Каляева А.В. вычислительные системы и модули с программируемой под структуру
решаемой задачи архитектурой. При реализации адаптивного синтеза на ЭВМ с
программируемой архитектурой представляется возможным создать адаптивную
АСОИ. В такой адаптивной АСОИ создается БД известных структур задач и описание
(каталог) архитектур вычислительных модулей. При поступлении на вход системы
некоторой задачи производится ее анализ, определяется ее структура и из каталога
архитектур вычислительных модулей выбирается наиболее адекватный модуль, затем
производят перепрограммирование архитектуры вычислительных модулей и
непосредственное решение требуемой задачи. Если для поступившей задачи в
каталоге архитектур существует оптимальный вариант архитектуры вычислительных
модулей, то это реализуется в автоматическом режиме. Если в каталоге нет
подходящей архитектуры, то формируется сигнал вызова администратора и система
переходит в автоматизированный режим, когда человек принимает решение о выборе
"нужной" архитектуры или формирует новую архитектуру и добавляет ее в каталог.
Универсальные ЭВМ решают реальные задачи с эффективностью 10-15 % от
пиковой производительности, в то время как специализированные ЭВМ позволяют
добиться 80-90 % эффективности. Внедрение адаптивного синтеза на
вычислительных системах с программируемой архитектурой позволит создать
достаточно универсальную самоорганизующуюся АСОИ, которая будет решать
широкий класс задач с эффективностью не менее 60-70 % от пиковой
производительности ЭВМ. После внедрения и реализации самоорганизующихся
АСОИ закупать можно будет только самые современные комплектующие, добавляя
их в новые эволюционные ИВК. Таким образом, в настоящее время изменились как
задачи, так и возможности по созданию ЭВМ, что выявило новые научные проблемы
и определило необходимость нетрадиционных подходов к их решению. Сегодня есть
все предпосылки для решения проблемы адаптивного синтеза ИВК и построения
самоорганизующихся компьютерных систем.


Во втором разделе исследованы принципы построения однородных
вычислительных систем, проведен системный анализ основных путей создания
эволюционных неоднородных компьютерных систем (ЭНКС) и предложены
13

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

В третьем разделе проведено формализованное описание основных структур
представления данных - СПД - традиционных моделей данных, их анализ, сравнение
и обобщение в виде нового формализма пятиуровневой одномерной таблицы
представления данных (ОТПД). На едином языке теории множеств описаны и
проанализированы СПД: реляционных; сетевых; иерархических; бинарных; объектно-
ориентированных; символьных моделей данных; модели "сущность-связь" и
семантических сетей. Под моделью данных понимают совокупность трех
составляющих: СПД, ограничения целостности, операции над данными. Для любой
модели данных основную роль играют именно СПД. Существует два простейших
способа представления данных: таблицы и графы, поэтому целесообразно выделить
графо-табличные СПД, которые и называются в дальнейшем: традиционными. В
связи с ограниченным объемом автореферата, рассмотрим здесь только реляционные
и сетевые СПД, а также СПД модели данных "сущность-связь".
Реляционная модель данных - это множество нормализованных отношений
(таблиц), к которым применимы операции реляционной алгебры. Все данные
рассматриваются как хранимые в таблицах, в которых каждая строка имеет один и
тот же формат. Выделяют следующие реляционные СПД: имена отношений, имена
атрибутов, значения. Пусть A - множество имен отношений:
(1)
A={a1,a2,...,ai,...,aI},
{ }
?a i ? A ?B i = b i1 , b i 2 ,..., b iji ,..., b iJ i , (2)
{ }
?b iji ? B i ?Ciji = c iji 1 , c iji 2 ,..., c iji k ij ,..., c iji K ij , (3)
i i

где i = 1, I ; ji = 1, J i ; k ijj = 1, K iji , Bi - это множество имен атрибутов отношения ai,

C iji - это множество значений атрибута b iji отношения ai. Подчеркнем, что от

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

данных типов записей, реализации типов записей, типы наборов-связей, реализации
наборов-связей.
Замечание. В связи с ограниченностью количества символов в латинском
алфавите и для подчеркивания аналогичных взаимосвязей элементов СПД различных
моделей данных будем использовать одинаковые символы для описания исследуемых
структур представления данных, но с различной их интерпретацией. С учетом этого
замечания, пусть A - множество имен типов записей:
(4)
A={a1,a2,...,ai,...,aI},
{ }
?a i ? A ?B i = b i1 , b i 2 ,..., b iji ,..., b iJ i , (5)
{ }
?b iji ? B i ?C iji = c iji 1 , c iji 2 ,..., c ijik ij ,..., c ijiK ij , (6)
i i

где i = 1, I ; ji = 1, J i ; k ij j = 1, K iji , Bi - это множество имен элементов данных

типа записи ai и Ciji - это множество значений элемента данных b iji типа записи ai.
Пусть Z - множество имен типов наборов-связей:
(7)
Z={z1,z2,...,zl,...,zL},
{ }
?z l ? Z ?Yl = y l1 , y l 2 ,..., y lm l ,..., y lM l , (8)
?X l = { x l1 , x l 2 ,..., x ln ,..., x lN },
?z l ? Z (9)
l l

где l = 1, L ; m l = 1, M l ; n l = 1, N l и Yl - это множество реализаций записей-
владельцев набора-связи типа zl и Xl - это множество реализаций записей-членов
набора-связи типа zl. При этом,
{ }
?z l ? Z ? < y 1ml , x lnl > y 1ml ? Yl , x lnl ? X l . (10)
Модель Чена ("сущность-связь", ER-модель)- это семантическая реляционная
модель данных, в основе которой лежит деление реального мира на отдельные
различимые сущности, находящиеся в определенных связях друг с другом. Эта
модель может рассматриваться как обобщение иерархических и сетевых моделей.
Выделим следующие СПД ER-модели: классы сущностей, множества сущностей,
классы (размерности) связей, множества связей, роли сущностей в связях, множество
атрибутов, множество значений. Пусть A - множество имен классов сущностей:
(11)
A={a1,a2,...,ai,...,aI},
{ }
?a i ? A ?B i = b i1 , b i 2 ,..., b iji ,..., b iJ i , (12)

где i = 1, I ; ji = 1, J i и Bi - это множество имен сущностей класса ai. Далее,
?С={с1,с2,...,сk,...,cK}, (13)
16

где k = 1, K ; C - множество имен атрибутов. Кроме того, пусть
?D={d1,d2,...,dl,...,dL}, (14)
где l = 1, L ; D - множество значений. Далее, пусть
?Z={z1,z2,...,zm,...,zM}, (15)
{ }
?z m ? Z ?Ym = y m1 , y m 2 ,..., y mn m ,..., y mN m , (16)

где m = 1, M ; n m = 1, N m , Z - множество имен классов связей и Ym - множество имен
связей класса zm. Рассмотрим описание сущностей, для
{ }
?b iji ? B i ?C iji = c iji 1 , c iji 2 ,..., c ijipij ,..., c iji Pij , (17)
{ },
i i

?c ijipij ? C iji ?D ijipij = d ij1pij 1 , d ijipij 2 ,..., d ijipij rij p ,..., d ijipij Rij p (18)
i i i i i i iji i i iji


i = 1, I ; ji = 1, J i ; p iji = 1, Piji ; riji p ij = 1, R iji p ij . В модели данных "сущность-
где
i i

связь", каждая связь может описываться некоторым набором атрибутов, которые
могут иметь определенные множества значений. Другими словами, для
{ },
?y mnm ? Ym ?Cmnm = c mnm 1 , c mnm 2 ,..., c mnmsmn ,..., c mnmSmn (19)
m m

{
?c mnmsmn ? Cmnm ?Dmnmsmn = d mnmsmn 1 , d mnmsmnm 2 ,...,

},
m m m
(20)
d mnmsmn ,..., d mnmsmn
t T
m mnmsmnm m mnmsmnm


где m = 1, M ; n m = 1, N m ; smn m = 1, Smn m ; t mn m s mn = 1, Tmn m s mn .
m m

Пусть, E - это множество имен ролей множеств сущностей в связях,
(21)
E={e1,e2,...,eu,...,eU},
где u = 1, U . Введем следующее обозначение:
I
B = ? Bi . (22)
i =1

Итак, каждой связи соответствует некоторый набор двоек, описывающих
некоторые сущности и их роли, т.е.:
?y mn m ? Ym ?{< b mn m 1 , emn m 1 > , < b mn m 2 , emn m 2 > ,...,
(23)
> ,..., < b mn m Vmn , emn m Vmn >},
< b mn m v mn , emn m v mn
m m m m

где b mnm vmn ? B; emnm vmn ? E; m = 1, M ; n m = 1, N m ; v mn m = 1, Vmn m .
m m

В объектно-ориентированной базе данных (ООБД) информация хранится в
форме объектов, а сама ООБД характеризуется свойствами инкапсуляции,
наследования и полиморфизма. Следует особо отметить, что в настоящее время,
17

отсутствуют единые взгляды и стандарты на объектно-ориентированные СПД.
Большинство исследователей БД считает, что ООБД должны сочетать в себе лучшие
черты модели "сущность-связь" и реляционных БД. Таким образом, объектно-
ориентированные СПД, в некотором роде, являются частным случаем СПД модели
"сущность-связь".
База данных является неструктурированной, если каждый новый факт о
предметной области обладает собственной структурой и схема БД не может быть
фиксированной. В том случае, когда в качестве структур выступают кортежи
бинарных отношений, а функтор - есть имя бинарного отношения, ассоциативный
кортеж может быть интерпретирован семантической сетью, которая, в свою очередь,
сама является частным случаем модели данных "сущность-связь". Кроме выше
описанных, существует еще достаточно много различных моделей данных
(позиционных множеств, активные, временные, графоориентированные,
слабоструктурированные, инфологические, концептуальные, плоские,
неструктурированные дескрипторные и фреймовые, графовые, формально-
логические, алгебраические, теоретико-множественные и т.д.), но практически все эти
модели данных могут быть сведены к модели данных "сущность-связь". Перейдем к
анализу основных СПД традиционных моделей данных. Прежде всего, введем
понятие "уровень представления данных".
Определение 1. Если каждому элементу одного множества соответствует
некоторое другое множество элементов, тогда будем говорить, что существует
двухуровневое представление данных.
Понятие "уровень представления данных" необходимо для сравнительного
анализа возможностей по представлению данных СПД различных моделей данных. В
общем случае, может существовать N-уровневое представление данных. Отметим,
что большее количество уровней представления данных одной модели, говорит и о
больших "семантических" возможностях такой модели. Формулы 1 и 2 можно
рассматривать, с точки зрения введенного понятия, и как формальное определение
двухуровневого представления данных.
В реляционной модели не выделяют специально структуры для представления
данных о связях сущностей. Формулы 1, 2 и 3 показывают, что имеет место три
уровня представления данных. В сетевой модели анализ формул 4, 5 и 6 показывает,
что сетевые СПД о сущностях имеют три уровня. Выделяют следующие сетевые СПД
о связях сущностей: типы наборов-связей; реализации наборов-связей. При этом
каждому элементу множества Z из формулы 7 сопоставляется два различных
18

множества, описанных формулами 8 и 9. Такое описание, непосредственно, не
соответствует понятию уровня представления данных. В этом случае, можно
говорить, что каждому элементу из множества Z соответствует некоторое количество
множеств. Каждому такому множеству может быть определенным образом присвоено
некоторое имя (идентификатор). Затем, можно рассмотреть некоторое новое
множество имен множеств. Получаем, что каждому элементу zl множества Z
соответствует некоторое множество Wl - множество имен множеств, которое на
самом деле, состоит только из двух элементов, например: Y и X. Далее, каждому
элементу множества Wl соответствует некоторое множество Vlp l .
w lp l
Следовательно, можно представить формулы 7 - 10 так:
(24)
Z={z1,z2,...,zl,...,zL},
{ }
?z l ? Z ?Wl = w l1 , w l 2 ,..., w lpl ,..., w lPl , (25)
{ }
?w lpl ? Wl ?Vlpl = v lpl 1 , v lpl 2 ,..., v lplqlp ,..., v lplQlp , (26)
l l

где l = 1, L ; p l = 1, Pl ; q lp l = 1, Q lp l , Wl - это множество имен множеств реализаций

записей набора-связи zl и Vlp l - это множество реализаций записей типа w lp l набора-

связи типа zl. Отметим, что если p=1, то Vlp l = Y1 , а если p=2, то Vlp l = X1 ; где Y1 и
X1, берутся в смысле формул 8 и 9. Анализ формул 24 - 26 показывает, что
существует 3-уровневое сетевое представление данных о связях сущностей.
В модели данных "сущность-связь" имеют место четырехуровневое
представление данных о сущностях и четырехуровневое представление данных о
связях сущностей. СПД модели "сущность-связь" являются обобщением и развитием
всех традиционных моделей данных. Повышение "семантичности" описания
достигается путем введения дополнительного уровня представления данных.
Обобщение основных СПД традиционных моделей данных. С учетом
понятия "уровень представления данных" все основные СПД "графо-табличных"
моделей данных могут быть описаны в виде одномерных таблиц трехуровневого
представления данных (ОТПД-3).
Определение 2. ОТПД-3 - это таблица, предназначенная для хранения
данных и состоящая из следующих элементов: заголовок таблицы, заголовки
столбцов и клетки таблицы.
Где, "заголовок таблицы" - это некоторая совокупность данных,
описывающих всю таблицу, например, ее название, тип, класс, и т.д. "Заголовок
столбца" - это некоторая совокупность данных, которая описывает соответствующий
19

столбец клеток ОТПД-3. Каждый столбец ОТПД-3 имеет только один "заголовок
столбца". Каждый "заголовок столбца" относится только к одному столбцу. Столбец -
это аналог атрибута или элемента данных в соответствующих моделях данных.
"Заголовок столбца" может содержать, например, данные о названии атрибута-
элемента данных, о формате хранения, о типе данных, и т.д. Отметим, что при таком
подходе, столбец данных - это заголовок столбца и совокупность всех
соответствующих клеток, относящихся к этому столбцу. Тогда, таблица данных - это
заголовок таблицы, совокупность всех заголовков столбцов таблицы и все
совокупности клеток всех столбцов данной таблицы. Важно отметить, что, если в
реляционных таблицах количество клеток в различных столбцах одной таблицы
должно быть одинаковым, то в ОТПД-3 столбцы могут быть разного размера, т.е.
содержать разное количество клеток. "Клетки таблицы" - это некоторая
совокупность хранимых данных, которые и образуют "тело" таблицы представления
данных, т.е. это, непосредственно, и есть хранимые, накапливаемые данные,
организованные в соответствии с заголовками столбцов таблицы. Рассмотрим
формализованное описание структур представления данных ОТПД-3. Пусть A -
множество имен заголовков таблиц:
(27)
A={a1,a2,...,ai,...,aI},
{ }
?a i ? A ?B i = b i1 , b i 2 ,..., b iji ,..., b iJ i , (28)
{ },
?b iji ? B i ?C iji = c ij1 1 , c iji 2 ,..., c ijik ij ,..., c ijiK ij (29)
i i

где i = 1, I ; ji = 1, J i ; k iji = 1, K iji , Bi - это множество имен заголовков столбцов

заголовка таблицы ai и Ciji - это множество значений клеток таблицы заголовка

столбца b iji заголовка таблицы ai.
Одномерность определяется тем, что после проектирования БД количество
таблиц и столбцов в них фиксировано, а добавляются только строки (клетки)
таблицы. Таким образом, одномерная таблица трехуровневого представления
данных - это не одна таблица, в традиционном понимании, а такое представление
данных, которое совмещает три различные таблицы. Первая таблица описывает
ОТПД-3 в целом, вторая описывает столбцы ОТПД-3, и только третья таблица
содержит хранимые, накапливаемые данные в виде клеток, т.е. строк-записей.
Пятиуровневая одномерная таблица представления данных. Если ввести
пятый уровень, называемый "класс таблицы", то это позволит отделять описания
объектов от описания связей этих объектов. Пятиуровневые ОТПД (ОТПД-5)
20

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




класс ОТПД сущности / связи 1 уровень

вид ОТПД класс сущностей / связей 2 уровень

заголовок
множество сущностей / связей 3 уровень
ОТПД

заголовки атрибут 1 атрибут 2 атрибут N
столбцов сущности / сущности / ... сущности / 4 уровень
ОТПД связи связи связи

значения значения значения
сущности / сущности / сущности /
клетки ОТПД ... 5 уровень
связи связи связи
1,1 2,1 N,1

значения значения значения
сущности / сущности / сущности /
...
связи связи связи
1,2 2,2 N,2
... ... ... ...

значения значения значения
сущности / сущности / сущности /
...
связи связи связи
1,K 2,K N,K

Рис. 3. СПД модели "сущность-связь" в формализме ОТПД-5.


Подчеркнем, что числа N и M - фиксированы, а изменяются только числа K и
P. ОТПД-5 позволяют в явном виде сохранять отличия связей от объектов, а также
различия по категориям типов, по категориям вершин, по классам сущностей, по
категориям дуг и по классам связей, соответственно. ОТПД-5 представляют собой
обобщение структур представления данных модели "сущность-связь", ООБД,
гипертекстовых, "неструктурированных" и многих других СПД.
21

Итак, приведем полный список элементов ОТПД-5 (таблица 1): класс
таблицы, вид таблицы, заголовок таблицы, заголовок столбца, клетки таблицы.

Таблица 1.
Модель
Сетевая Бинарная
данных Реляционная Иерархическая Семантические
№ ОТПД-5 модель модель
модель модель сети
"сущность-
данных данных
связь"
1 класс ОТПД - - - - - -
класс
категории
категория
сущностей;
2 вид ОТПД - - - вершин;
типов
класс
категории дуг
связей
множества типы
категории;
заголовок классы вершин;
сущностей; записей;
3 отношения типы записей бинарные
ОТПД множества типы дуги
отношения
связей наборов
атрибуты
заголовки
сущности; элементы элементы функции
столбцов
4 атрибуты -
данных данных доступа
атрибуты
ОТПД
связи
значения реализации реализации объекты,
строки-
сущности; типов; типов; реализации;
5 значения значения вершины
значения реализации реализации реализации
ОТПД
связи наборов связей отношений


Рассмотрим формализованное описание структур представления данных
ОТПД-5. Пусть A - множество имен классов таблиц:
(30)
A={a1,a2,...,ai,...,aI},
{ }
?a i ? A ?B i = b i1 , b i 2 ,..., b iji ,..., b iJ i , (31)
{ },
?b iji ? B i ?C iji = c ij1 1 , c iji 2 ,..., c ijik ij ,..., c ijiK ij (32)
i i

? ?
?c ijik ij ? C iji ?D ijik ij = ? d ij1k ij 1 , d ijik ij 2 ,..., d ijik ij lij k ,..., d ijik ij Lij k ? , (33)
? ?
i i i i i i iji i i iji


?d iji k ij l ij k ? Diji k ij ?E iji k ij l ij k =
i i iji i i i iji

?
?E iji k ij l ij k = ? e ij1k ij l ij k 1 , e iji k ij l ij k 2 ,..., e iji k ij l ij k m ij k l ,...
(34)
?
i i iji i i iji i i iji i i iji i iji ijik iji

?
?,
..., eiji k ij l ij k M ij k l
i?
i i iji i iji iji k ij


где i = 1, I ; ji = 1, J i ; k iji = 1, K iji ; l iji k ij = 1, L iji k ij ; m iji k ij = 1, M iji k ij , Bi -
l l
i iji k ij i i ij i k iji
i i

это множество имен видов таблиц класса таблиц ai, Ciji - это множество имен

заголовков таблиц вида таблиц b iji класса таблиц ai, Diji k ij - это множество имен
i
22

заголовков столбцов заголовка таблицы ciji k ij вида таблиц b iji класса таблиц ai и
i

- это множество значений клеток таблицы заголовка столбца d iji k ij
Eiji k ij l ij k l
i iji k iji
i i iji

заголовка таблицы ciji k ij вида таблиц b iji класса таблиц ai.
i

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


Четвертый раздел диссертации посвящен разработке теоретических основ
построения многомерного информационного динамического пространства
унифицированного представления данных и правил. В этом разделе
проанализированы основные возможности нового представления данных, показан
переход от ОТПД к многомерному пространству представления данных, проведено
сравнение трехуровневых таблиц и трехмерного информационного динамического
пространства представления данных, подробно описаны СПД о точках такого
пространства и об их отношениях, приведен пример описания данных в многомерном
информационном пространстве унифицированного представления данных и правил.
Традиционная графо-табличная концепция представления данных, получившая
свое наибольшее развитие в модели данных "сущность-связь", ориентирована на
моделирование предметных областей, описываемых в виде изменяющихся данных
некоторой фиксированной структуры. Рассмотрим другой подход, основанный на
использовании многомерного информационного динамического объектно-системного
дискретного пространства унифицированного представления данных и правил.
Существуют различные подходы к решению проблемы описания поведения
сложной предметной области или некоторой развивающейся системы. Например,
применение "скользящей аксиоматической системы". В кибернетике поведение
системы обычно рассматривается в фиксированном пространстве Хi, причем,
поведение системы - это изменение ее состояний во времени, исходом которого
является некоторый результат. Однако, использование фиксированного пространства
состояний не позволяет описать поведение сложной развивающейся системы.
Поэтому для создания моделей развивающихся систем необходимо применять более
совершенный аппарат. Например, на основе математической структуры Н. Бурбаки
можно синтезировать целый класс различных моделей. В соответствии с работой
И.М. Яглома математическая структура Н. Бурбаки - это система:
(35)
S=<M, R>,
23

где M= {a, b, c, ...} - основное множество, а R={R1, R2, R3, ...} - множество унарных,
бинарных и других отношений. Однако, такая структура (формула 35) не описывает
динамики развития системы. Следовательно, для учета фактора времени в систему
необходимо добавить еще и время:
(36)
S(t)=<M(t), R(t)>,
где t - текущее время. Ю.Г. Ростовцев полагает, что более целесообразно
ввести понятие квазидинамической структуры, которая не изменяет свои элементы
M и R в пределах интервала времени [t0, t1]. После окончания этого интервала
времени параметры структуры изменяются скачками. Для развивающейся логической
обработки информации может использоваться система операторных алгоритмов
Ван Хао, возможности которой ограничены, но идея динамичности описания
предметной области может быть использована. Таким образом, для более адекватного
отображения объектов реального мира целесообразно разработать новый
математический аппарат.
Будем исходить из того, что реально существует некоторая предметная
область, а познающая система изучает и моделирует данную область. Полученные
сведения о предметной области накапливаются в некоторой системе представления
данных. Для решения этой задачи введем три равнозначных понятия: вещь (объект,
сущность), свойство (атрибут, характеристика), отношение (связь, взаимодействие).
Этих трех выделенных понятий-категорий достаточно для представления любой
информации о любой предметной области. Рассмотрим некоторое множество V
названий вещей. Так как каждое название является уникальным, то количество
элементов этого множества будет равно количеству выделенных вещей в
рассматриваемой предметной области. Затем, некоторые одинаковые свойства могут
быть обнаружены у различных вещей. Тогда можно рассмотреть некоторое
множество S названий свойств, состоящее из различных и уникальных названий-
элементов. Кроме того, существует третье множество O названий отношений,
состоящее из уникальных названий выявленных отношений вещей данной
предметной области. Итак, можно рассмотреть три различных множества названий:
V, S, О. Известно, что в определенных ситуациях вещь может рассматриваться, как
свойство или как отношение; свойство может рассматриваться, как вещь либо как
отношение и отношение может рассматриваться, как вещь или как свойство. Вещь не
существует вне свойств и отношений. Точно также, не существует свойств вне вещей
и вне отношений, как не существует и отношений вне вещей и вне свойств. Таким
образом, будем исходить из того, что некоторое "нечто" может быть и сущностью, и
24

свойством, и отношением, в зависимости от исследуемого предмета и его роли в этом
исследовании. Например, понятие "стол" - с одной стороны это сущность, но в
некотором смысле это может быть и отношение составных частей: столешницы,
ножек, крепежа и т.п. Кроме того, это может рассматриваться даже как свойство,
например, "ящик" или "пень" могут иметь свойство, в некоторых ситуациях, "быть
столом".
Основной идеей самоорганизующегося подхода является то, что реальный мир
существует сам по себе, но при изучении этого мира, в процессе познания, человек
(АСОИ) представляет себе описание этого мира в виде трехмерного пространства,
осями которого являются понятия: вещь, свойство и отношение. Эти три понятия -
абстракции удобные для описания реального мира. Эти абстракции аналогичны трем
осям Декартова геометрического пространства, так как это только три разных взгляда
на одно объективно существующее "нечто". Три разных и взаимосвязанных точки
зрения на одно и тоже "нечто", и позволяют нам выделять из предметной области
вещи, свойства и отношения. Эти три абстракции абсолютно равнозначны. Построим
трехмерное дискретное информационное пространство:
<вещь, свойство, отношение> (<V, S, O>).
Наименьший элемент этого пространства (трехмерная точка) - это некоторая
конкретная вещь, обладающая некоторым конкретным свойством, находящаяся в
некотором конкретном отношении в определенный момент времени и в конкретных
географических координатах. При таком подходе, вещь - это уникальное название
этой вещи, совокупность всех свойств (атрибутов) этой вещи и значения во всех
отношениях этой вещи со всеми другими вещами предметной области. Очень важно,
что степень детализации описания вещи может быть различной: от описания всех
свойств и отношений до представления лишь сущности вещи. При этом, существует
возможность адаптации данных (повышение адекватности), учета времени,
географического расположения, системного уровня, и объектных характеристик при
объектно-ориентированном подходе. "Физический" смысл "точки", с координатами
<v,s,o> состоит в том, что это некоторая вещь "v", обладающая некоторым свойством
"s" и находящаяся в некотором отношении "о". Принципиальным и новым является
то, что также как каждый пользователь имеет право на свой "центр мироздания",
точно также у каждого пользователя может быть свой персональный "горизонт"
трехмерного самоорганизующегося многомерного информационного динамического
пространства, что предполагает наличие некоторых общих подпространств, по типу
энциклопедий. Такая система хранения и обработки данных принципиально
25

позволяет в любой момент времени добавить, изменить, переупорядочить или
уничтожить любые данные.
Самоорганизующаяся концепция представления данных позволяет: работать с
динамическими (эволюционными) структурами хранения данных; использовать
неявные ассоциативные связи различных понятий и объектов (ассоциативный поиск);
вводить понятие меры близости - расстояния либо между отдельными "точками",
либо между их совокупностями; использовать меру подобия, схожести различных
структур; обрабатывать неоднородные данные, организуя связь между ними
посредством координат N-мерных точек. Кроме того, правила обработки данных и
непосредственно сами данные могут храниться в едином формате.
Самоорганизующееся представление включает в себя идеи объектно-
ориентированного программирования, более того, оно раскрывает новые
возможности и перспективы. Один и тот же объект в разных отношениях может
описываться с разной степенью детализации: от одного краткого идентификатора или
перечня нескольких наиболее важных характеристик, до полного описания всех
свойств и отношений. Кроме того, многомерная информационная концепция
открывает новые возможности по созданию информационных систем, работающих в
реальном масштабе времени без потери динамики изменения структуры.
Объединение трехмерного пространства <V,S,O> с трехмерным Декартовым
пространством <X,Y,Z> и с учетом времени T, позволит говорить о едином:
семимерном геометрико-временно-информационном пространстве. Особо отметим,
что при необходимости можно вводить дополнительные оси и размерности, а это
будет уже: N-мерное самоорганизующееся представление данных. Такой подход
позволяет проводить распределенную и параллельную обработку и защиту данных.
Самоорганизующаяся концепция появилась как обобщение и развитие традиционных
моделей данных. С точки зрения сетевых моделей, самоорганизующееся
представление - это некоторая сеть, находящаяся в координатном трехмерном
пространстве, что только расширяет возможности сетевых моделей. С точки зрения
реляционных моделей, самоорганизующееся представление - это трехмерная (или N-
мерная) реляционная таблица, находящаяся в трехмерном пространстве, в которой
собраны все обычные реляционные таблицы. Такие таблицы представления данных
позволяют эффективно хранить правила и отношения между объектами типа: "многие
ко многим" (M:N).
В трехмерном многомерном пространстве представления данных
(МППД-3) выделяют элементы следующих четырех типов множеств: заголовки
26

таблиц; заголовки столбцов; заголовки строк; клетки таблицы. При этом,
каждым трем элементам из трех различных множеств заголовков может
соответствовать только один элемент множества клеток. Рассмотрим
формализованное описание МППД-3. Пусть A - множество имен заголовков
таблиц:
?A={a1,a2,...,ai,...,aI}, (37)
Пусть существует В - множество имен заголовков столбцов, т.е.:
?B={b1,b2,...,bj,...,bJ}, (38)
Пусть существует D - множество имен заголовков строк, т.е.:
?D={d1,d2,...,dk,...,dK}, (39)
Кроме того, пусть существует С - множество клеток таблиц, т.е.:
?С={с111,с112,...,сijk,...,cIJK}, (40)
i = 1, I , j = 1, J , k = 1, K . Для любых трех элементов, принадлежащих
где
соответственно множествам A, В, D всегда существует единственный элемент,
принадлежащий множеству С, т.е.:
?ai?A, ?bj?B, ?dk?D ?! cijk?C. (41)
И наоборот, для любого элемента множества клеток таблиц С существует
единственный набор трехмерных координат пространства, т.е.:
?cijk?C ?!<i,j,k>. (42)
где i = 1, I , j = 1, J , k = 1, K - трехмерные координаты в МППД.
Основное отличие МППД-3 от ОТПД-3 заключается в том, что множества
заголовков таблиц, столбцов и строк являются независимыми, а, кроме того,
появляются элементы четвертого множества - клеток таблицы, в то время как в
ОТПД-3 различаются только три типа множеств: заголовки таблиц, заголовки
столбцов и строки клеток-записей. Наименьшей адресуемой частью данных при
операциях добавления, удаления и изменения в МППД-3 является отдельная клетка
таблицы, связанная с тремя соответствующими заголовками, а в ОТПД-3 - целая
строка клеток, которые относятся к одной записи реляционной таблицы. Можно
сделать вывод о том, что трехуровневые одномерные таблицы представления данных
ОТПД-3 являются частным случаем МППД-3.
В общем случае, можно рассматривать: K-мерное подпространство точек и
L-мерное подпространство отношений точек, которые образуют: N-мерное
самоорганизующееся информационное динамическое пространство
унифицированного представления данных и правил, где K+L=N.
27

Рассмотрим формализованное описание этого N-мерного пространства. Пусть:
?A={a1,a2,...,an,...,aN}, (43)
где n = 1, N ; A - множество названий осей самоорганизующегося пространства, N -
количество осей (динамическое) самоорганизующегося пространства. Тогда:
{ }
?a n ? A ?B n = b n1 , b n 2 ,..., b nin ,..., b nIn , (44)

i n = 1, I n ; Bn- множество точек оси an. Для любых допустимых значений координат
всегда существует определенная точка многомерного пространства:
?i 1 , i 2 ,..., i n ,..., i N ? < i 1 , i 2 ,..., i n ,..., i N > ? I 1 ? I 2 ? ... ? I n ? ... ? I N , (45)
где < i1 , i 2 ,..., i n ,..., i N > - координаты N-мерной точки.
Существует множество значений точек самоорганизующегося пространства:
?C = {c i 1i 2 ...i n ...i N | i 1 = 1, I 1 ;...; i n = 1, I n ;...; i N = 1, I N } . (46)
Для каждой точки самоорганизующегося пространства существует
единственное значение из множества значений C:
? < i1 , i 2 ,..., i n ,..., i N > ? ! c i 1 , i 2 ,..., i n ,..., i N ? C . (47)
Отметим, что в многомерном информационном динамическом пространстве
могут изменяться не только значения переменных, но и количество осей
пространства, т.е. сама структура представления данных. Таким образом,
предлагается новый класс моделей данных с изменяемой (эволюционной)
структурой представления данных. Такой подход позволяет хранить в едином
пространстве и сами данные, и правила их обработки - отношения объектов.
Отметим, что любое отношение также может быть добавлено, удалено или изменено.


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

между ними. Все операции над данными, которые есть в модели "сущность - связь",
могут быть реализованы в самоорганизующейся модели данных. Кроме того,
предложены новые операции над данными, которые расширяют возможности по
адаптивности, универсальности и оперативности обработки информации в АСОИ. Из
всех правил (отношений) и заданных (известных) значений формируется логическая
сеть вывода (обработки), управляемая потоком данных, которая может быть
представлена в виде трех списков: входных переменных, правил и выходных
переменных. Списочное представление логической сети позволяет изменить состав и
конфигурацию графа. Допустим, что если у правила заданы все входные переменные,
то могут быть однозначно определены и все выходные переменные. Таким образом,
получаем адаптивную логическую сеть обработки, управляемую потоком входных
данных, которая объединяет и обработку известных данных на основе известных
правил, и одновременно осуществляет обучение, изменение системы правил со
своевременным внесением изменений в соответствующие процессы обработки. Это
позволяет непрерывно обрабатывать новые входные переменные и обеспечивает
эволюционное, самоорганизующееся развитие АСОИ в целом. Кроме того, такая
активная логическая сеть позволяет распараллелить и повысить эффективность
обработки потока данных.
"Графовый" поиск маршрута логического вывода основан на использовании
теории графов в части построения многополюсных сетей и определения
минимального разреза (максимального потока). Данный метод называется
"графовым", потому что для поиска маршрута вывода строится граф обработки, с
одной стороны от исходных, известных значений, а с другой стороны - от требуемых,
искомых значений. Затем осуществляется анализ связности этого графа путем поиска
его минимального разреза. Если минимальный разрез больше или равен единице, то
решение существует и определяется кратчайший, минимальный путь достижения
требуемых результатов, а затем на этой основе непосредственно запускается
механизм вывода и обработки данных, что позволит значительно экономить
вычислительные ресурсы. Если минимальный разрез равен нулю, то цепочки вывода
нет, но можно определить значения каких переменных необходимы для уточняющего
запроса, что и является признаком "интерактивности".
Преобразование логической сети правил в многополюсную сеть теории графов
осуществляется следующим образом. Выделяют два типа узлов: переменные и
процедуры. Переменные преобразуются в узлы-переменные, правила - в узлы-
процедуры, а их взаимосвязи - в ребра многополюсной сети и получают двудольный
29

ориентированный граф. Затем выделяют две группы узлов-переменных: "входные" и
"искомые". Построение многополюсной сети начинают с группы входных
переменных, которые образуют полюса этой сети. Искомые переменные образуют
другую группу полюсов этой сети. От "входных" полюсов осуществляют постепенное
построение многополюсной сети до "искомых" полюсов.
Адаптивный механизм логического вывода на сети гиперправил с
мультиактивизаторами, управляемой потоком данных. Одним из наиболее
перспективных формализмов представления
знаний являются гиперправила с
мультиактивизаторами (ГПМ). Существо
предлагаемого подхода к построению
адаптивного механизма логического вывода на
активной эволюционной сети ГПМ, управляемой
потоком данных, в том, что из всех возможных
ГПМ и известных объектов (активизаторов,
переменных) формируется логическая сеть ГПМ.
На ее основе строится двудольный
ориентированный граф и на этом графе
формируется подграф логического вывода
Рис. 4.
(рис. 4). На полученном подграфе выполняется
поиск маршрута логического вывода путем анализа его связности.
В теории графов известно достаточно много алгоритмов поиска минимального
разреза (или максимального потока) кубической вычислительной сложности и
меньше: до О(n2,5) (алгоритм Карив-Арбиб). Рассмотрим квадратичной сложности
метод поиска минимального разреза многополюсных сетей. Адаптивную
логическую сеть правил можно представить в виде некоторого многоуровневого
многотипового динамического графа: G=(V, X), в котором, n- количество вершин.
Граф, в котором выделено S вершин, называют S-полюсной сетью или
многополюсной сетью. В данном случае, полюса - это заданные и искомые
логические переменные. Разрез - это множество удаляемых вершин и ребер, которое
разбивает граф на S компонент по числу полюсов сети, при этом различные полюса
находятся в различных компонентах. Рассмотрим случай разреза двухполюсной сети
по ребрам. Некоторым образом все вершины нумеруются: первый полюс - 1, а второй
полюс - n. Пусть значения всех коэффициентов ребер равны 1. Строим
нижнетреугольную матрицу смежности А следующим образом:
30

1. ?i ,? j a ij = 0; i = 1, n; j = 1, n.

2. j=1: aij=1 для всех i = j + 1, n .
3. ? j, i = j + 1, n если эти вершины связаны ребром, то aij=1.
Количество ребер графа равно сумме значений всех клеток матрицы. Если граф
разбивается на две части (в первой k вершин, а во
1 р
второй остальные - (n-k)), то все ребра, связывающие
2 1
вершины из разных частей графа принадлежат
3 11
4 11 прямоугольнику, образованному клетками
5 1 нижнетреугольной матрицы (рис. 5), которые
6 1
расположены ниже k-той строки и левее (n-k)-того
7 1
8 11 столбца. Если граф разбит на два компонента, то
9 1
практически матрица распадается на две подматрицы,
10 11р
1 2 3 4 5 6 7 8 9 10 а соответствующий прямоугольник является нулевым
Рис. 5. (PRк). Для нахождения минимального разреза в
нижнетреугольной матрице необходимо просуммировать все прямоугольники при k
от 1 до (n-1), а затем выбрать минимальный, которому и будет соответствовать
искомый разрез. Процедура определения суммы:
n
1. PR 1 = ? a i1 , где: k=1; j=1; i = j + 1, n .
i=2

n
2. PR 2 = PR 1 ? a 21 + ? a i 2 , где: k=2.
i=3

k ?1 n
3. PR k = PR k ? 1 ? ? akj + ? a ik .
j= 1 i =k +1

Из всех PRk выбираем минимальный. Всего определяются суммы для (n-1)-го
прямоугольника, при этом выполняется (k-1)
1 p вычитание и (n-k) сложение, т.е. всего (n-1) действий.
2 1
Получаем сложность: (n-1)2, т.е. О(n2). Особенностью
3 11
данного подхода является то, что для многополюсной
4 11
5 p сети строится фактически такая же матрица, в которой
1
6 1
по мере связности указаны все вершины и полюса
7 1
(рис. 6). В полученной матрице ищем разрез 1-го
8 11
9 полюса от всех остальных, который соответствует
1
10 11p
прямоугольникам от 1-го до 2-го полюса. Затем
1 2 3 4 5 6 7 8 9 10
Рис. 6.
31

определяем разрез 2-го полюса от всех и так далее. Из всех прямоугольников между
соседними полюсами выбираем минимальные и получаем минимальный разрез
многополюсной сети по ребрам. Сложность алгоритма даже меньше, чем для
двухполюсной сети за счет того, что, определив минимальный прямоугольник, в
дальнейшем все операции производят только с оставшейся частью матрицы
смежности (снижается размерность).
Линейный матричный метод поиска маршрута логического вывода на
сети правил. Суть метода в том, что для некоторой сети правил строится матрица, на
основе анализа которой выявляется факт наличия маршрута вывода, определяются
возможные маршруты и из этих маршрутов выбирают "кратчайший", наиболее
оптимальный по заданным критериям. Пусть известны m - правил и n - переменных.
Тогда в матрице V (n ? m) представлены все взаимосвязи между правилами и
переменными. При этом, входные переменные правила помечаются символом x,
выходные - y, "выводимые" переменные - z, а все искомые переменные - w.
В матрицу V добавим одну строку и
V 1 2 3 4 5 ... n-2 n-1 n n+1
один столбец для хранения служебной
1 x x x y y
информации. Тогда, получаем матрицу V
2 x y y x x
размерности (n+1) ? (m+1), в которой
... ...
отражена вся структура исходной сети
m x x x y
правил, которая может изменяться
m+1
(рис. 7). Для поиска маршрута вывода
Рис. 7.
производят следующие действия.
1. В строке (m+1) помечают известные z и искомые w переменные.
2. Поиск "запускаемых" правил: если таких правил нет, то - запрос на уточнение
входных данных; если правила есть, то они помечаются в служебной строке.
3. Если "запускаемых" правил несколько, то выбираются такие правила, которые
должны быть активизированы в первую очередь.
4. Имитация запуска правила осуществляется путем присваивания выводимым в этом
правиле переменным значений "известно" (z).
5. После "запуска" правил анализируют вывод искомых переменных. Если все
искомые переменные определены, то успешное завершение работы.
6. Аналогично п. 2 определяют наличие "запускаемых" правил после определения
новых значений на предыдущем этапе. Если правил нет, то запрос на
дополнительную информацию. Если правила есть, то идут на п.7.
32

7. Аналогично п. 4 "запускают" правила, далее аналогично п.п. 5 и 6 выполняют в
цикле необходимые действия до получения результата.
8. При необходимости, повторяют все п.п. со 2 по 7 до достижения результата или до
использования всех переменных. При этом результат может быть как
положительный - маршрут вывода существует, так и отрицательный - вывода нет
из-за неопределенности входных данных.
На рис. 8 в служебной строке больше не осталось искомых правил, а в клетках
таблицы появились новые значения: в клетке (n+1, m) - 2, а в клетке (n-2, m+1)
вместо значения w появилось значение z,
V 1 2 3 4 5 ... n-2 n-1 n n+1
т.е. маршрут логического вывода при
1 x x x y y 2
данных исходных значениях существует.
2 x y y x x 2
Общее количество действий при
... ...
матричном методе определяется суммой
m x x x y 2
действий на каждом этапе: присваивание
m+1 z z z z z z(w) z z
известных z и искомых w значений
Рис. 8.
клеткам служебной строки (m+1), общее
количество таких действий не более n; присваивание признака обработки правил в
служебном столбце (n+1), количество действий не более 2m, но может быть не более
числа m; присваивание известных z значений клеткам служебной строки (m+1),
общее количество таких действий не более n; определение новых значений клеткам
строки (m+1), количество таких действий не более n. Отметим, что фактически на 1,
3 и 4 этапе производится обработка одного массива данных, т.е. клеток служебной
строки (m+1). При этом общее, суммарное количество действий на всех этих этапах
(1, 3 и 4) не должно превышать общее количество клеток в этой строке, т.к.
обработанные значения "вычеркиваются" и более не обрабатываются. Получаем, что
общее количество действий (KD) при линейном матричном методе поиска маршрута
логического вывода (вычислительная сложность) не должно превышать количества
клеток в служебных частях матрицы: О(n+m), т.е. KD ? (n+m). В том случае, когда
нельзя реализовать предложенные сокращения вычислений, этот метод решает задачу
поиска маршрута логического вывода с вычислительной сложностью: О(nm).


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

исследованы параметры предлагаемых виртуальных потоковых БД, а также
проведена оценка быстродействия обработки потока данных различными методами,
которая доказала максимальность распараллеливания доступа предлагаемого метода.
Каждому процессу выделим виртуальный образ ресурса БД и организуем
централизованное корректное управление, как виртуальными образами, так и самим
ресурсом, на основе построения виртуальной потоковой базы данных (ВПБД). В
зависимости от времени поступления, все элементы (наборы элементов) входного
потока (элементы множества А) и соответствующие им процессы обработки
(элементы множества Р) могут быть разделены на: старших (поступивших на
обработку ранее) и младших.
Определение 3. Потоковая параллельность обработки БД - это такая
обработка элементов входного потока, когда одновременно обрабатываются
несколько однотипных по названию переменных, которым присвоены различные
значения и при этом выполняется следующее условие: младшие процессы не могут
влиять на старшие процессы, а старшие процессы могут вносить такие данные,
которые оказывают влияние на младшие процессы.
Для каждого процесса обработки pi требуется некоторый интервал времени
inti, необходимый для завершения данного процесса, следовательно, имеет место
следующее множество пар: {< p i , int i >}. Интервалы времени обработки различных
процессов pi могут различаться: ?i ? i?:int i ? int i ? . Если ti - начало обработки, inti -
величина интервала времени обработки, то: (ti + inti ) - время окончания обработки
pi.
процесса Для любого достаточно длительного интервала времени

стр. 1
(всего 2)

СОДЕРЖАНИЕ

>>