Книги, научные публикации
На правах рукописи
УДК 004.82 Варламов Олег Олегович Системный анализ и синтез моделей данных и методы обработки информации в самоорганизующихся комплексах оперативной диагностики 05.13.01 -
Системный анализ, управление и обработка информации (в оборонной и гражданской технике)
Автореферат диссертации на соискание ученой степени доктора технических наук
Москва - 2003 2
Работа выполнена в Московской академии рынка труда и информационных технологий (МАРТИТ).
Научный консультант: академик РАН, доктор технических наук, профессор Каляев Анатолий Васильевич.
Официальные оппоненты:
член-корреспондент РАН, доктор технических наук, профессор Хорошевский Виктор Гаврилович, доктор технических наук, профессор Афанасьев Валерий Николаевич, доктор технических наук, профессор Богатырев Владимир Ильич.
Ведущая организация - Институт проблем информатики РАН.
Защита состоится "16" октября 2003 г. в 14.00 часов на заседании диссертационного Совета Д 850.001.01 при Московской академии рынка труда и информационных технологий (МАРТИТ) по адресу: 121351, г. Москва, ул. Молодогвардейская, д. 46, корп. 1, телефон (095) 149-86-38.
С диссертацией можно ознакомиться в библиотеке Московской академии рынка труда и информационных технологий.
Автореферат разослан "5" июня 2003 г.
Ученый секретарь диссертационного совета, профессор Чересов Ю.И.
й О.О. Варламов,
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Одной из основных проблем, решаемых при создании автоматизированных систем обработки информации (АСОИ), в целом, и программно аппаратных комплексов (ПАК) оперативной диагностики (ОД) в частности, является обеспечение, в условиях их непрерывного функционирования, адаптации программно-аппаратных средств для эффективного и оперативного решения сложных задач. Анализ актуальных научных проблем создания АСОИ показал, что необходимо, прежде всего, решить следующие две взаимосвязанные проблемы.
Первая проблема - это создание интерактивных самоорганизующихся баз данных (БД) и знаний, на основе которых возможно создание программного обеспечения АСОИ. Отметим, что, так как фактически в "базах знаний" хранятся правила, процедуры и отношения объектов, то вместо термина "знания" будем применять термин "правила". Подчеркнем, что особую актуальность решению первой проблемы придает то, что в последнее время теория баз данных оказывает определяющее воздействие на многие смежные области. Например, БД используются при создании перспективных ЭВМ, что определяет место и роль второй научной проблемы:
создание теоретических основ адаптивного синтеза информационно-вычислительных конфигураций (ИВК) АСОИ. Основное направление решения данной проблемы - это создание систем адаптивного синтеза (САС) самоорганизующихся конфигураций АСОИ. Две эти проблемы решают на разных уровнях: на уровне программного обеспечения (первая) и на уровне аппаратных средств (вторая), фактически одну и ту же проблему - создание самоорганизующихся АСОИ (ПАК ОД).
Системный анализ задач, которые необходимо решить как для создания самоорганизующихся баз данных и правил (СБДП), так и для построения САС ИВК, показал их взаимозависимость, поэтому обе эти проблемы в совокупности образуют одну крупную научную проблему. Следовательно, разработка теоретических основ создания СБДП и САС ИВК для построения самоорганизующихся программно аппаратных комплексов оперативной диагностики (СПАКОД) является актуальной крупной научной проблемой. Решение этой новой проблемы имеет важное хозяйственное значение для целого ряда областей (медицины, экономики, юриспруденции, анализа чрезвычайных ситуаций, метеорологии и др.). Отдельные наиболее сложные задачи этих областей могут быть отнесены к классу ресурсоемких научно-практических задач оперативной диагностики. Как правило, это уникальные задачи, решение которых носит эмпирический характер и требует научно обоснованного синтеза специализированных ИВК. Известные технологии БД и САПР не применимы в этом случае. Противоречие в том, что в условиях дефицита времени требуется оперативно синтезировать уникальный самоорганизующийся ПАК с использованием всех доступных ресурсов, включая Интернет, для обеспечения экспресс-диагностики сложных уникальных задач. Как правило, это NP-полные задачи, которые в зависимости от конкретной ситуации, могут быть сведены к набору полиномиальных задач, решаемых за обозримое допустимое время с учетом конкретных ограничений. На программном уровне эволюционность СПАКОД обеспечивается СБДП, а на аппаратном уровне - САС ИВК.
Адаптивность синтеза ИВК обусловлена уникальностью каждой диагностической задачи, необходимостью учета ранее разработанных вариантов конфигураций, быстротой создания, развития и старения программных и аппаратных средств. Для синтеза требуемых конфигураций фактически необходимо разработать некоторую новую САПР на основе распределенных СБДП. Используемые данные необходимо хранить в едином структурированном пространстве унифицированного представления данных и правил с целью научно-обоснованного всеобъемлющего синтеза уникальных конфигураций ЭВМ и последующего оперативного решения задачи. САС ИВК может являться ядром формируемых СПАКОД.
Таким образом, актуальность крупной научной проблемы разработки СБДП и САС ИВК для создания СПАКОД обусловлена тем, что необходимо в минимальное время достижение максимального быстродействия для решения диагностической задачи в ситуации, когда нахождение правильного решения имеет жизненно-важное значение, цена которого априори во много раз превышает стоимость затрат на синтез компьютерной системы. Следовательно, известные методы синтеза ЭВМ (ИВК), основанные на коммерческой эффективности, в таких ситуациях не применимы.
Научная проблема: разработка теоретических основ построения самоорганизующихся программно-аппаратных комплексов оперативной диагностики за счет использования известных технологий автоматизированного проектирования и создания интерактивных самоорганизующихся баз данных и правил, изыскания принципов построения и применения систем адаптивного синтеза информационно вычислительных конфигураций, разработки быстродействующих методов обработки информации, что позволит уменьшить время решения уникальных диагностических задач, снизить материально-финансовые затраты и повысить эффективность разработки и эксплуатации компьютерных систем.
Цель работы: решение крупной научной проблемы разработки теоретических основ построения самоорганизующихся программно-аппаратных комплексов оперативной диагностики для повышения, по заданным критериям, эффективности решения сложных оперативных диагностических задач в условиях дефицита времени, неопределенности и непрерывности функционирования, что имеет важное значение для развития экономики страны и повышения ее обороноспособности.
В соответствии с поставленной целью определены задачи диссертации:
1) изыскать принципы построения и применения систем адаптивного синтеза информационно-вычислительных конфигураций;
2) в теории баз данных провести системный анализ, сравнение и обобщение основных структур представления данных (СПД) традиционных моделей данных;
3) разработать теоретические основы создания интерактивных самоорганизующихся баз данных и правил;
4) создать метод обработки данных на основе применения интерактивной самоорганизующейся логической сети правил, управляемой потоком данных;
5) разработать быстродействующий метод "графового" поиска маршрута логического вывода путем построения многополюсной сети теории графов и определения ее минимального разреза;
6) разработать метод распараллеливания потокового множественного доступа к общей базе данных в условиях недопущения взаимного искажения данных;
7) разработать метод алгоритмической минимизации необходимого количества устройств и вычислительных процедур сложения для единично-инкрементного суммирования чисел.
Научная новизна диссертации заключается в том, что в ней впервые:
1) предложены принципы построения и применения систем адаптивного синтеза информационно-вычислительных конфигураций;
2) на основе применения пятиуровневых одномерных таблиц представления данных осуществлено описание, системный анализ, сравнение и обобщение основных структур представления данных графо-табличных моделей данных;
3) разработаны теоретические основы создания интерактивных самоорганизующихся баз данных и правил путем построения многомерного информационного динамического пространства унифицированного представления данных и правил;
4) предложен метод обработки данных на основе применения интерактивной самоорганизующейся логической сети правил, управляемой потоком данных;
5) разработаны быстродействующий метод "графового" поиска маршрута логического вывода, матричный метод поиска маршрута логического вывода и квадратичные методы поиска минимального разреза многополюсных сетей;
6) разработан метод распараллеливания потокового множественного доступа к общей базе данных в условиях недопущения взаимного искажения данных;
7) разработан метод алгоритмической минимизации количества процедур и устройств сложения для единично-инкрементного суммирования чисел.
Достоверность полученных результатов обеспечивается использованием аппарата математической логики, теорий множеств, графов, структур данных, принятия решений, системного анализа, математического программирования и оптимизации на сетях и графах, полнотой и корректностью исходных предпосылок, математической строгостью доказанных утверждений и преобразований при получении аналитических зависимостей, а также результатами имитационного моделирования и практической реализации.
Для публичной защиты выдвигается следующая совокупность новых научных результатов и положений:
1. К концу 20 века были разработаны: либо одномерные многоуровневые, либо многомерные, либо динамические базы данных и знаний. Возрастание потребностей науки и практики сделало актуальным решение новых сложных задач оперативной диагностики в условиях многомерного, динамического и непрерывного функционирования комплексов оперативной диагностики.
Известные технологии БД и САПР не применимы для синтеза таких комплексов.
Противоречие в том, что в условиях дефицита времени требуется оперативно синтезировать ("под задачу") уникальный комплекс с использованием всех доступных ресурсов, включая Интернет, для обеспечения экспресс-диагностики сложных задач. Затем, комплекс переформировывается, самоорганизуется для решения новой уникальной задачи.
2. Совокупность взаимосвязанных проблем создания СБДП, САС ИВК и методов обработки информации образует единую крупную научную проблему разработки основ построения СПАКОД, от успеха решения которой зависит оперативность диагностики в медицине, метеорологии, юриспруденции и т.п.
3. Адаптивность синтеза ИВК обусловлена уникальностью каждой диагностической задачи, необходимостью учета ранее разработанных конфигураций, быстротой создания и старения программных и аппаратных средств. Исходные данные для синтеза ИВК и решения задач, могут быть в различных форматах представления данных и знаний, но их необходимо хранить в едином структурированном унифицированном пространстве представления данных и правил.
4. Для обеспечения эволюционного развития комплексов оперативной диагностики предложено на программном уровне ввести СБДП, а на аппаратном - САС ИВК.
5. Для создания САС ИВК предложены принципы их построения и применения.
6. Для создания СБДП проведено обобщение СПД моделей данных путем применения пятиуровневых одномерных таблиц представления данных и предложены основы построения многомерного информационного динамического пространства унифицированного представления данных и правил.
7. Для обеспечения эволюционности логической обработки информации создан метод обработки данных на основе применения интерактивной самоорганизующейся логической сети правил, управляемой потоком данных.
8. Для повышения быстродействия обработки информации разработаны: метод "графового" поиска маршрута логического вывода;
квадратичной сложности методы поиска минимального разреза (максимального потока) двухполюсных и многополюсных сетей;
линейной сложности матричный метод поиска маршрута логического вывода на сети правил.
9. Для повышения параллельности и оперативности обработки информации разработан метод распараллеливания потокового множественного доступа к общей базе данных в условиях недопущения взаимного искажения данных.
10. Для повышения быстродействия единично-инкрементного суммирования чисел разработан и запатентован новый метод (способ) суммирования чисел.
Практическая ценность работы определяется тем, что:
1) основы создания СБДП и принципы построения и применения САС ИВК обеспечивают возможность создания самоорганизующихся программно аппаратных комплексов оперативной диагностики;
2) основы создания СБДП позволяют адаптивно и своевременно наращивать объем хранимой информации и обрабатывать ее с применением интерактивной эволюционной логической сети правил, управляемой потоком данных, что повышает интеллектуальные способности АСОИ;
3) интерактивная самоорганизующаяся логическая сеть, управляемая потоком данных, объединяет обработку известных данных на основе известных правил и осуществляет обучение, изменение системы правил, что обеспечивает эволюционное развитие всей компьютерной системы в целом;
4) методы поиска маршрута логического вывода и минимального разреза позволяют снизить вычислительную сложность поиска маршрута логического вывода до квадратичной;
5) методы поиска минимального разреза позволяют снизить сложность поиска минимального разреза (максимального потока) двухполюсных и многополюсных сетей с кубической до квадратичной;
6) метод алгоритмической минимизации количества процедур и устройств для единично-инкрементного суммирования чисел позволяет перейти от степенной к линейной зависимости количества операций сложения от разрядности чисел;
7) матричный метод поиска маршрута логического вывода позволяет снизить сложность поиска маршрута логического вывода до линейной;
8) интерактивная самоорганизующаяся логическая сеть позволяет распараллелить логическую обработку потока данных;
9) метод распараллеливания потокового множественного доступа к общей БД реализует максимальное быстродействие (без накопления времени задержки) обработки данных;
10) предложенные основы и методы в совокупности позволяют повысить эффективность разработки, эксплуатации и модернизации компьютерных систем (АСОИ) за счет оптимизации синтеза конфигураций по критерию отношения реальной производительности к стоимости;
11) предложенные основы и методы в совокупности позволят уменьшить время решения сложных задач за счет общего повышения производительности адаптивных ЭВМ относительно традиционных, в среднем за период эксплуатации, на половину разности производительности следующих и современных поколений ЭВМ (не менее чем в 50 раз);
12) предложенные научные основы, принципы и рекомендации совместно с применением ЭВМ с программируемой архитектурой, разрабатываемых под руководством академика РАН Каляева А.В., в совокупности позволят повысить реальную производительность адаптивных самоорганизующихся ЭВМ вдвое, т.е.
относительно пиковой мощности обычных ЭВМ с 10-30 % до 50-70 %;
13) полученные новые научные результаты и рекомендации могут использоваться как по отдельности, так и вместе для решения проблемы создания самоорганизующихся комплексов оперативной диагностики, а также для снижения материально-финансовых затрат на разработку и эксплуатацию АСОИ.
Основные результаты диссертационной работы получены автором единолично (без соавторов). Эти результаты реализованы, внедрены и используются в Государственном научно-исследовательском испытательном институте проблем технической защиты информации Гостехкомиссии России, Таганрогском радиотехническом университете (ТРТУ), Академии налоговой полиции ФСНП России, ОАО "НИИ СуперЭВМ", ОАО "НИИ ВК им. М. А. Карцева" и др. Получен патент на изобретение.
Апробация работы. Основные результаты работы докладывались, одобрены и опубликованы в материалах международных научных конференций "Интеллектуальные и многопроцессорные системы" (ИМС) ТРТУ, ЦНИИРЭС, научных сессий МИФИ и др.
Публикации. Основные научные результаты диссертации опубликованы в 35 научных работах, из них: 2 монографии, 20 статей, 1 патент, 12 докладов.
Структура и объем диссертации. Диссертация состоит из введения, семи разделов, заключения и списка литературы из 352 наименований. Она содержит 307 страниц текста, 16 таблиц, 43 рисунка.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность крупной научной проблемы, проанализирован научный уровень создания АСОИ, сформулированы цель и задачи исследования, дан краткий обзор содержания диссертации, перечислены полученные новые научные результаты и приведены сведения о практической ценности работы.
В первом разделе рассмотрена проблема создания самоорганизующихся БД и правил для синтеза комплексов оперативной диагностики, сформулирована проблема адаптивного синтеза информационно-вычислительных конфигураций. Понятие "самоорганизующиеся комплексы оперативной диагностики" не является строго определенным термином, но их БД должны быть эволюционными. Действительно эволюционной может быть только БД с изменяемой структурой данных.
Традиционные структурированные модели данных БД предназначены для автоматизации обработки данных в таких предметных областях, структура описания данных которых фиксирована. При изменении концептуальной модели предметной области проектирование структуры БД необходимо фактически делать заново.
Существуют неструктурированные модели данных, но для них характерны другие недостатки, связанные со сложностью реализации высокоскоростной обработки данных. Кроме того, наличие структуры представления данных позволяет проводить систематизацию данных, ассоциативную обработку, а многомерность значительно ускоряет обработку любых массивов. К структурированным моделям данных относятся реляционные, сетевые, иерархические модели, модель "сущность-связь", а к неструктурированным - гипертекст, символьная модель и др. Отметим, что если принято различать два типа данных: структурированные и неструктурированные, то самоорганизующиеся базы данных можно отнести к новому типу представления данных с изменяемой структурой. Такая структура обладает возможностью эволюционного наращивания, а при необходимости и кардинального изменения, даже в условиях непрерывности функционирования системы.
Проблема адаптивного синтеза информационно-вычислительных конфигураций. В настоящее время синтез конфигураций новых поколений ЭВМ приобретает особую актуальность, что обусловлено постоянно возрастающими потребностями решения различных диагностических задач. Кроме того, актуальность создания именно адаптивных ЭВМ обусловлена необходимостью постоянной модернизации АСОИ в условиях непрерывности их функционирования. Современные ЭВМ могут содержать тысячи вычислительных блоков, одновременная замена которых требует больших финансовых и временных затрат. Создание адаптивных ЭВМ позволит изменить процесс проектирования многопроцессорных вычислительных систем, а также обеспечит возможность наращивания и проведения поэтапной модернизации модулей ЭВМ в условиях эксплуатации. В настоящее время, в области создания суперЭВМ возникло противоречие, которое состоит в том, что для любой задачи наиболее эффективными являются специализированные устройства, но их производство оказалось в новых условиях экономически нецелесообразным.
Поэтому, теперь ЭВМ собирают из множества унифицированных модулей, производимых различными фирмами. Более того, можно самостоятельно собрать суперЭВМ и одна из них уже вошла в 2001 году в "TOP-500".
Актуальность проблемы адаптивного синтеза ИВК обусловлена изменением принципов создания ЭВМ;
уникальностью каждой задачи;
необходимостью обучения и учета, ранее разработанных вариантов конфигураций;
быстротой создания, развития и старения программных и аппаратных средств.
Современное развитие Рис. 1.
науки и техники позволяет из унифицированных комплектующих на ИНФОРМАЦИЯ необходимый для решения задачи период МОДЕЛИ времени собрать неоднородную ЭВМ, КЛАССОВ МОДЕЛИ ИВК САС ЗАДАЧ которая после решения этой задачи ИВК может быть адаптирована для решения других задач (рис. 1). Методы синтеза АДАПТАЦИЯ отдельных ЭВМ известны, но проблема адаптивного синтеза конфигураций ЭВМ ОЦЕНКА ЗАДАЧИ КОНФИГУРАЦИЯ ЭВМ ИВК не решена. Для проектирования адаптивных ЭВМ необходимо создать систему адаптивного синтеза РЕШЕНИЕ ЗАКАЗЧИК информационно-вычислительных Рис. 2.
конфигураций (САС ИВК) (рис. 2). В САС ИВК должна оперативно накапливаться информация о решаемых задачах и существующих компонентах ИВК. САС ИВК должна быть многопроцессорной самоорганизующейся неоднородной АСОИ, в которой можно в условиях эксплуатации добавлять, изменять и удалять любые модули, средства и данные.
Отметим, что особый интерес, с точки зрения адаптации ЭВМ под различные классы задач, представляют разрабатываемые под руководством академика РАН Каляева А.В. вычислительные системы и модули с программируемой под структуру решаемой задачи архитектурой. При реализации адаптивного синтеза на ЭВМ с программируемой архитектурой представляется возможным создать адаптивную АСОИ. В такой адаптивной АСОИ создается БД известных структур задач и описание (каталог) архитектур вычислительных модулей. При поступлении на вход системы некоторой задачи производится ее анализ, определяется ее структура и из каталога архитектур вычислительных модулей выбирается наиболее адекватный модуль, затем производят перепрограммирование архитектуры вычислительных модулей и непосредственное решение требуемой задачи. Если для поступившей задачи в каталоге архитектур существует оптимальный вариант архитектуры вычислительных модулей, то это реализуется в автоматическом режиме. Если в каталоге нет подходящей архитектуры, то формируется сигнал вызова администратора и система переходит в автоматизированный режим, когда человек принимает решение о выборе "нужной" архитектуры или формирует новую архитектуру и добавляет ее в каталог.
Универсальные ЭВМ решают реальные задачи с эффективностью 10-15 % от пиковой производительности, в то время как специализированные ЭВМ позволяют добиться 80-90 % эффективности. Внедрение адаптивного синтеза на вычислительных системах с программируемой архитектурой позволит создать достаточно универсальную самоорганизующуюся АСОИ, которая будет решать широкий класс задач с эффективностью не менее 60-70 % от пиковой производительности ЭВМ. После внедрения и реализации самоорганизующихся АСОИ закупать можно будет только самые современные комплектующие, добавляя их в новые эволюционные ИВК. Таким образом, в настоящее время изменились как задачи, так и возможности по созданию ЭВМ, что выявило новые научные проблемы и определило необходимость нетрадиционных подходов к их решению. Сегодня есть все предпосылки для решения проблемы адаптивного синтеза ИВК и построения самоорганизующихся компьютерных систем.
Во втором разделе исследованы принципы построения однородных вычислительных систем, проведен системный анализ основных путей создания эволюционных неоднородных компьютерных систем (ЭНКС) и предложены принципы построения и применения САС ИВК. СПАКОД относятся к классу многопроцессорных вычислительных систем (МВС), которые состоят из трех основных компонент: процессоры, модули памяти и коммутирующая сеть. Основным принципом построения однородных МВС является то, что коммутирующая сеть соединяет однородные процессоры друг с другом и с модулями памяти.
В настоящее время во всем мире проводятся активные исследования по изысканию возможных путей создания эволюционных и неоднородных компьютерных систем. Так как все однородные системы могут рассматриваться как частный случай неоднородной системы, то данные исследования обобщают весь накопленный опыт и открывают новые перспективы развития МВС. Неоднородные МВС предназначены для оптимизации выполнения больших задач, включающих программы с разными формами параллелизма. Создание эволюционных компьютерных систем позволит изменить процесс проектирования, создания и эксплуатации ЭВМ. Эволюционные компьютерные системы в общем случае должны быть неоднородными. Существует противоречие между универсальностью ЭВМ и требованиями эффективности, производительности при решении конкретных задач.
Неоднородные компьютерные системы повысят универсальность ЭВМ за счет подключения к системе специализированных устройств.
Проведенный анализ показал, что наиболее рациональным путем построения СПАКОД следует считать создание систем адаптивного синтеза информационно вычислительных конфигураций - САС ИВК. Известно достаточно много систем синтеза вычислительных конфигураций, но до сих пор не достаточно полно рассматривались вопросы адаптивного синтеза конфигураций ЭВМ. Выделим следующие основные принципы построения и применения САС ИВК: возможность перестройки архитектуры системы в целом, распределенность обработки и памяти, модульность, наращиваемость, непрерывность функционирования, живучесть, многопроцессорность, универсальность, возможность неограниченного накопления и обработки в едином унифицированном формате любых данных и правил, максимальная оперативность обработки потоков информации, адаптивность, самоанализ и активное формирование требований по изменению своих ресурсов и конфигурации. В САС ИВК должны храниться данные и модели, описывающие как специальные задачи, так и возможные конфигурации ЭВМ. Таким образом, САС ИВК может быть отнесена к классу АСОИ. В области исследования АСОИ работали многие специалисты, но результаты этих исследований не являются достаточными для создания САС ИВК.
В третьем разделе проведено формализованное описание основных структур представления данных - СПД - традиционных моделей данных, их анализ, сравнение и обобщение в виде нового формализма пятиуровневой одномерной таблицы представления данных (ОТПД). На едином языке теории множеств описаны и проанализированы СПД: реляционных;
сетевых;
иерархических;
бинарных;
объектно ориентированных;
символьных моделей данных;
модели "сущность-связь" и семантических сетей. Под моделью данных понимают совокупность трех составляющих: СПД, ограничения целостности, операции над данными. Для любой модели данных основную роль играют именно СПД. Существует два простейших способа представления данных: таблицы и графы, поэтому целесообразно выделить графо-табличные СПД, которые и называются в дальнейшем: традиционными. В связи с ограниченным объемом автореферата, рассмотрим здесь только реляционные и сетевые СПД, а также СПД модели данных "сущность-связь".
Реляционная модель данных - это множество нормализованных отношений (таблиц), к которым применимы операции реляционной алгебры. Все данные рассматриваются как хранимые в таблицах, в которых каждая строка имеет один и тот же формат. Выделяют следующие реляционные СПД: имена отношений, имена атрибутов, значения. Пусть A - множество имен отношений:
A={a1,a2,...,ai,...,aI}, (1) ai A Bi = {bi1,bi2,...,biji,...,biJi}, (2) { biji Bi Ciji = ciji 1,ciji 2,...,cijik iji,...,cijiK iji }, (3) где i = 1,I ;
ji = 1,Ji ;
kijj = 1,Kiji, Bi - это множество имен атрибутов отношения ai, Ciji - это множество значений атрибута biji отношения ai. Подчеркнем, что от традиционного описания реляционных СПД формулы 1-3 отличаются большей структурированностью индексов, так как для каждого отношения определяется множество атрибутов, а для каждого атрибута определяется множество значений. В случае необходимости, все элементы однотипных множеств могут быть соответственно объединены в множество имен атрибутов или множество значений.
Однако, для дальнейшего анализа и сравнения СПД целесообразно выделять различные множества, как это и сделано в формулах 2-3.
Сетевая структура данных - это структура данных, представляющая собой ориентированный граф, в любой узел которого может входить более одной связи.
Можно выделить следующие основные сетевые СПД: типы записей, элементы данных типов записей, реализации типов записей, типы наборов-связей, реализации наборов-связей.
Замечание. В связи с ограниченностью количества символов в латинском алфавите и для подчеркивания аналогичных взаимосвязей элементов СПД различных моделей данных будем использовать одинаковые символы для описания исследуемых структур представления данных, но с различной их интерпретацией. С учетом этого замечания, пусть A - множество имен типов записей:
A={a1,a2,...,ai,...,aI}, (4) ai A Bi = {bi1,bi2,...,biji,...,biJi}, (5) { biji Bi Ciji = ciji1,ciji 2,...,cijikiji,...,cijiKiji }, (6) где i = 1, I ;
ji = 1, Ji ;
kijj = 1,Kiji, Bi - это множество имен элементов данных типа записи ai и Ciji - это множество значений элемента данных biji типа записи ai.
Пусть Z - множество имен типов наборов-связей:
Z={z1,z2,...,zl,...,zL}, (7) zl Z Yl = {yl1, yl2,..., ylml,..., ylMl }, (8) zl Z Xl = {xl1, xl2,..., xlnl,..., xlNl }, (9) где l = 1,L ;
ml = 1, Ml ;
nl = 1, Nl и Yl - это множество реализаций записей владельцев набора-связи типа zl и Xl - это множество реализаций записей-членов набора-связи типа zl. При этом, zl Z {< y1ml,xlnl > y1ml Yl, xlnl Xl}.
(10) Модель Чена ("сущность-связь", ER-модель)- это семантическая реляционная модель данных, в основе которой лежит деление реального мира на отдельные различимые сущности, находящиеся в определенных связях друг с другом. Эта модель может рассматриваться как обобщение иерархических и сетевых моделей.
Выделим следующие СПД ER-модели: классы сущностей, множества сущностей, классы (размерности) связей, множества связей, роли сущностей в связях, множество атрибутов, множество значений. Пусть A - множество имен классов сущностей:
A={a1,a2,...,ai,...,aI}, (11) ai A Bi = {bi1,bi2,...,biji,...,biJi}, (12) где i = 1, I ;
ji = 1, Ji и Bi - это множество имен сущностей класса ai. Далее, С={с1,с2,...,сk,...,cK}, (13) где k = 1,K ;
C - множество имен атрибутов. Кроме того, пусть D={d1,d2,...,dl,...,dL}, (14) где l = 1,L ;
D - множество значений. Далее, пусть Z={z1,z2,...,zm,...,zM}, (15) zm Z Ym = {ym1, ym2,..., ymnm,..., ymNm }, (16) где m = 1,M ;
nm = 1, Nm, Z - множество имен классов связей и Ym - множество имен связей класса zm. Рассмотрим описание сущностей, для { biji Bi Ciji = ciji1,ciji 2,...,cijipiji,...,cijiPiji }, (17) cijipiji Ciji Dijipiji ={dij1piji 1,dijipiji 2,...,dijipijirijipij,...,dijipiji Rijipij }, (18) i i где i = 1, I ;
ji = 1, Ji ;
piji = 1, Piji ;
rijipiji = 1, Rijipiji. В модели данных "сущность связь", каждая связь может описываться некоторым набором атрибутов, которые могут иметь определенные множества значений. Другими словами, для { ymnm Ym Cmnm = cmnm1,cmnm 2,...,cmnmsmnm,...,cmnmSmnm }, (19) { cmnmsmnm Cmnm Dmnmsmnm = dmnmsmnm 1,dmnmsmnm 2,..., (20) dmnmsmnmtmnmsmn,...,dmnmsmnmTmnmsmn }, m m где m = 1,M ;
nm = 1, Nm ;
smnm = 1,Smnm ;
tmnmsmnm = 1,Tmnmsmnm.
Пусть, E - это множество имен ролей множеств сущностей в связях, E={e1,e2,...,eu,...,eU}, (21) где u = 1, U. Введем следующее обозначение:
I B = Bi.
(22) i= Итак, каждой связи соответствует некоторый набор двоек, описывающих некоторые сущности и их роли, т.е.:
ymnm Ym {< bmnm 1,emnm 1 >, < bmnm 2,emnm 2 >,..., (23) < bmnm vmnm,emnm vmnm >,...,< bmnmVmnm,emnmVmnm >}, где bmnmvmnm B;
emnmvmnm E;
m = 1,M ;
nm = 1, Nm ;
vmnm = 1, Vmnm.
В объектно-ориентированной базе данных (ООБД) информация хранится в форме объектов, а сама ООБД характеризуется свойствами инкапсуляции, наследования и полиморфизма. Следует особо отметить, что в настоящее время, отсутствуют единые взгляды и стандарты на объектно-ориентированные СПД.
Большинство исследователей БД считает, что ООБД должны сочетать в себе лучшие черты модели "сущность-связь" и реляционных БД. Таким образом, объектно ориентированные СПД, в некотором роде, являются частным случаем СПД модели "сущность-связь".
База данных является неструктурированной, если каждый новый факт о предметной области обладает собственной структурой и схема БД не может быть фиксированной. В том случае, когда в качестве структур выступают кортежи бинарных отношений, а функтор - есть имя бинарного отношения, ассоциативный кортеж может быть интерпретирован семантической сетью, которая, в свою очередь, сама является частным случаем модели данных "сущность-связь". Кроме выше описанных, существует еще достаточно много различных моделей данных (позиционных множеств, активные, временные, графоориентированные, слабоструктурированные, инфологические, концептуальные, плоские, неструктурированные дескрипторные и фреймовые, графовые, формально логические, алгебраические, теоретико-множественные и т.д.), но практически все эти модели данных могут быть сведены к модели данных "сущность-связь". Перейдем к анализу основных СПД традиционных моделей данных. Прежде всего, введем понятие "уровень представления данных".
Определение 1. Если каждому элементу одного множества соответствует некоторое другое множество элементов, тогда будем говорить, что существует двухуровневое представление данных.
Понятие "уровень представления данных" необходимо для сравнительного анализа возможностей по представлению данных СПД различных моделей данных. В общем случае, может существовать N-уровневое представление данных. Отметим, что большее количество уровней представления данных одной модели, говорит и о больших "семантических" возможностях такой модели. Формулы 1 и 2 можно рассматривать, с точки зрения введенного понятия, и как формальное определение двухуровневого представления данных.
В реляционной модели не выделяют специально структуры для представления данных о связях сущностей. Формулы 1, 2 и 3 показывают, что имеет место три уровня представления данных. В сетевой модели анализ формул 4, 5 и 6 показывает, что сетевые СПД о сущностях имеют три уровня. Выделяют следующие сетевые СПД о связях сущностей: типы наборов-связей;
реализации наборов-связей. При этом каждому элементу множества Z из формулы 7 сопоставляется два различных множества, описанных формулами 8 и 9. Такое описание, непосредственно, не соответствует понятию уровня представления данных. В этом случае, можно говорить, что каждому элементу из множества Z соответствует некоторое количество множеств. Каждому такому множеству может быть определенным образом присвоено некоторое имя (идентификатор). Затем, можно рассмотреть некоторое новое множество имен множеств. Получаем, что каждому элементу zl множества Z соответствует некоторое множество Wl - множество имен множеств, которое на самом деле, состоит только из двух элементов, например: Y и X. Далее, каждому элементу wlpl множества Wl соответствует некоторое множество Vlpl.
Следовательно, можно представить формулы 7 - 10 так:
Z={z1,z2,...,zl,...,zL}, (24) zl Z Wl = {wl1,wl2,...,wlpl,...,wlPl}, (25) { wlpl Wl Vlpl = vlpl1, vlpl 2,..., vlplqlpl,..., vlplQlpl }, (26) где l = 1,L ;
pl = 1, Pl ;
qlpl = 1,Qlpl, Wl - это множество имен множеств реализаций записей набора-связи zl и Vlpl - это множество реализаций записей типа wlpl набора связи типа zl. Отметим, что если p=1, то Vlpl = Y1, а если p=2, то Vlpl = X1 ;
где Y1 и X1, берутся в смысле формул 8 и 9. Анализ формул 24 - 26 показывает, что существует 3-уровневое сетевое представление данных о связях сущностей.
В модели данных "сущность-связь" имеют место четырехуровневое представление данных о сущностях и четырехуровневое представление данных о связях сущностей. СПД модели "сущность-связь" являются обобщением и развитием всех традиционных моделей данных. Повышение "семантичности" описания достигается путем введения дополнительного уровня представления данных.
Обобщение основных СПД традиционных моделей данных. С учетом понятия "уровень представления данных" все основные СПД "графо-табличных" моделей данных могут быть описаны в виде одномерных таблиц трехуровневого представления данных (ОТПД-3).
Определение 2. ОТПД-3 - это таблица, предназначенная для хранения данных и состоящая из следующих элементов: заголовок таблицы, заголовки столбцов и клетки таблицы.
Где, "заголовок таблицы" - это некоторая совокупность данных, описывающих всю таблицу, например, ее название, тип, класс, и т.д. "Заголовок столбца" - это некоторая совокупность данных, которая описывает соответствующий столбец клеток ОТПД-3. Каждый столбец ОТПД-3 имеет только один "заголовок столбца". Каждый "заголовок столбца" относится только к одному столбцу. Столбец - это аналог атрибута или элемента данных в соответствующих моделях данных.
"Заголовок столбца" может содержать, например, данные о названии атрибута элемента данных, о формате хранения, о типе данных, и т.д. Отметим, что при таком подходе, столбец данных - это заголовок столбца и совокупность всех соответствующих клеток, относящихся к этому столбцу. Тогда, таблица данных - это заголовок таблицы, совокупность всех заголовков столбцов таблицы и все совокупности клеток всех столбцов данной таблицы. Важно отметить, что, если в реляционных таблицах количество клеток в различных столбцах одной таблицы должно быть одинаковым, то в ОТПД-3 столбцы могут быть разного размера, т.е.
содержать разное количество клеток. "Клетки таблицы" - это некоторая совокупность хранимых данных, которые и образуют "тело" таблицы представления данных, т.е. это, непосредственно, и есть хранимые, накапливаемые данные, организованные в соответствии с заголовками столбцов таблицы. Рассмотрим формализованное описание структур представления данных ОТПД-3. Пусть A - множество имен заголовков таблиц:
A={a1,a2,...,ai,...,aI}, (27) ai A Bi = {bi1,bi2,...,biji,...,biJi}, (28) { } biji Bi Ciji = cij11,ciji 2,...,cijikiji,...,cijiKiji, (29) где i = 1, I ;
ji = 1, Ji ;
kiji = 1,Kiji, Bi - это множество имен заголовков столбцов заголовка таблицы ai и Ciji - это множество значений клеток таблицы заголовка столбца biji заголовка таблицы ai.
Одномерность определяется тем, что после проектирования БД количество таблиц и столбцов в них фиксировано, а добавляются только строки (клетки) таблицы. Таким образом, одномерная таблица трехуровневого представления данных - это не одна таблица, в традиционном понимании, а такое представление данных, которое совмещает три различные таблицы. Первая таблица описывает ОТПД-3 в целом, вторая описывает столбцы ОТПД-3, и только третья таблица содержит хранимые, накапливаемые данные в виде клеток, т.е. строк-записей.
Пятиуровневая одномерная таблица представления данных. Если ввести пятый уровень, называемый "класс таблицы", то это позволит отделять описания объектов от описания связей этих объектов. Пятиуровневые ОТПД (ОТПД-5) позволяют описывать (например, даже для модели "сущность-связь"), как сущности, так и их связи в едином формате (рис. 3), т.е. в виде однотипных таблиц представления данных.
класс ОТПД сущности / связи 1 уровень вид ОТПД класс сущностей / связей 2 уровень заголовок множество сущностей / связей 3 уровень ОТПД заголовки атрибут 1 атрибут 2 атрибут N столбцов сущности / сущности /... сущности / 4 уровень ОТПД связи связи связи значения значения значения сущности / сущности / сущности / клетки ОТПД... 5 уровень связи связи связи 1,1 2,1 N, значения значения значения сущности / сущности / сущности /...
связи связи связи 1,2 2,2 N,............
значения значения значения сущности / сущности / сущности /...
связи связи связи 1,K 2,K N,K Рис. 3. СПД модели "сущность-связь" в формализме ОТПД-5.
Подчеркнем, что числа N и M - фиксированы, а изменяются только числа K и P. ОТПД-5 позволяют в явном виде сохранять отличия связей от объектов, а также различия по категориям типов, по категориям вершин, по классам сущностей, по категориям дуг и по классам связей, соответственно. ОТПД-5 представляют собой обобщение структур представления данных модели "сущность-связь", ООБД, гипертекстовых, "неструктурированных" и многих других СПД.
Итак, приведем полный список элементов ОТПД-5 (таблица 1): класс таблицы, вид таблицы, заголовок таблицы, заголовок столбца, клетки таблицы.
Таблица 1.
Модель Сетевая Бинарная данных Реляционная Иерархическая Семантические № ОТПД-5 модель модель "сущность- модель модель сети данных данных связь" 1 класс ОТПД - - - - - класс категории сущностей;
категория 2 вид ОТПД - - - вершин;
класс типов категории дуг связей множества типы категории;
заголовок сущностей;
записей;
классы вершин;
3 отношения типы записей бинарные ОТПД множества типы дуги отношения связей наборов атрибуты заголовки сущности;
элементы элементы функции 4 столбцов атрибуты - атрибуты данных данных доступа ОТПД связи значения реализации реализации объекты, строки сущности;
типов;
типов;
реализации;
5 значения значения вершины значения реализации реализации реализации ОТПД связи наборов связей отношений Рассмотрим формализованное описание структур представления данных ОТПД-5. Пусть A - множество имен классов таблиц:
A={a1,a2,...,ai,...,aI}, (30) ai A Bi = {bi1,bi2,...,biji,...,biJi}, (31) { } biji Bi Ciji = cij11,ciji 2,...,cijikiji,...,cijiKiji, (32) cijikiji Ciji Dijikiji = dij1kiji 1,dijikiji 2,...,dijikijilijikij,...,dijikijiLijikij, (33) i i dijik iji lijikij Dijik iji Eijik iji lijikij = i i Eijik iji lijikij = eij1k iji lijikij 1,eijik iji lijikij 2,...,eijik iji lijikij mijikij,...
(34) i i i i ilijikiji...,eijikiji lijik iji Mijik iji lijik, iji где i = 1, I ;
ji = 1, Ji ;
kiji = 1,Kiji ;
lijik iji = 1,Lijik iji ;
mijikiji lijik iji = 1,Mijikiji lijik iji, Bi - это множество имен видов таблиц класса таблиц ai, Ciji - это множество имен заголовков таблиц вида таблиц biji класса таблиц ai, Dijikiji - это множество имен заголовков столбцов заголовка таблицы cijikiji вида таблиц biji класса таблиц ai и Eijik iji lijikij - это множество значений клеток таблицы заголовка столбца dijikiji lijikij i i заголовка таблицы cijikiji вида таблиц biji класса таблиц ai.
Таким образом, ОТПД-5 - это обобщение и развитие структур представления данных всех традиционных графо-табличных моделей данных.
Четвертый раздел диссертации посвящен разработке теоретических основ построения многомерного информационного динамического пространства унифицированного представления данных и правил. В этом разделе проанализированы основные возможности нового представления данных, показан переход от ОТПД к многомерному пространству представления данных, проведено сравнение трехуровневых таблиц и трехмерного информационного динамического пространства представления данных, подробно описаны СПД о точках такого пространства и об их отношениях, приведен пример описания данных в многомерном информационном пространстве унифицированного представления данных и правил.
Традиционная графо-табличная концепция представления данных, получившая свое наибольшее развитие в модели данных "сущность-связь", ориентирована на моделирование предметных областей, описываемых в виде изменяющихся данных некоторой фиксированной структуры. Рассмотрим другой подход, основанный на использовании многомерного информационного динамического объектно-системного дискретного пространства унифицированного представления данных и правил.
Существуют различные подходы к решению проблемы описания поведения сложной предметной области или некоторой развивающейся системы. Например, применение "скользящей аксиоматической системы". В кибернетике поведение системы обычно рассматривается в фиксированном пространстве Хi, причем, поведение системы - это изменение ее состояний во времени, исходом которого является некоторый результат. Однако, использование фиксированного пространства состояний не позволяет описать поведение сложной развивающейся системы.
Поэтому для создания моделей развивающихся систем необходимо применять более совершенный аппарат. Например, на основе математической структуры Н. Бурбаки можно синтезировать целый класс различных моделей. В соответствии с работой И.М. Яглома математическая структура Н. Бурбаки - это система:
S=
S(t)=
Будем исходить из того, что реально существует некоторая предметная область, а познающая система изучает и моделирует данную область. Полученные сведения о предметной области накапливаются в некоторой системе представления данных. Для решения этой задачи введем три равнозначных понятия: вещь (объект, сущность), свойство (атрибут, характеристика), отношение (связь, взаимодействие).
Этих трех выделенных понятий-категорий достаточно для представления любой информации о любой предметной области. Рассмотрим некоторое множество V названий вещей. Так как каждое название является уникальным, то количество элементов этого множества будет равно количеству выделенных вещей в рассматриваемой предметной области. Затем, некоторые одинаковые свойства могут быть обнаружены у различных вещей. Тогда можно рассмотреть некоторое множество S названий свойств, состоящее из различных и уникальных названий элементов. Кроме того, существует третье множество O названий отношений, состоящее из уникальных названий выявленных отношений вещей данной предметной области. Итак, можно рассмотреть три различных множества названий:
V, S, О. Известно, что в определенных ситуациях вещь может рассматриваться, как свойство или как отношение;
свойство может рассматриваться, как вещь либо как отношение и отношение может рассматриваться, как вещь или как свойство. Вещь не существует вне свойств и отношений. Точно также, не существует свойств вне вещей и вне отношений, как не существует и отношений вне вещей и вне свойств. Таким образом, будем исходить из того, что некоторое "нечто" может быть и сущностью, и свойством, и отношением, в зависимости от исследуемого предмета и его роли в этом исследовании. Например, понятие "стол" - с одной стороны это сущность, но в некотором смысле это может быть и отношение составных частей: столешницы, ножек, крепежа и т.п. Кроме того, это может рассматриваться даже как свойство, например, "ящик" или "пень" могут иметь свойство, в некоторых ситуациях, "быть столом".
Основной идеей самоорганизующегося подхода является то, что реальный мир существует сам по себе, но при изучении этого мира, в процессе познания, человек (АСОИ) представляет себе описание этого мира в виде трехмерного пространства, осями которого являются понятия: вещь, свойство и отношение. Эти три понятия - абстракции удобные для описания реального мира. Эти абстракции аналогичны трем осям Декартова геометрического пространства, так как это только три разных взгляда на одно объективно существующее "нечто". Три разных и взаимосвязанных точки зрения на одно и тоже "нечто", и позволяют нам выделять из предметной области вещи, свойства и отношения. Эти три абстракции абсолютно равнозначны. Построим трехмерное дискретное информационное пространство:
<вещь, свойство, отношение> (
Наименьший элемент этого пространства (трехмерная точка) - это некоторая конкретная вещь, обладающая некоторым конкретным свойством, находящаяся в некотором конкретном отношении в определенный момент времени и в конкретных географических координатах. При таком подходе, вещь - это уникальное название этой вещи, совокупность всех свойств (атрибутов) этой вещи и значения во всех отношениях этой вещи со всеми другими вещами предметной области. Очень важно, что степень детализации описания вещи может быть различной: от описания всех свойств и отношений до представления лишь сущности вещи. При этом, существует возможность адаптации данных (повышение адекватности), учета времени, географического расположения, системного уровня, и объектных характеристик при объектно-ориентированном подходе. "Физический" смысл "точки", с координатами
Самоорганизующаяся концепция представления данных позволяет: работать с динамическими (эволюционными) структурами хранения данных;
использовать неявные ассоциативные связи различных понятий и объектов (ассоциативный поиск);
вводить понятие меры близости - расстояния либо между отдельными "точками", либо между их совокупностями;
использовать меру подобия, схожести различных структур;
обрабатывать неоднородные данные, организуя связь между ними посредством координат N-мерных точек. Кроме того, правила обработки данных и непосредственно сами данные могут храниться в едином формате.
Самоорганизующееся представление включает в себя идеи объектно ориентированного программирования, более того, оно раскрывает новые возможности и перспективы. Один и тот же объект в разных отношениях может описываться с разной степенью детализации: от одного краткого идентификатора или перечня нескольких наиболее важных характеристик, до полного описания всех свойств и отношений. Кроме того, многомерная информационная концепция открывает новые возможности по созданию информационных систем, работающих в реальном масштабе времени без потери динамики изменения структуры.
Объединение трехмерного пространства
семимерном геометрико-временно-информационном пространстве. Особо отметим, что при необходимости можно вводить дополнительные оси и размерности, а это будет уже: N-мерное самоорганизующееся представление данных. Такой подход позволяет проводить распределенную и параллельную обработку и защиту данных.
Самоорганизующаяся концепция появилась как обобщение и развитие традиционных моделей данных. С точки зрения сетевых моделей, самоорганизующееся представление - это некоторая сеть, находящаяся в координатном трехмерном пространстве, что только расширяет возможности сетевых моделей. С точки зрения реляционных моделей, самоорганизующееся представление - это трехмерная (или N мерная) реляционная таблица, находящаяся в трехмерном пространстве, в которой собраны все обычные реляционные таблицы. Такие таблицы представления данных позволяют эффективно хранить правила и отношения между объектами типа: "многие ко многим" (M:N).
В трехмерном многомерном пространстве представления данных (МППД-3) выделяют элементы следующих четырех типов множеств: заголовки таблиц;
заголовки столбцов;
заголовки строк;
клетки таблицы. При этом, каждым трем элементам из трех различных множеств заголовков может соответствовать только один элемент множества клеток. Рассмотрим формализованное описание МППД-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 всегда существует единственный элемент, принадлежащий множеству С, т.е.:
aiA, bjB, dkD ! cijkC. (41) И наоборот, для любого элемента множества клеток таблиц С существует единственный набор трехмерных координат пространства, т.е.:
cijkC !
Основное отличие МППД-3 от ОТПД-3 заключается в том, что множества заголовков таблиц, столбцов и строк являются независимыми, а, кроме того, появляются элементы четвертого множества - клеток таблицы, в то время как в ОТПД-3 различаются только три типа множеств: заголовки таблиц, заголовки столбцов и строки клеток-записей. Наименьшей адресуемой частью данных при операциях добавления, удаления и изменения в МППД-3 является отдельная клетка таблицы, связанная с тремя соответствующими заголовками, а в ОТПД-3 - целая строка клеток, которые относятся к одной записи реляционной таблицы. Можно сделать вывод о том, что трехуровневые одномерные таблицы представления данных ОТПД-3 являются частным случаем МППД-3.
В общем случае, можно рассматривать: K-мерное подпространство точек и L-мерное подпространство отношений точек, которые образуют: N-мерное самоорганизующееся информационное динамическое пространство унифицированного представления данных и правил, где K+L=N.
Рассмотрим формализованное описание этого N-мерного пространства. Пусть:
A={a1,a2,...,an,...,aN}, (43) где n = 1, N ;
A - множество названий осей самоорганизующегося пространства, N - количество осей (динамическое) самоорганизующегося пространства. Тогда:
an A Bn = {bn1,bn2,...,bnin,...,bnIn}, (44) in = 1,In ;
Bn- множество точек оси an. Для любых допустимых значений координат всегда существует определенная точка многомерного пространства:
i1,i2,...,in,...,iN < i1,i2,...,in,...,iN > I1 I2... In... IN, (45) где < i1,i2,...,in,...,iN > - координаты N-мерной точки.
Существует множество значений точек самоорганизующегося пространства:
C = {ci1i2...in...iN | i1 = 1,I1;
...;
in = 1, In;
...;
iN = 1, IN }.
(46) Для каждой точки самоорганизующегося пространства существует единственное значение из множества значений C:
< i1,i2,...,in,...,iN > ! ci1,i2,...,in,...,iN C.
(47) Отметим, что в многомерном информационном динамическом пространстве могут изменяться не только значения переменных, но и количество осей пространства, т.е. сама структура представления данных. Таким образом, предлагается новый класс моделей данных с изменяемой (эволюционной) структурой представления данных. Такой подход позволяет хранить в едином пространстве и сами данные, и правила их обработки - отношения объектов.
Отметим, что любое отношение также может быть добавлено, удалено или изменено.
В пятом разделе предложены методы обработки данных на основе адаптивной логической сети правил;
адаптивный механизм логического вывода на сети гиперправил с мультиактивизаторами;
квадратичной сложности методы поиска маршрута логического вывода на основе определения минимального разреза многополюсных сетей и линейной сложности матричный метод поиска маршрута логического вывода. Все ограничения целостности традиционных моделей данных могут быть применены для самоорганизующейся модели данных. Более того, если в графо-табличных моделях нельзя накладывать ограничения целостности на части описаний объектов, атрибутов и отношений, то предлагаемые СПД позволяют реализовать ограничения целостности (в том числе и по защите информации) для любых точек информационного пространства, любых их множеств и отношений между ними. Все операции над данными, которые есть в модели "сущность - связь", могут быть реализованы в самоорганизующейся модели данных. Кроме того, предложены новые операции над данными, которые расширяют возможности по адаптивности, универсальности и оперативности обработки информации в АСОИ. Из всех правил (отношений) и заданных (известных) значений формируется логическая сеть вывода (обработки), управляемая потоком данных, которая может быть представлена в виде трех списков: входных переменных, правил и выходных переменных. Списочное представление логической сети позволяет изменить состав и конфигурацию графа. Допустим, что если у правила заданы все входные переменные, то могут быть однозначно определены и все выходные переменные. Таким образом, получаем адаптивную логическую сеть обработки, управляемую потоком входных данных, которая объединяет и обработку известных данных на основе известных правил, и одновременно осуществляет обучение, изменение системы правил со своевременным внесением изменений в соответствующие процессы обработки. Это позволяет непрерывно обрабатывать новые входные переменные и обеспечивает эволюционное, самоорганизующееся развитие АСОИ в целом. Кроме того, такая активная логическая сеть позволяет распараллелить и повысить эффективность обработки потока данных.
"Графовый" поиск маршрута логического вывода основан на использовании теории графов в части построения многополюсных сетей и определения минимального разреза (максимального потока). Данный метод называется "графовым", потому что для поиска маршрута вывода строится граф обработки, с одной стороны от исходных, известных значений, а с другой стороны - от требуемых, искомых значений. Затем осуществляется анализ связности этого графа путем поиска его минимального разреза. Если минимальный разрез больше или равен единице, то решение существует и определяется кратчайший, минимальный путь достижения требуемых результатов, а затем на этой основе непосредственно запускается механизм вывода и обработки данных, что позволит значительно экономить вычислительные ресурсы. Если минимальный разрез равен нулю, то цепочки вывода нет, но можно определить значения каких переменных необходимы для уточняющего запроса, что и является признаком "интерактивности".
Преобразование логической сети правил в многополюсную сеть теории графов осуществляется следующим образом. Выделяют два типа узлов: переменные и процедуры. Переменные преобразуются в узлы-переменные, правила - в узлы процедуры, а их взаимосвязи - в ребра многополюсной сети и получают двудольный ориентированный граф. Затем выделяют две группы узлов-переменных: "входные" и "искомые". Построение многополюсной сети начинают с группы входных переменных, которые образуют полюса этой сети. Искомые переменные образуют другую группу полюсов этой сети. От "входных" полюсов осуществляют постепенное построение многополюсной сети до "искомых" полюсов.
Адаптивный механизм логического вывода на сети гиперправил с мультиактивизаторами, управляемой потоком данных. Одним из наиболее перспективных формализмов представления знаний являются гиперправила с мультиактивизаторами (ГПМ). Существо предлагаемого подхода к построению адаптивного механизма логического вывода на активной эволюционной сети ГПМ, управляемой потоком данных, в том, что из всех возможных ГПМ и известных объектов (активизаторов, переменных) формируется логическая сеть ГПМ.
На ее основе строится двудольный ориентированный граф и на этом графе формируется подграф логического вывода Рис. 4.
(рис. 4). На полученном подграфе выполняется поиск маршрута логического вывода путем анализа его связности.
В теории графов известно достаточно много алгоритмов поиска минимального разреза (или максимального потока) кубической вычислительной сложности и меньше: до О(n2,5) (алгоритм Карив-Арбиб). Рассмотрим квадратичной сложности метод поиска минимального разреза многополюсных сетей. Адаптивную логическую сеть правил можно представить в виде некоторого многоуровневого многотипового динамического графа: G=(V, X), в котором, n- количество вершин.
Граф, в котором выделено S вершин, называют S-полюсной сетью или многополюсной сетью. В данном случае, полюса - это заданные и искомые логические переменные. Разрез - это множество удаляемых вершин и ребер, которое разбивает граф на S компонент по числу полюсов сети, при этом различные полюса находятся в различных компонентах. Рассмотрим случай разреза двухполюсной сети по ребрам. Некоторым образом все вершины нумеруются: первый полюс - 1, а второй полюс - n. Пусть значения всех коэффициентов ребер равны 1. Строим нижнетреугольную матрицу смежности А следующим образом:
1. i,j aij = 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 вершины из разных частей графа принадлежат 3 1 4 1 прямоугольнику, образованному клетками 5 нижнетреугольной матрицы (рис. 5), которые 6 расположены ниже k-той строки и левее (n-k)-того 7 8 1 столбца. Если граф разбит на два компонента, то 9 практически матрица распадается на две подматрицы, 10 1 1 р а соответствующий прямоугольник является нулевым 1 2 3 4 5 6 7 8 9 Рис. 5.
(PRк). Для нахождения минимального разреза в нижнетреугольной матрице необходимо просуммировать все прямоугольники при k от 1 до (n-1), а затем выбрать минимальный, которому и будет соответствовать искомый разрез. Процедура определения суммы:
n 1. PR1 = ai1, где: k=1;
j=1;
i = j + 1,n.
i= n 2. PR2 = PR1 - a21 + ai2, где: k=2.
i= k -1 n 3. PRk = PRk -1 - akj + aik.
j=1 i=k + Из всех PRk выбираем минимальный. Всего определяются суммы для (n-1)-го прямоугольника, при этом выполняется (k-1) 1 p вычитание и (n-k) сложение, т.е. всего (n-1) действий.
2 Получаем сложность: (n-1)2, т.е. О(n2). Особенностью 3 1 данного подхода является то, что для многополюсной 4 1 5 1 p сети строится фактически такая же матрица, в которой 6 по мере связности указаны все вершины и полюса 7 (рис. 6). В полученной матрице ищем разрез 1-го 8 1 9 полюса от всех остальных, который соответствует 10 1 1 p прямоугольникам от 1-го до 2-го полюса. Затем 1 2 3 4 5 6 7 8 9 Рис. 6.
определяем разрез 2-го полюса от всех и так далее. Из всех прямоугольников между соседними полюсами выбираем минимальные и получаем минимальный разрез многополюсной сети по ребрам. Сложность алгоритма даже меньше, чем для двухполюсной сети за счет того, что, определив минимальный прямоугольник, в дальнейшем все операции производят только с оставшейся частью матрицы смежности (снижается размерность).
Линейный матричный метод поиска маршрута логического вывода на сети правил. Суть метода в том, что для некоторой сети правил строится матрица, на основе анализа которой выявляется факт наличия маршрута вывода, определяются возможные маршруты и из этих маршрутов выбирают "кратчайший", наиболее оптимальный по заданным критериям. Пусть известны m - правил и n - переменных.
Тогда в матрице V (n m) представлены все взаимосвязи между правилами и переменными. При этом, входные переменные правила помечаются символом x, выходные - y, "выводимые" переменные - z, а все искомые переменные - w.
В матрицу V добавим одну строку и V 1 2 3 4 5... n-2 n-1 n n+ один столбец для хранения служебной 1 x x x y y информации. Тогда, получаем матрицу V 2 x y y x x размерности (n+1) (m+1), в которой......
отражена вся структура исходной сети m x x x y правил, которая может изменяться m+ (рис. 7). Для поиска маршрута вывода Рис. 7.
производят следующие действия.
1. В строке (m+1) помечают известные z и искомые w переменные.
2. Поиск "запускаемых" правил: если таких правил нет, то - запрос на уточнение входных данных;
если правила есть, то они помечаются в служебной строке.
3. Если "запускаемых" правил несколько, то выбираются такие правила, которые должны быть активизированы в первую очередь.
4. Имитация запуска правила осуществляется путем присваивания выводимым в этом правиле переменным значений "известно" (z).
5. После "запуска" правил анализируют вывод искомых переменных. Если все искомые переменные определены, то успешное завершение работы.
6. Аналогично п. 2 определяют наличие "запускаемых" правил после определения новых значений на предыдущем этапе. Если правил нет, то запрос на дополнительную информацию. Если правила есть, то идут на п.7.
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 x x x y y данных исходных значениях существует.
2 x y y x x Общее количество действий при......
матричном методе определяется суммой m x x x y действий на каждом этапе: присваивание 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).
В шестом разделе рассмотрен метод распараллеливания потокового доступа к общей базе данных в условиях недопущения взаимного искажения одновременно обрабатываемых данных, приведена конвейерная реализация алгоритма функционирования сервера базы данных с потоковым распараллеливанием, исследованы параметры предлагаемых виртуальных потоковых БД, а также проведена оценка быстродействия обработки потока данных различными методами, которая доказала максимальность распараллеливания доступа предлагаемого метода.
Каждому процессу выделим виртуальный образ ресурса БД и организуем централизованное корректное управление, как виртуальными образами, так и самим ресурсом, на основе построения виртуальной потоковой базы данных (ВПБД). В зависимости от времени поступления, все элементы (наборы элементов) входного потока (элементы множества А) и соответствующие им процессы обработки (элементы множества Р) могут быть разделены на: старших (поступивших на обработку ранее) и младших.
Определение 3. Потоковая параллельность обработки БД - это такая обработка элементов входного потока, когда одновременно обрабатываются несколько однотипных по названию переменных, которым присвоены различные значения и при этом выполняется следующее условие: младшие процессы не могут влиять на старшие процессы, а старшие процессы могут вносить такие данные, которые оказывают влияние на младшие процессы.
Для каждого процесса обработки pi требуется некоторый интервал времени inti, необходимый для завершения данного процесса, следовательно, имеет место следующее множество пар: {< pi, inti >}. Интервалы времени обработки различных процессов pi могут различаться: i i :inti inti. Если ti - начало обработки, inti - величина интервала времени обработки, то: (ti + inti ) - время окончания обработки процесса pi. Для любого достаточно длительного интервала времени функционирования АСОИ всегда существует некоторое количество таких i, для которых выполняется следующее:
i : inti > ti+1 - ti. (48) Обеспечение потоковой параллельности обработки БД предоставляет возможность завершения нескольких младших процессов обработки раньше, чем завершится обработка некоторого старшего элемента входного потока:
i : ti+1 > ti;
inti+1 < inti;
ti+1 + inti +1 < ti + inti. (49) Формальная постановка проблемы обеспечения потоковой параллельной обработки БД: необходимо обеспечить такой режим функционирования АСОИ, при котором любой процесс обработки pi, внося изменения в общую базу данных, не влиял бы на обработку старших процессов pi-1, pi-2,..., но одновременно с этим и на этой же общей БД оказывал бы влияние на обработку младших процессов pi+1, pi+2,....
Дано: входной поток {ai } и общая база данных DB.
Требуется: одновременная параллельная обработка следующих процессов {..., pi-2, pi-1, pi, pi+1, pi+2,... }, при которой любой pi может читать и вносить изменения в общую базу данных DB.
При условии, что: изменения вносимые pi не влияют на обработку {..., pi-2, pi-1 }, но влияют на обработку { pi+1, pi+2,... }.
Пусть одновременно в базе данных обрабатываются несколько, например, k - элементов входного потока, при этом k < i: {ai-k, ai-k+1,..., ai-k+j,..., ai-k+(k-1) }. В таком случае, самым старшим процессом является ai-k, который работает непосредственно с реальной БД. Для всех остальных действующих процессов обработки создается общая виртуальная потоковая база данных (ВПБД), в которой для каждого процесса, начиная с pi-k+1 и более младших pi-k+j создается и ведется соответствующая персональная виртуальная потоковая база данных (ПВПБД) vpbdj.
Все изменения, которые процесс pi-k+j должен внести в БД, фиксируются в его ПВПБД vpbdj и тогда {< pi-k + j, vpbdj >}. Таким образом, младшие процессы получают доступ по чтению последовательно через все соответствующие персональные виртуальные потоковые базы данных старших процессов обработки, а все изменения вносятся только в соответствующие ПВПБД. Получаем, что все изменения вносятся в общую БД, но младшие процессы не оказывают никакого влияния на одновременно обрабатываемые старшие процессы. Совокупность всех персональных виртуальных потоковых БД образует единую виртуальную потоковую базу данных.
Допустим, что одновременно могут обрабатываться k процессов, а остальные накапливаются во входной очереди. При поступлении элемента ai на обработку порождается процесс обработки pi. Процесс pi, поступивший на обработку раньше всех других, является самым старшим процессом, а все остальные процессы являются для него младшими. Для каждого pi, кроме самого старшего, создается ПВПБД vpbdj. Как только процесс становится самым старшим, все данные из его ПВПБД переносятся в реальную БД, ресурс ПВПБД высвобождается, а вся дальнейшая обработка этого процесса ведется непосредственно с БД. Будем различать два вида ресурсов обработки: ресурсы УпроцессоровФ - количество одновременно обрабатываемых процессов, задач и т.п., которое зависит от количества процессоров и ресурсы Уоперативной памятиФ - суммарный размер необходимой оперативной памяти для хранения и обработки значений переменных, буферов БД, ключевых файлов и т.п., которые зависят от общедоступной оперативной памяти. Обобщенная схема управления виртуальной потоковой базой данных - ВПБД, обеспечивающая конвейеризацию обработки, показана на рис. 9.
Каждому процессу обработки pi соответствует некоторый Рис. 9.
интервал времени обработки inti.
Процесс обработки состоит из последовательности различных операций, которые представляется целесообразным разделить на два класса:
1) OP - операции без обращения к БД, т.е. только в оперативной памяти;
2) BD - операции, требующие обращения к базе данных.
Введем следующие обозначения: int opiop - интервал времени выполнения одной операции iop первого класса;
и int bdibd - интервал времени выполнения одной операции ibd второго класса. Тогда:
IOP IBD inti = int opiop + int bdibd.
(50) iop=1 ibd= Если обозначить суммарное время обработки процессов от i до i+N через - INT, тогда для обработки в общем случае будет верно, что:
IOPn IBDn N N INT = inti+n = int opiopn + int bdibdn.
(51) n=0 n=0 iopn =1 ibdn = При обычной последовательной обработке интервал времени обработки, обозначаемый как INT1, будет выражаться следующим образом:
IOPn IBDn N N INT1 = int opiopn + int bdibdn.
(52) n=0 iopn =1 n=0 ibdn = При функциональной параллельной обработке в оперативной памяти могут выполняться одновременно несколько операций одного процесса iopn. Введем коэффициент обработки kobrn, который будет зависеть от времени выполнения алгоритмически последовательных операций процесса iopn. Из всех одновременно выполняемых операций, выберем максимальную по времени обработки. Тогда, inti - интервал времени при функциональной параллельной обработке в оперативной памяти процесса обработки будет иметь вид:
IOPn - IBDn 2 kobrn + MAX int opiopn inti = + int bdibdn.
(53) iopn = ibdn = При функциональной параллельной обработке интервал времени обработки, обозначаемый как INT2, будет выражаться следующим образом:
IOPn - IBDn N N kobrn + MAX int opiopn INT2 = + int bdibdn.
(54) iopn = n=0 n=0 ibdn = Перейдем к исследованию параллельной обработки данных, при которой могут выполняться одновременно несколько или даже все операции одного процесса iopn и первого, и второго классов. Аналогично, inti - интервал времени при параллельной обработке данных процесса обработки будет иметь вид:
IOPn -1 IBDn 3 kobrn + MAX int opiopn inti = + MAX intbdibdn.
(55) iopn = 2 ibdn = Сравнивая выражения 50, 53 и 55 приходим к выводу, что 3 inti inti inti. (56) Следовательно, при параллельной обработке данных суммарное время обработки всех процессов от i до i + N, обозначаемое как INT3, будет:
IBDn N 3 IOPn - INT3 =.
(57) kobr + MAX int opiopn + MAX int bdibdn n iopn = 2 ibdn = n= При потоковой параллельной обработке данных одновременно могут выполняться операции первого и второго классов нескольких процессов. Тогда, при потоковой параллельной обработке суммарное время обработки всех процессов от i до i + N, обозначаемое как INT4, будет выражаться:
IOPn -1 IBDn N INT4 = MAXkobrn + MAX int opiopn + MAX int bdibdn.
(58) n=0 iopn = 2 ibdn = Итак, только метод потокового распараллеливания доступа к общей базе данных, основанный на ВПБД, обеспечивает такое быстродействие с минимальной "не возрастающей" (фиксированной) задержкой, которое необходимо для решения задач в режиме времени, близком к реальному.
В седьмом разделе диссертации рассмотрен новый метод повышения быстродействия обработки данных на основе запатентованного линейного способа единично-инкрементного суммирования чисел, который при решении некоторых классов задач позволяет достичь существенного повышения оперативности обработки данных. Там же проанализированы возможности и перспективы использования локальных корректировок вычислений Таблица 2.
и обработки данных;
подведены итоги РАЗРЯДЫ № 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 исследований и показаны перспективы 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 применения самоорганизующихся баз 1. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 данных и правил для адаптивного 3. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4. 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 синтеза комплексов оперативной 5. 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 диагностики.
6. 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 7. 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 Линейный метод единично 8. 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 инкрементного суммирования чисел 9. 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 10. 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 предназначен для решения задачи 11. 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 12. 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 суммирования n-разрядного числа Х с 13. 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 массивом чисел от XA до XB, где:
14. 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 15. 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0XAXBРn. Путем разбиения 16. 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 17. 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 исходного числа на блоки, нового 18. 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 поблочного суммирования (табл. 2), 19. 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 20. 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 анализа и формирования требуемых 21. 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 чисел, линейный метод суммирования 22. 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 23. 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 чисел позволяет уменьшить 24. 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 25. 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 количество операций сложения при 26. 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 Р-ичном суммировании n-разрядного 27. 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 28. 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 числа X с массивом V n-разрядных 29. 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 чисел от 0 до Рn, повысить 30. 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 31. 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 интегральное быстродействие 32. 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 33. 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 суммирования чисел, а также перейти 34. 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 от степенной к линейной зависимости 35. 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 36. 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 общего количества операций сложения от разрядности чисел.
Актуальность разработки линейного метода суммирования чисел определяется тем, что его практическая реализация может привести к существенному сокращению необходимого количества сумматоров в ЭВМ, уменьшению разрядности этих сумматоров и значительному повышению оперативности обработки специальной информации.
Сущность линейного метода суммирования чисел заключается в следующем.
Прежде всего, представляется возможным разбить исходное число на равные группы.
При каждом добавлении единицы, как показано в таблице 2, все основные операции суммирования осуществляются только в первой группе самых младших разрядов чисел. Если нет единицы переноса, которая формируется только при завершении цикла суммирования в группе, то в более старших разрядах ничего не изменяется.
Следовательно, в таком случае суммирование групп старших разрядов можно не производить и сократить требуемое количество операций сложения.
Основной выигрыш предлагаемого метода в том, что при переборном сложении достаточно больших чисел "лишние", т.е. фактически "невыполняемые" операции сложения старших разрядов чисел, алгоритмически блокируются и не выполняются. Проведем оценку временной и емкостной сложности предлагаемого метода на основе определения количества требуемых операций сложения и объема оперативной памяти.
Обозначим количество операций сложения - KS, а ресурсы требуемой оперативной памяти - OP. Для традиционного простого переборного суммирования необходимо выполнить на n-разрядном сумматоре Рn операций сложения. В оперативной памяти необходимо хранить только n-разрядное исходное число X (n) и получаемое n-разрядное число Y (n). Отметим, что требуемый массив {Y}, содержащий Рn чисел, не должен храниться в оперативной памяти. Тогда:
KS0=Pn;
OP0=2n. (59) Общее количество операций сложения KS1 в линейном методе определяют на этапе суммирования как k раз по Рm (m+1)-разрядных операций сложения, где: n=km и m=Const. В оперативной памяти необходимо хранить исходное число X (km), требуемое число Y (km), разбиение числа X на k чисел по m разрядов (km), k массивов Zi по Рm (m+1)-разрядных чисел (k(m+1)Pm) и k блоков формирования числа по m разрядов (km). Пусть Pm/m=Const=a, тогда:
n Pm (60) KS1 = kPm = Pm = n = an ;
m m OP1=4km+k(m+1)Pm km(4+Pm)=(4+Pm)n Pm n. (61) Таким образом, линейный метод суммирования чисел позволяет уменьшить количество операций сложения при полном переборном суммировании, уменьшить разрядность сумматоров, повысить интегральное быстродействие суммирования чисел, а также перейти от степенной к линейной зависимости общего количества операций сложения от разрядности чисел.
Предложены две модификации этого метода: первая позволяет реализовать суммирование на основе специальной таблицы без использования сумматоров;
а вторая - ускорить суммирование и реализовать предложенный метод на ЭВМ с малой (недостаточной) оперативной памятью.
Перспективы и практическая ценность данной диссертационной работы обусловлены тем, что внедрение полученных новых научных результатов позволит:
1) создать самоорганизующиеся программно-аппаратные комплексы оперативной диагностики путем использования интерактивных самоорганизующихся баз данных и правил (рис. 10);
2) уменьшить время решения сложных задач:
Х за счет общего повышения производительности адаптивных ЭВМ относительно традиционных, в среднем за период эксплуатации на половину разности производительности следующих и современных поколений ЭВМ - сейчас на 1,5 порядка (не менее чем в 50 раз) (рис. 11), где:
t P(AF(t))P(Fj);
PCP(AF(tj)) P(Fj)+0,5[P(Fj+1)-P(Fj)];
P P(F3) P(AF(t)) P(F2) P(AF(t)) P(F1) T t1 t2 t3 t Рис. 10. Рис. 11.
Х путем повышения реальной производительности адаптивных ЭВМ более чем в 2 раза, т.е. относительно пиковой мощности с 10-30 % до 50-70 % (рис. 12), где: FK- универсальные, AF - адаптивные, а SFN - специализированные ЭВМ;
3) снизить материально-финансовые затраты и повысить эффективность разработки, эксплуатации и модернизации компьютерных систем (СПАКОД, АСОИ) за счет оптимизации процесса синтеза конфигураций по критерию отношения реальной производительности к стоимости, а также путем постоянного наращивания вычислительной мощности на основе адаптации и добавления только наиболее современных, на каждом этапе существования ЭВМ, компьютерных модулей (рис. 13), где: W - эффективность по критерию отношения реальной производительности к стоимости, AF- адаптивные ЭВМ, FJ и FI - традиционные ЭВМ.
P(%) W W(AF) W(FJ) W(FI) T РАЗРАБОТКА ЭКСПЛУАТАЦИЯ МОДЕРНИЗАЦИЯ 0 FK AF SFN Рис. 12. Рис. 13.
В заключении сформулированы положения, выносимые на защиту, кратко охарактеризованы решенные в диссертации задачи, показана научная новизна диссертации, обоснована достоверность полученных результатов и приведены сведения о практической ценности диссертационной работы.
Внедрение разработанных в этой диссертации: теоретических основ создания интерактивных самоорганизующихся баз данных и правил, принципов построения и применения систем адаптивного синтеза информационно-вычислительных конфигураций и быстродействующих методов обработки информации позволит создать интеллектуальные самоорганизующиеся программно-аппаратные комплексы оперативной диагностики, что имеет важное хозяйственное значение.
ЗАКЛЮЧЕНИЕ В диссертации решена актуальная крупная научная проблема разработки теоретических основ построения СПАКОД путем создания интерактивных самоорганизующихся баз данных и правил, изыскания принципов построения и применения САС ИВК, разработки быстродействующих методов обработки информации. При этом, полученные результаты позволили с единых методологических позиций найти научно-обоснованное решение целому ряду задач по разработке новых моделей данных, принципов адаптивного синтеза ЭВМ и методов обработки информации, что позволило уменьшить время решения уникальных диагностических задач, снизить материально финансовые затраты и повысить эффективность разработки и эксплуатации компьютерных систем.
В диссертационной работе выполнено следующее:
1. Изысканы принципы построения и применения САС ИВК, к которым относятся: адаптивность, модульность, непрерывность, возможность накопления и обработки в унифицированном формате любых данных и правил, максимальная оперативность обработки, формирование требований по изменению своих ресурсов и конфигурации, независимость от конкретных технических средств и открытость системы. Кроме того, для создания САС ИВК предложено применение новой самоорганизующейся модели унифицированного представления и обработки данных.
2. В теории баз данных проведен системный анализ, осуществлено сравнение и обобщение основных структур представления данных традиционных моделей данных, а также доказано, что все традиционные структуры данных могут быть обобщены в виде пятиуровневой одномерной таблицы представления данных.
3. Разработаны теоретические основы создания интерактивных самоорганизующихся баз данных и правил. Впервые созданы эволюционные самоорганизующиеся структуры представления данных, в которых могут изменяться не только значения переменных, но и сама структура представления данных.
Предложено рассмотреть новый класс моделей данных с эволюционной, изменяемой структурой, причем отношения объектов хранятся в том же пространстве и могут представлять собой правила или процедуры обработки. Любое отношение может быть добавлено, удалено или изменено в любое время.
4. Создан метод обработки данных на основе применения интерактивной самоорганизующейся логической сети правил, управляемой потоком данных. Из всех правил и объектов формируется логическая сеть вывода (обработки). В зависимости от имеющихся значений переменных и правил, подграфы обработки-вывода могут динамически изменяться. Интерактивная самоорганизующаяся логическая сеть, управляемая потоком данных, объединяет и обработку известных данных на основе известных правил, и одновременно осуществляет обучение, изменение системы правил со своевременным внесением изменений в соответствующие процессы, что обеспечивает эволюционное развитие всей АСОИ (СПАКОД) в целом. Кроме того, такая логическая сеть позволяет распараллелить обработку потока данных.
5. Для повышения оперативности обработки данных в СПАКОД, разработан быстродействующий метод "графового" поиска маршрута логического вывода путем построения многополюсной сети теории графов и определения ее минимального разреза. Суть этого метода в преобразовании логической сети правил в многополюсную сеть теории графов и поиска ее минимального разреза. Если минимальный разрез равен нулю, то цепочки вывода нет, но можно определить необходимые переменные, что является признаком "интерактивности" обработки данных. Кроме того, разработаны квадратичной сложности методы поиска минимального разреза и линейный матричный метод определения маршрута логического вывода на сети правил. Внедрение этих методов позволило интерактивно формулировать уточняющие запросы и снизить вычислительную сложность поиска маршрута логического вывода до квадратичной (линейной), что повысило оперативность функционирования СПАКОД (АСОИ).
6. На основе построения виртуальных потоковых БД разработан метод распараллеливания потокового множественного доступа к общей базе данных в условиях недопущения взаимного искажения данных. Суть разработанного метода в том, что поступивший на обработку раньше всех процесс работает непосредственно с реальной БД, а для всех остальных действующих процессов создается виртуальная потоковая база данных, в которой для каждого процесса создается и ведется соответствующая персональная база. Все изменения, которые процесс должен внести в БД фиксируются в его персональной базе. Из всех известных способов только потоковая параллельная обработка обеспечивает корректное максимальное распараллеливание множественного доступа к общей базе данных.
7. Разработан линейной сложности метод алгоритмической минимизации необходимого количества устройств и вычислительных процедур сложения для единично-инкрементного суммирования чисел при решении некоторых классов специальных задач. Анализ основных факторов, влияющих на процесс обработки информации, выявил возможность повышения быстродействия ЭВМ при использовании запатентованного способа суммирования чисел, который позволил разработать линейный метод переборного суммирования. Суть этого метода в алгоритмической минимизации количества операций сложения при единично инкрементном суммировании чисел, что приводит к линейной зависимости общего количества операций сложения от разрядности суммируемых чисел.
8. Приведены рекомендации по использованию научных выводов, результаты имитационного моделирования и экспериментальных исследований, выполненных автором в области создания различных автоматизированных систем обработки информации и СПАКОД. Практическая реализация рекомендаций и полученных результатов исследования позволила:
Х разработать теоретические основы построения самоорганизующихся программно-аппаратных комплексов оперативной диагностики;
Х повысить эволюционные и интеллектуальные способности компьютерных систем путем интерактивного формирования запросов и ресурсов для развития в изменяющейся внешней среде;
Х повысить эффективность и оперативность решения сложных задач;
Х оптимизировать создание компьютерных конфигураций по критерию отношения реальной производительности к стоимости;
Х снизить материально-финансовые затраты разработки и эксплуатации компьютерных систем (АСОИ).
9. В диссертации изложены основные результаты по системному анализу моделей данных, синтезу самоорганизующихся баз данных и правил, разработке быстродействующих методов обработки информации, изысканию принципов построения и применения САС ИВК для создания СПАКОД. Предложенные в диссертации новые решения строго аргументированы и критически оценены по сравнению с другими известными решениями.
Таким образом, в диссертации, имеющей теоретическое значение, решена актуальная крупная научная проблема, имеющая важное хозяйственное значение, и приведены рекомендации по использованию научных выводов, которые способствуют развитию экономики и повышению обороноспособности России.
Список основных опубликованных научных работ по теме диссертации:
Монографии 1. Варламов О.О. Эволюционные базы данных и знаний для адаптивного синтеза интеллектуальных систем. Миварное информационное пространство. - М.: Радио и связь, 2002. - 288 с.
2. Амарян М.Р., Варламов О.О. Принципы и методы построения программно-аппаратных комплексов автоматизированных систем управления связью. - М.: ИРИАС, 2003. - 204 с.
Статьи, патент на изобретение, тезисы докладов 3. Пат. RU 2145113 C1 Россия, МКИ 7 G 06 F 7/50. Способ суммирования чисел. / Варламов О.О.
(Россия). - № 98119301/09(021284);
Заявл. 23.10.1998;
Опубл. 27.01.2000. Бюллетень № 3. - 12 с.
4. Варламов О.О. Линейный метод единично-инкрементного суммирования чисел. - М., 2002. - Рус.
- Деп. в ВИНИТИ 19.06.2002 - № 1138.
5. Варламов О.О. Адаптивный механизм логического вывода на эволюционной интерактивной сети ГПМ, управляемой потоком данных. - М., 2002. - Рус. - Деп. в ВИНИТИ 19.06.2002 - № 1139.
6. Варламов О.О. Линейный матричный метод определения маршрута логического вывода на сети правил. - М., 2002. - Рус. - Деп. в ВИНИТИ 19.06.2002 - № 1140.
7. Варламов О.О. Квадратичной сложности методы поиска минимального разреза двухполюсных и многополюсных сетей. - М., 2002. - Рус. - Деп. в ВИНИТИ 19.06.2002 - № 1141.
8. Варламов О.О. Метод распараллеливания потокового множественного доступа к общей БД в условиях недопущения взаимного искажения данных. - М., 2002. - Рус. - Деп. в ВИНИТИ 19.06.2002 - № 1142.
9. Варламов О.О. Разработка адаптивного механизма логического вывода на эволюционной интерактивной сети гиперправил с мультиактивизаторами, управляемой потоком данных // Искусственный интеллект, № 3, 2002. С. 363-370.
10. Варламов О.О. Разработка квадратичной сложности методов поиска минимального разреза двухполюсных и многополюсных сетей // Искусственный интеллект, № 3, 2002. С. 371-375.
11. Варламов О.О., Журавлева Э.М., Чудинов С.М. О моделях документооборота и обучения на основе миварного пространства данных в АСУ регионального оператора связи // Компьюлог, № 5, 2002. С. 39-43.
12. Варламов О.О., Журавлева Э.М., Лысаковский В.А. О защите информации в АСУ регионального оператора связи на основе применения миварных БД и правил // Компьюлог, № 6, 2002. С. 10-16.
13. Варламов О.О. Разработка линейного матричного метода определения маршрута логического вывода на адаптивной сети правил // Известия вузов. Электроника, № 6, 2002. С. 43-51.
14. Варламов О.О. Переборное единично-инкрементное суммирование чисел с линейной вычислительной сложностью // Автоматизация и современные технологии, № 1, 2003. С. 34-40.
15. Варламов О.О. Разработка метода распараллеливания потокового множественного доступа к общей базе данных в условиях недопущения взаимного искажения данных // Информационные технологии, № 1, 2003. С. 20-28.
16. Варламов О.О., Журавлева Э.М., Чудинов С.М., Амарян М.Р. Проблема защиты информации в АСУ регионального оператора // Вестник связи, № 1, 2003. С. 42-48.
17. Варламов О.О., Амарян М.Р. Многомерное изменяющееся представление данных для компаний электросвязи // Вестник связи International, № 1, 2003. С. 23-25.
18. Варламов О.О. Основы многомерного информационного развивающегося (миварного) пространства представления данных и правил // Информационные технологии, № 5, 2003. С. 42 47.
19. Варламов О.О., Амарян М.Р., Лысаковский В.А., Адамова Л.Е. Подход к защите информации в АСУ оператора связи на основе миварных баз данных и правил // Известия ТРТУ, № 4, 2003.
С. 174-175.
20. Варламов О.О., Амарян М.Р., Лысаковский В.А., Адамова Л.Е. Особенности защиты персональных данных и информации в АСУ регионального оператора связи // Известия ТРТУ, № 4, 2003. С. 238-239.
21. Варламов О.О., Амарян М.Р., Лысаковский В.А., Адамова Л.Е. Об одном подходе к созданию ревизоров ОБИ на отдельных компьютерах // Известия ТРТУ, № 4, 2003. С. 175-176.
22. Варламов О.О., Амарян М.Р., Лысаковский В.А., Адамова Л.Е. Подход к защите информации на основе локальных корректировок вычислений и обработки данных // Известия ТРТУ, №4, 2003.
С. 239-240.
23. Варламов О.О., Амарян М.Р., Лысаковский В.А., Адамова Л.Е. Подготовка персонала компаний электросвязи в области информационной безопасности // Известия ТРТУ, №4, 2003. С. 388-389.
24. Варламов О.О., Баранов А.П. Предложения по основным направлениям и путям создания ВВК в России // Тр. международ. науч.-техн. конф. ИМС-99. - Таганрог: Изд-во ТРТУ, 1999. С. 104-105.
25. Варламов О.О. Подход к обеспечению максимального распараллеливания множественного доступа к общей БД в условиях недопущения взаимного искажения используемых данных для ИМС // Тр. международ. науч.-техн. конф. ИМС-99. - Таганрог: Изд-во ТРТУ, 1999. С. 106-107.
26. Варламов О.О. Проблема адаптивного синтеза конфигураций компьютерных систем для решения сложных задач // Науч. сессия МИФИ-2001. Сб. науч. трудов. Т.2. - М.: МИФИ, 2001. С. 228-229.
27. Варламов О.О. Проблема создания эволюционных неоднородных компьютерных систем//Тр. Юб.
науч.-техн. конф. ЦНИИРЭС 12-14 сентября 2001г. Часть 2. - М.: ЦНИИРЭС, 2001. С. 103-105.
28. Варламов О.О. Проблема обеспечения потоковой параллельной обработки баз данных//Тр. Юб.
науч.-техн. конф. ЦНИИРЭС 12-14 сентября 2001г. Часть 2. - М.: ЦНИИРЭС, 2001. С. 106-108.
29. Варламов О.О. Проблема адаптивного синтеза конфигураций интеллектуальных многопроцессорных систем // Тез. докл. Международ. науч. конф. "ИМС-2001". - Таганрог: Изд во ТРТУ, 2001. С. 114-117.
30. Варламов О.О., Адамова Л.Е. Влияние психологических аспектов самоотношения при разработке систем искусственного интеллекта // Тез. докл. Международ. науч. конф. "ИМС-2001".- Таганрог:
Изд-во ТРТУ, 2001. С. 24-27.
31. Варламов О.О., Адамова Л.Е. Обеспечение адаптивности и активности логического вывода на эволюционной сети // Научная сессия МИФИ - 2002. Сб. науч. трудов. Т.2. - М.:МИФИ, 2002.
С. 99-101.
32. Варламов О.О., Адамова Л.Е. Создание эволюционных баз данных и знаний // Научная сессия МИФИ - 2002. Сб. науч. трудов. Т.2. - М.:МИФИ, 2002. С. 101-103.
33. Варламов О.О., Адамова Л.Е. О психологических аспектах моделирования самоотношения интеллектуальных систем на основе эволюционных баз данных и знаний // Тез. докл.
Международ. науч. конф. "ИМС-2002".- Таганрог: Изд-во ТРТУ, 2002. С. 294 - 297.
34. Варламов О.О., Адамова Л.Е. Об одном подходе к моделированию интеллектуальных систем на основе создания адаптивного активного механизма логического вывода на эволюционной сети // Тез. докл. Международ. науч. конф. "ИМС-2002".- Таганрог: Изд-во ТРТУ, 2002. С. 297 - 300.
35. Варламов О.О. О квадратичном методе поиска разреза сети // Тез. докл. Международ. науч. конф.
"ИМС-2002".- Таганрог: Изд-во ТРТУ, 2002. С. 178-180.
Подписано в печать 03.06.2003г. Тираж 100 экз. Участок оперативной печати ГОУ МАРТИТ.
Книги, научные публикации