Оптимизация структур баз данных тема диссертации по экономике, полный текст автореферата
Автореферат
| Ученая степень | кандидат экономических наук |
| Автор | Амана Нахуда Ибрахим |
| Место защиты | Киев |
| Год | 1993 |
| Шифр ВАК РФ | 08.00.13 |
Автореферат диссертации по теме "Оптимизация структур баз данных"
О МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ
к КИЕВСШ1 ГОСУДАРСТВЕИНШ1 ЙКОНШИЧЕСКИЙ УНИВЕРСИТЕТ
на правах рукописи
амана нахуда ибрахим
оптимизация структур баз данных
Специальность 08.00.13. - Экономико-математические
АВТОРЕФЕРАТ диссертация на соискание ученой степени кандидата экономических наук
Киев 1993
Работа выпонена на кафедре информационных систем в ХарБ-копском инженерно-экономическом институте.
.Научный руководитель - Доктор технических наук,профессор
Официальные оппоненты:
Ведущая организация:
Боколугкша Р.Т.
Доктор экономических наук,профессор Суслов О.П.
Кандидат экономических наук,доцент Витлинский В.В.
Главный научно-исследовательский институт по проблемам информатики Министерства экономики Украины
Защита диссертации состоится " " УУИ^_1993 года
часов на заседании Специализированного совета
1С. 0(38.28.05. в Киевском государственном экономическом университете /21)2057,г.Ккев-57, Проспект Победы, 54/1, ауд. 214 /.
С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан " 2^ "_ Л/Ц/ _1993 года.
Учений секретарь Специализированного совета
В.П.Кулагина
i. общая харктешсшса
1.1. Актуальность теш. Одной из важнейших задач любой системы управления является переработка информации. Важную роль в переработке информации призвана сыграть технология создания баз данных. Важнейшим элементом этой технологии является процесс выбора структуры базы данных. Выбор надежного представления такой структуры по тому или иному критерию составляет задачу логического проектирования, решение которой позволит оптимизировать базу данных, что обеспечит эффективность функционирования информационной системы по времени и стоимости.
Постоянный .оиск методов, позволяющих снизить затраты на . стоимость хранения дашшх и их переработку, послужил объективной необходимостью углубления исследований по данным вопросам
и определил актуальность темы диссертационной работы.
1.2. Цель и задачи исследования. Целью диссертационной работы является исследование, разработка методов, агоритмов и. программ решения задач оптимизации структур баз данных и пост-роениеоптимальной логической структуры.
Достижение поставленной цели обеспечивается решением следующих задач:
1. Создание модифицированного метода динамического сгущения.
2. Разработка метода и агоритма исключения нулевых элементов .
3. Построение альтернативного множества.
4. Нахождение локального оптимума.
5. Создание модифицированного метода выбора системы отношений мекду элементами информации.
6. Выделение классов однотипных элементов.
7. Создание метода и агоритма исключения бесперспективных вариантов.
8. Разработка метода и агоритма синтеза оптимальной структуры базы данных.
1.3. Методы исследования. При выпонении данной работы применялись методы исследования операций, векторной оптимизации, кластер-анализа, теории множеств, теории матриц, теории графов.
1.4. Научная новизна результатов исследований:
- разработаны методы: модификация динамического сгущения, исключения нулевых элементов, модификация метода выбора системы отношений между элементами информации, исключения бесперспективных вариантов, векторной оптимизации;
- созданы агоритмы и программы вышеперечисленных методов.
1.5. Практическая значимость. Разработанные методы и агоритмы могут быть использованы для данных, позволяя оптимизировать структуры всех типов данных: иерархических, сетевых, реляционных и структуру представленную в виде гиперграфов.
1.6. Реализация результатов работы. Основные результаты работы использованы текстильным заводом СОТЕМА на Мадагаскаре для перспективного развития информационных систем (свидетельство посольства Республики МадагаскарУЗШШМОЗС/ДГСШ-ТЛ
1.7. Апробация работы. Достоверность полученных результатов и выводов подтверждена расчетом специальных математических критериев, апробащейметодов оптимизации логической структуры баз данных яа тестовых примерах, докладами на учредительной конференции международной ассоциации по нетрадиционным методам оптимизаттии (г. Дивно горек, 16 марта 1992 г.), в Медуна-
родной школе "Проектирование автоматизированных систем контроля и управления сложным объектом" (г.Туапсе 17 сентября 1992 г.), а также регулярно в течение всего периода выпонения исследований на заседаниях семинара "Проблемы экономической кибернетики" Академии наук Украины (г.Харьков, ХИЗИ, кафедра информационных систем), кроме того доклад по теме диссертации 'направляся во Францию на конференцию: 10en,tconinence vitein&Ueaah iuv ('anaCy4t et foptimiia-tion. tfл SyittmM аррго-chii rie^tatitUi) et tmpo-icCb da Syitima de ftnemicrv ифпа, \-U Juin, W2 , SOPHIA-ANTIPOUS (FRWCE)
и был принят экспертной комиссией.
1.8. Пубнкаиии. По теме диссертации опубликовано 3 печатных работы.
1.9. Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, выводов по главам, заключения, списка использованной литературы и трех приложений, 7 рисунков, 8 таблиц. Список литературы включает 124 наименования, из них 9 на иностранных языках.
' 2. СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновываются актуальность теш, выбор предмета исследований, научная новизна и практическая значимость полученных результатов, формулируются основные направления исследований.
Первая глава посвящена критическому анализу некоторых существующих методов оптимизации логической структуры баз данных, а такие сформулированы задачи исследования.
В первых шагах проектирования структур баз данных требуется определение состава информационных массивов. Традицион-
ный метод сортировки массивов требует большого перебора и более того, не устраняет дублирования информации, что приводит к неоптимальной логической структуре базы данных, а значит к ухудшению качества управления.
Информация, подлежащая обработке при решении задач, представляет собой информационный массив о некотором множестве элементов исследуемого объекта. Данные о каждом отдельном элементе такого множества составляют определенную совокупность, которую будем называть информационным модулем (ИМ). Информационный модуль расчленяется на отдельные части, называемые элементарными информационными модулями (ЭИМ) и представляющие собой последовательности символов определенного афавита. Отдельные ЭШ несут законченную смысловую нагрузку, соответствующую качественным и количественным характеристикам элементов объектов, описываемым информационным модулем. Тогда для устранения ранее перечисленных недостаток требуется образовать альтернативные модули наименьшей мощности из всех возможных ском-панованных по исходным данным Ш и ввести оптимизацию этого альтернативного множества согласно соответствующим критериям.
В целях получения набора альтернативных информационных модулей предлагается разработать модифицированный метод динамического сгущения и метод исключения нулевых элементов, целью которых является устранение дублирования информации в покрытии и сникенне затрат на вычисление при работе с разреженной матрицей. Выбор рациональных по составу и количеству альтернативных ИМ осуществляется с помощью метода нахождения локального оптимума.
Все эти предлагаемые разработанные методы направлены на по-высннс качества управления.
Рассмотренный метод приведения отношений к третьей норма-
льной фэрмз затрудняет проектирование подсхем базы данных, поскольку этот метод не учитывает наличие всех решаемых задач. В этой связи, для устранения этого недостатка необходимо применить модифицированный метод выбора системы отношений.
Оценка логической структуры базы данных осуществляется методом многокритериальной оптимизации; компромисным путем, с разработанным методом исключения бесперспективных вариантов.
Во_второй главе разработаны модификация метода динамического сгущения, метод исключения нулевых элементов, применен метод локального оптимума, разработан модифицированный метод выбора системы отношений, сформулирована математическая модель названных методов, применен подход к построению альтернативного множества и приведены результаты действия агоритмов этих методов.
Введем некоторые понятия и обозначения.
Множества элементов, определяющее ИМ, необходимое для решения задач ) обозначим как
Множество непустых подмножеств ...,К) , объеди-
нения которых запоняют 2 , назовем его покрытием 2,' сп свойствами:
Х I. 41 6 { .. ,к] , Р1 Ф0(
Тогда совокупность ^СО. (*С) , попарное пересечение которых со всеми совокупностями ^ (]- , 1Ф}) образует пустые множества, определяет разбиение на классы Р^ <
предельное количество которых равно И , вычисление которого происходит с помощью соответствующего агоритма.
Свойства классов:
I. Р^Р^Р, у Р,.]=(Р>и..иРт)п(РКи...ирг),
2- Чупх.к.г е{],г,...Л}.
Проектирование информационных модулей можно сформулировать как задачу:
- определения рациональных по составу модулей в том смысле, что каждый информационный модуль содержит минимальные избыточные и максимальные необходимые элементарные модули для решения задач;
- определения минимального количества набора информационных модулей.
Данная задача разделена на две подзадачи.
Первая подзадача: образование альтернативных ИМ наименьшей мощности, а вторая - оптимизация этого альтернативного множества.
Для решения первой задачи предлагается применить модифицированный метод динамического сгущения, а вторую задачу предполагается решить с помощью метода нахождения локального оптимума.
Образуем исходную матрицу. Исходные данные, состоящие из
, необходимые для решения задач 2 = могут бы-
ть представлены матрицей информационных потребностей элементы которой Х^* I , если Q.j , и О в противном случае, где - множество ЭИМ, которое необ-
ходимо для решения ZJХ
Как правило, слабозапоненная или разреженная матрица представляет собой матрицу с большим количеством нулей. Для хранения такой матрицы при расчетах потребуются чрезмерные затраты машинного времени и объема памяти.
Разработан метод и агоритм исключения нулевых элементов, которые позвотат значительно снизить стоимость не только хра-
нения информации, но и стоимость затрат на вычисления.
Данный метод предполагает хранить в списке только значения индексов X и j матрицы, с ненулевыми элементами. Таким образом, он позволяет преобразовать исходную матрицу М на список значений индексов ненулевых элементов матрицы М .
Используем процедуру разбиения на классы. Разобьем исходную матрицу на блоки согласно следующих требований, т.е. определяя блоки наименьшей мощности и производя разбиение на минимальное количество блоков. Пусть, в качестве примера, исходная матрица выглядитследующим образом:
гч т* 24 г, 2, г. 2 г9 2,о
Рз 0 г 0 0 0 I 0 I г 0
рь 0 0 0 0 0 0 г 0 , I 0
р? 0 0 0 0 0 0 I I 0 I
р, I 0 I 0 0 I 0 I 0 I
р, 0 I 0 I I 0 I 0 I 0
м.= в I 0 I 0 0 I 0 I 0 I
р9 0 I 0. 0 0 I 0 0 0 I
ъ I 0 I 0 0 I 0 I 0 I
я 0 I 0 I I 0 I 0 I 0
0 I 0 0 I 0 I 0 0 0
Разбиение Р=(Р1,Ц.Р3) множества 2 и а --КО множества Z соответственно находятся по строкам и стобцам матрицы.
Тогда задача состоит в нахождении однородных пар классов ( 'к > ) т.е., либо запоненных единицами, либо нулями, и каждая пара ( , ) классов ассоциируется с банарнш идеальным значением 0 или I.
I. Таким образом, создается бинарная матрица по К строкам и L стобцам-, так называемое ядро, и обозначается как
L = (Qi<) .где пе {0,1} VK'CiCi и U--L ; а[
есть представительство пар классов (Рц.бс)
Уточним понятие идеального значения. Когда в паре классов (PK,Ql) в матрице М( стоит большее количество единиц, чем количество нулей, то Clk = 1 . В противном случае йц-0 .
Исходя из вышеизложенного, суть модифицированного метода динамического сгущения состоит в определении элементов, которые могли бы служить представителями всех пар классов (f\,Qt), элементов всех классов, таких чтобы сумма расстояния от всех пар классов (Рц,Ое) до их представительств была минимальной.
Итак, матёматическая модель модифицированного метода динамического сгущения описывается следующим образом
mtYV(p'Q',L)=IIII(U; "О , (I)
к-i w ^ДЧ'Ц!
где j ГI, если Т.- используем ЭИМ Рг , ' 1о в противном случае
^ il, если пара (К,[) классов запонена единицами ,= ] ш
в противном случае.
Из (I ) можно определить ряд
Пусть две функции g я f соответственно для представительства и назначения.
Функция представительства предназначена для определения ядра или представительств
НЧ, ^Де Ln-(Hn). Функция назначения предназначена для отнесения элементарных информационных модулей либо задач к классу
i Ln-'->Hn . гуе Hn- i(Ln-')
Поскольку из предыдущего представительства 1 определяется следующий класс ЭИМ либо задач Н* =
, то ряд стациони-рует (Мп,ип) и уменьшает значение IV до стационарности. Если будем считать, что ряд стационарный с N порядка, получим:
и/(н
В случае достижения стационаронсти Д/-0 , т.е. с самого начала, можно симметричным образом конструировать разбиение Р" и ядро , которое уменьшает критерий . В этом случае образуется ряд ('Р'1,(3''\ который выпоняет соотношение
МР'Ю": ... (2)
Агоритм модифицированного метода конкретизируется двумя промежуточными этапами. .
Можно выразить функцию IVГР.'с?' IЧ } меры сходства:
. К I ' .
Пусть 1--1
V1 Х ( ,
^ = ,.'^1 и й = СС1И1 , т.е. мощность (?,
Воспользуемся переменной уг , где ^ ,3?. . Это оз-
^г всех единиц в классе. Тогда Л выраяается в таком виде: А = I уг
С Цг , если а? = 0 , поскольку) I *
ИгУм если ={
В этом случае мокно записать:
Р.'а'. I) = I I I | и! - 0 . ^ I - пи а . ( 3 )
и !>;-[)' |> Л' ил
саге! (Рк')
е Ю , ^ ..
Выразим через ук матрицу (, К 0) . Все ядра представляются в виде ЦХ'^Ж.....Оь^О гДе '} Х Необходимо
находить для всех классов элементы , ...
которые минимизируют
' . (4)
Это приводит к нахождению элементов (]ей , которые минимизируют X " С^Сц I,
Р р,ер
Если йк = С , то мы получим
Если С1К * / , тогда
1(цс-^) = 5кСк , , т.е.
мощность .
Таким образом, можно определить значения ядра. Если С1Л - 0 , то суша элементов в (Рк, ближе к нулю и С1ц-1 , если эта сумма приближается к .
В общем виде можно выразить А таким образом
Л-иК-аХ
Пусть **
/Ук.есды Л , Р I.
/1 = 1 , или /4= и,-э^п.ал
Тогда задача состоит в определении бцС^йц классов, которые минимизируют
В результате для нашего примера получим
( 5 ) для всех
2, 2? 25 2,0 2;
Рз I I I
р. I I I
Г Г Г
I I I I I
а I I I I I
р. I I I I I
р, I I I I I
ъ I I I I I
% I ' 0 0 0 I
Ро I I 0 I О
1 о о I
Отметим, что альтернативное множество ИМ представляет собой множество ИМ, полученных с помощью некоторых операций, ' имеющее меньшую мощность по сравнению с первоначальным множеством возможных вариантов ИМ. Для построения альтернативного ИМ, имеется пара снежных классов задач и из матрицы Ма . Пусть 5с - множество ЗИМ покрывающих информационные потребности класса задач , элементный состав которого определяется стобцами матрицы Мг . Каждая пара смежных классов задач порождает некоторые информационные модули., Несколько из них могут быть получены с помощью операции объединения (и) , пересечения (П) , разности (\) и допонения % Х
Используя эти операции, можно выражать одни множества через другие. Тогда пара смежных классов задач порождает ,
Можно выражать через и ЭЛ^е-). Исклю-
чаем в связи с тем, что построение информационных
массивов в виде единого набора ЭИМ приводит к практически поному отсутствию гибкости структуры баз данных.
Такая пара смежных классов задач ,Ое)порождает не-
которое множество ИМ, которые могут быть включены в альтернативное множество:
Таким образом, рассмотренный подход построения множества альтернативных информационных модулей позволяет значительно уменьшить возможные варианты ИМ с до .
Для данного тестового примера Ти . Тогда уменьшение идет от 1024 вариантов ИМ до 5 вариантов. В дальнейшем выбор наилучшего варианта по составу, количеству и качеству ИМ осуществляется из 5 вариантов с помощью метода нахождения локального оптимума, что значительно сокращает затраты на время.
Введем понятие так называемого идеального информационного модуоя, который содержит те и только те элементарные информационные модели, которые необходимы для 2J .
Далее введем величину С^ для оценки ИМ ^ , {7' . Отметим, что Ру определяет ИМ.
Введем следующие величины:
ГГ1> = РУ1'/Р] > ТУ1'"Р]1,/Р} ^ -мощность"^, (необ-
ходимые данные для Zj ), Руу - мощность множества ЭИМ отсутствующих в и необходимых для , - мощность множества лишних для ЭИМ, входящих в состав . Тогда величина Т-* -у',-< -+ Ту./ будет определять оценку отклонения эле-
ментного состава №,1 F/ от идеального ИМ для Zj . Суммарная оценка R' всех задач выражается в виде С,-^,' ~ Tjj1
представляет сумму всех лишних и отсутствющих нужных ЗИМ в j -ом ИМ при решении задач {Zj} .
Тогда задача оптимизации информационных массивов, исходя из указанных выше требований к выделяемым из альтернативного множества Q. , можно выразить требованием минимизации критерия качества cj, .
Итак, математическая модель структуризации информационных массивов можно представить в виде следующей задачи линейного программирования с булевыми переменными
Ф=1С//Х;. (6)
j'-. J J
при ограничетш г
х, Ч, J.
j-'l lJ J .
Из множества выбираем непересекающиеся ИМ, т.е. из
1 ;%; ь<п; 5Лsa' ,
Тогда получим
^'/={{sbsa\s|}, {s,s1\s},{s(\sisrosa>s\s)}} .
Из всех т возможных вариантов ИМ необходимо ввести выбор по
к непересекающимся [Н<т) ИМ для покрытия информационной
потребности. Каждый ИМ имеет информационное качество Су
Пусть множество Х"с{/,,5,..,,m} / 7'"! = к - его мощность.
Тогда задача оптимизации состоит в нахождении Т" так, чтобы
Ф= (T") =Zcrx. -rrnin, (7)
j'-l J J
при ограничениях m
gb^Xj,^, cc ={0,0 Далее, имеется множество T'\ Vj' И 7" . Найдем, если су-
ществует, лучщуто оценку, то есть, если существует |'"е{<ид...,/п}\ 7" , такое, что яучумуту).
Если такой случай проверен, то меняем 7" на Т( = Т"1/{]"]\{]'} и процедуру повторяем до тех пор, пока найдем локальный оптимум.
В результате получим { 5(| Эд \ 5, } . Тогда в состав базы данных входят ИМ {5|( 5г\5, } . Таким образом, метод нахождения локального оптимума позволяет найти набор ИМ, который формирует базу данных с самой минимальной суммой всех лишних и отсутствующих нужных ЭИМ при решении всех задач {2,-}
Для создания логической структуры баз данных кроме необходимых и достаточных используемых элементов всеми решаемыми задачами, надо знать отношения между ними. Выбор системы отношений осуществляется с помощью модифицированного метода выбора системы отношений между элементами информации.
Пусть каждый пользователь декларирует свою систему отношений и'т , где т - номер пользователя и ] - номер задачи / ^ = Т , пг = 1, М / в задаваемом им множестве элементов информации. Причем, среди этих отношений могут быть эквивалентные, независимые и пересекающиеся. Поэтому возникает необходимость анализа исходных информационных структур, представляемых пользователем, с целью их совмещения в единой структуре.
Исходные структуры пользователей можно представлять в виде ориентированных графов. Если каждому элементу 1 ^ и &А5| идентифицировать некоторую вершину графа Х^ , геометрический образ которой на графе будет задан точкой, то совокупность их определенная на графе с помощью отрезвок кривых,
1':;знтифицирует 11] . Они образуют множество отношений Цу 6 Ц Совокупность элементов ИМ 5, , составляют элемен-
ты множества X , которое вместе с множеством II представляют собой граф б (Х,1/) , моделирующий структуру рассматриваемой системы.
Из каждой системы отношений и'т можно образовать
множество декларируемых отношений А'т _ Г j
А т. ~ К ^т
Ориентированные графы ит
(С I ^т/ соответствуют
матрице смежностей II "Р Щ И
( I, если существует ориентированная дуга I /в множестве отношении, соединяющая
Т>?=/ ' с у ;
0 в противном случае.
Эти графы могут быть связными и содержать одни и те же отношения. Поэтому преобразуем исходные графы пользователей следующим образом. ;
Приводим все матрицы II ТуЦ! II к одному размеру и формируем матрицу
того же размера.
j г-1 д ___
Для каждой матрицы II II формируем матрицу ИТ/уН таким образом, чтобы
Т1 = Я-если Х
\_0 в противном случае.
Устраняем транзитивные отношения таким образом. Определим все транзитивные отношения: там, где стоят единицы, ставим нули. Так например, имеются три элемента , , Они формируют такие отношения как (З^ьХ,) (ж,,
Из этих отношений является лишним. Тогда в мат-
рице смежности ставим нуль для (Х] ДОС^) и получим матрицу II II Х Матрица сложности окончательной синтезированной логической структуры БД определяется
Формируем для матрицы также матрицу II
таким образом, чтобы
О в противном случае.
Для всех задач Zj , j=: , условие независимости
описывается следующим образом.
рируемых отношений для всех решаемых задач.
Ли. - некоторая мера независимости множеств отношений, которая может быть задана, исходя из необходимой точности последующих вычислений.
В результате применения таконо модифицированного метода выбора системы отношений получим все отношения, приведенные в табл. I.
Третья глава посвящена выделению классов однотипных элементов, реализации элементарных запросов, разработке метода и агоритма синтеза оптимальной структуры баз данных с помощью метода исключения бесперспективных вариантов, а также постро-
I, если Я^';' > {
Таблица I.
Необходимые и достаточные отношения для создания логической структуры БД фрагментов предметных областей о заработной плате рабочих.
№ отношения Тип отношения Начало отношения Конец отношения Отношения
I 1:1 ТМ По (TN,По)
2 1:1 ти К (ТЫ,К)
3 1:1 тм С (TN,С)
4 1:1 г N12 (IZ.NIZ)
5 1:1 кг (12,KZ)
6 1:1 \г (12,KV)
7 1:М БМ и (SM, и)
8 1:М РФ ВЦ (P,№)
9 1:1 Рю (Fi0,6$)
10 1:1 кг (SM.KZ)
II 1:1 БМ fSM.NV)
12 1:1 \ъ КОР (IZ,!C0P)
13 1:М РЯ к fPR.K)
14 1:1 К \Ы0 (K,woj
15 ЙС (S) ,RCj
16 1:1 \г К2АТ (1Z.KZAT)
17 тъ 31 (N1 Z,S1)
18 1:М с V (C.U)
19 1:1 с Ж 1С.HC)
20 1:1 тм' ЯМ (TN,SM)
21 1:1 г КР (]2,KP>
22 1:1 тт. к (KRZ,K)
23 1:1 1 К РЪ (K.Ptt) '
ению оптимальной логической структуры. В главе показано, что целесообразно шделить классы однотипных элементов, таких, что структуры отношений элементов принадлежат к одному классу. Для этого используется метод динамического сгущения.
Имеется множество 1."' , в состав которого входят элементы базы данных. Образуем два непересекающихся подмножества множества 1! , Ъ и V , мощностью которых являются П атрибутов и р количественных переменных соответственно. Если предположить, что все элементы находятся в матрице X , тогда элементы множества 'Э расположены по Л строкам и элементы множества V по р стобцам.
Хл(х/), 1еъ и ]е\1,
где СС' - значение переменной ] для атрибута (.
Предполагается, что каждому атрибуту приписан некоторый
вес р- , сумма которых равна Р; = \ , где
Я. 'к * е*.
Предположим также, что каждый атрибут I можно представить как точку. Тогда, для атрибута I можно ассоциировать вектор . Множество векторов
с весами р; образуют облако
Предположим, что матрица X , центрированная по стобцам, то есть, сумма элементов каждого стобца равна нулю. В противном случае необходимо ввести преобразование для выпонения этого условия. Это требование получается в результате ,того, что центр тяжести облака N (%*>) находится в начале пространства Я^ . .
Т^сс; =с , У.-еУ.
1,-4, Ь <1
Также для каждой переменной j аналогичным образом ассоциируем ее с вектором л'= (л',..., ) . Множество X1 с весами fy образуют облако M(V)И Rn .
Имеется пространство атрибутов с квадратичной метрикой, определенной диагональной матрицей, где коэффициенты важности Cjj: находятся по диагональной линии. Тогда
В этом выражении могут существовать значения переменной j с разными единицами измерения. Чтобы каждая переменная j сыграла одинаковую роль, необходимо ввести нормализацию коэффициентов важности Ц Х таким образом:
где 6f-X H (Xlf.
J uj itn '
dj - представляет собой дисперсию переменной j
Имеется пространство переменных с весами Ър и метрика. Тогда
' ей 1 ' 1
Введем понятие инерции. Рассмотрим облако из л- точек пространства , причем каждой точке
приписан некоторый вес ик (к - 1,2,..., п) . Инерцией множества (3^, , .,., CC,J вокруг точки й RP называется величина
i(a) = l/uKde(xKia).
Вклад каждой течки в эту инерцию есть !UK с1г(ХК)&).
КС ) гис1г(хи С ) = I /М^.б.) +
+ Хт/*(6-,в), где. в: = I /икд:, /I /ик -
центры тяжести ' к' классов. Эти центры образуют облаки из К' новых объектов, которым соответствуют веса
^ т.у(3' ~ центр тяжести облака (хк},К-
с весами {(^к}, 14= является также центром тяжести
облака (бу] , имеющегося веса {/Пу},]=Х/,К'.
Инерция облака I (6) вокруг центра тяжести также называете^ поной инерцией облака и обозначается Т . Величина (б/ ) есть инерция облака центров тяжести . Ее называют межклассовой инерцией и обозначают 5 . Каждое выражение
б:) пред-
ав' " ' '
ставляет инерцию точек, составляющих класс Су , вокруг центра тяжести этого класса. Суша этих инерции на-
зывается внутриклассовой инерцией и обозначается У^ Уравнение разложения инерции записывается как
Т=№ +6.
Отметим, что метод приводит к минимизации внутриклассовой инерции и наоборот, к максимизации межклассовой инерции.
Определяется инерция облака АП&) по отношению к началу координаты, которая представляет также центр тяжести:
= I р1С1г(ОЛ0-=1н1А^ =
ХГч^'Х
иь ч >
Далее, из исходной матрицы X сформируем новую матрицу, в которой по строкам расположено разбиение множества 'Э на непустые подмножества Р = (Р,,.,., Рл>) на К' классов и по стобцам разбиения множества V на непустые подмножества (3((Зь , на I классов. Элементы матрицы Х(Р,а ) определяются таким образом:
<?') = Хм-АЯХ.щ
С новой матрицей Х(Р ,0 ) связываются некоторое весы И рГЕ;С1; = <.....Ь.
Исходя из ранее изложенного, задача нахождения однотипных_ элементов по классам в системе состоит в нахождении разбиения-
Р' и <?' множеств Э и V соответственно такого, чтобы новая матрица Х(Р,С\) , имеющая весы и (р() ,
потеряла меньше информации, то есть
Таблица 2
Расчет количественных атрибутов
К 2 КР КОЛ И2М 51
I 2 3 4 5 6 7 8
тм 15 8 5 0 0 0 0
Рю 15 0 О 0 0 0 0
к 0 0 0 0 ' 0 0 0
РЯ 0 0 0 0 0 0 0
0 0 0 0 0 0 0
с 1500 1000 40 0 0 0 0
Окончание табл. 2
I 2 3 4 5 6 7 8
и 150 92 40 0 0 0 0
SM 150 92 5 0 0 0 0
WO 0 0 0 0 0 0 0
NC 1500 100 40 0 0 0 0
12 150000 100000 90 3200 30 1500 15
N12 150000 100000 30 3200 30 1500 15
КОР 0 0 0 0 0 0 0
PD 0 0 0 5 0 4 0
ЬЪ 0 0 0 45 0 41 0
Сумма 303330 201292 250 6450 60 Х 3045 30
X 20222 13419,41 16,67 430 4 203 2
Таблица 3.
Результативная таблица.
j i KZAT KOLtl SI R С MV KP KZ
I 2 3 4 5 6 7 8
TN 0,40 0,39 0,39 0,40 0,46 0,39 0,40
Fio 0,40 0,39 0,39 0,40 0,66 0,40 0,40
SM 0,40 0,39 0,39 0,40 0,46 0,39 0,39
С 0,40 0,39 0,39 0,40 -0,92 0,37 0,37
U 0,40 0,39 0,39 0,40 -0,92 0,39 0,39
NC 0,40 0,39 0,39 0,40 -0,92 0 39 0,37
KRZ 0,40 0,39 0,39 0,40 0,66 0,40 0,40
Окончание табл. 3.
I 2 3 4 5 6 7 8
11 -2,55 -2,55 -2,55 -2,55 -2,89 -2,55 -2,55
N12 -2,55 -2,55 -2,55 -2,55 -0,52 -2,55 -2,55
КОР 0,40 0.39 0,39 0,40 0,66 0,40 0,40
РЯ 0,40 0,39 0,39 0,40 0,66 0,40 0,40
1С 0,40 0,39 0,39 0,40 0,66 0,40 0,40
№ 0,40 0,39 0,39 0,40 0,66 0,40 0,40
ва 0,32 0,39 0,39 0,35 0,66 0,40 0,40
I = 0,0000305; ^= 0,0000196; Цг = 0,0000294;
= 0,393580; С}Д = 0,0009204 ; ^= 0,0980581; q6 = 0,0019653 ; 0,1961161.
Тогда все классы однотипных элементов описываются таким образом:
м], Рг'^с.кг^ р3'=[12,К1г,корЗ.
={"РЛ,К,1УО, Р.ьз(ЗМшт.коиъ.БП . ={/?С.^С,КР,К 2].
Реализация элементарных запросов осуществляется следующим образом.
Пусть имеются некоторые множества отношений {А^ ,
необходимые для решения задач }
Тогда проблема состоит в формировании связного подграфа для каждого множества А] , чтобы для любого его элемента существовали пути /дуги/ от 'него к остальным элементам этого множества.
В этой главе разработан метод и агоритм синтеза оптимальной логической структуры базы данных.
Логическая структура представляет собой множество элементов и отношений между ними. Тогда можно представить ее в виде ориентированного графа где X={xt\
L- множество вершин, , j = i m
множество дуг, соединяющих между собой пары вершины. Каждая вершина графа 6 однозначно сопоставляется информаци-
онными элементами определенного типа, каждая дуга jUj связь между двумя какими-либо информационными элементами.
Итак, модель синтеза оптимальной логической структуры БД описывается следующими соотношениями.
Определить множество дуг {^-'т- "О > входящих
в оптимальное решение при минимальной годовой стоимости поиска, хранения и передачи информации к р р п. п.
W= Z I I I I diu X1'* min.
K--L И pl I i -t Ч" 17 '
где а - средняя стоимость обработки одного указателя связи /включает стоимость преобразования ключа в адрес, стоимость поиска, чтения соответствующего элемента информации и передачи информации; j- частота связи (ij'j в
К -ом запросе ; Л!1? - бинарная переменная, используемая
запросами.
I, если дуга (L,j)e 1*Т в K-ом запро-
L 0, в противном случае. Принимая во внимание следующие условия
Ипг. (з +)-, 5 ,
где 3 - минимальная стоимость хранения логической
структуры базы данных ; X - радиус окружности ; /I - искомый параметр.
] < 7 и I поскольку граф ориентирован-
ный и без петель.
Приведенная модель синтеза оптимальной логической структуры БД легко сводится к задаче целочисленного линейного программирования.
Пронумерованы классы и их элементы, полученные в результате действия метода динамического сгущения
I ={1, 2, з}, 2 ={4,5,6,7} , 3 = {8,9,10} , 4 = {11,12,13,14,15} , 5= {16,17,18} , 6 =(19,20,21,22], где ТЫ = I; Рю = 2; 6М = 3;С=4;1У=5 ;Г1С= 6;
= 7; 1 = 8; N 1г = 9; КОР = 10; К = II ; РЯ = 12; МО = 13 ; РО = 14 ; 6 = 15 ; К2Т = 16 ;КОЦ5 = 17 ; 51 = 18 ;КС = 19 = 20 ; РК = КР = 21; КЪ = 22.
Таблица 4.
Частота решения задач.
Ь Zj чу
I 180 6 30
2 150 7 20
3 100 8 10
4 80 9 10
5 50 10 5
В результате действия агоритма синтеза оптимальной логической структуры базы данных получается для нашего примера логическая структура со стоимостью хранения ^ = 960 руб. и суммарной стоимостью поиска и передачи информации М = 10760 руб.
Элементарные запросы реализуются таким образом.
-.{/6,9/, /8,20/, /8,22/, /3,22/, /1,3/, /1,4/,
/1,5/, /1,2/, /1,11/, /1,12/] ;
-{/3,20/, /3,22/, /3,5/, /1,3/, /1,2/, /2,15/, /1,15/, /14,15/};
- { /8,9/, /8,17/, /8,22/, /3,22/, /1,3/, /8,10/,
/1,2/, /10,17/};
- { /8,9/, /9,18/, /16,19/, /8,20/, /3,20/, /1,3/,
/1,11/, /7,11/, /11,14/, /11,12/, /11,13/};
- { /8,9/, /8,16/, /9,18/, /8,19/, /8,18/};
- { /8,9/, /8,20/, /8,21/, /3,21/, /1,3/, /1,2/,
/4,5/, /4,6/, /1,4/, /1,5/};
- { /8,9/, /4,5/, /8,16/, /8,19/, /8,18/, /3,20/,
/3,5/};
- { /8,9/, /8,22/, /1,3/, /1,2/, /1,11/, /1,12/,
/1,13/ } ;
-{/8,9/, /8,16/, /8,20/, /1,3/, /1,2/}; -{/1,4/, /4,6/}.
В этой главе также построена оптимальная логическая структура. Она представлена в виде гиперграфов на рис. I.
Основные выводы.
1. Анализ оптимизации распределения информационных потоков с применением метода сортировки, показывает, что этот метод не позволяет устранить дублирование информации, что приводит к неоптимальной логической структуре баз данных. Для устранения этого недостатка применен модифицированный метод динамического сгущения.
2. Исследование метода динамического сгущения показывает, что он не только не позволяет устранить дублирование информации в покрытии, но и не может найти предельное количество попарных пересечений классов, нужных для нахождения разбиения.
. Модифицированный метод динамического сгущения позволяет устранить эти недостатки.
3. Разработан также метод исключения нулевых элементов, который позволяет снизить стоимость хранения и вычисления.
4. Разработан метод исключения бесперспективных вариантов логической структуры баз данных, который позволяет исключить ненужные варианты логической структуры базы данных.
5. Разработанный метод синтеза логической структуры Иа-зы данных позволяет найти оптимальную логическую структуру базы данных компромиссным путем между суммарной стоимостью поиска и передачей информации, с одной стороны, и стоимостью' хранений логической структуры базы данных, с другой стороны, с минимальными затратами на вычисления.
6. Разработанный модифицированный метод выбора системы отношения учитывает наличие всех решаемых задач, а также позволяет найти логическую структуру базы данных в виде гиперграфа. Такая новая модель базы данных использует ассоциативный метод доступа.
Основные опубликованные работы, отражающие содержание диссертации
1. Воколупова Р.Т., Амана Н.И. Идентификация подструктур баз данных. Сборник научных трудов "Экономические проблемы работы предприятий в новых условиях хозяйствования". -К.: УЖВО, 1988. - С.52-61.
2. Воколупова Р.Г., Амана Н.И. Ыодмфицироиашшй метод динамического сгущения. Материалы докладов учредительной конференции международной ассоциации по нетрадиционным методам оптимизации. - Красноярск: КИКТ, 1992.
3. Воколупова Р.Г., Бузько Я.П., Амана Н.И. Ыетод нахождения локального оптимума. Сборник научных, трудов "Использование математических методов и информационных технологий в технических и экономических системах". - К.: ИК АН Украины,1992.
Похожие диссертации
- Организационно-экономический механизм развития лизинга на предприятиях текстильной промышленности РФ
- Управление развитием научно-технопарковых структур в современной России
- Организационно-экономические основы формирования кадров управления сельскохозяйственных предприятий
- Повышение конкурентоспособности промышленных предприятий на основе инновационных процессов управления качеством продукции
- Организация функционирования пассажирского транспорта в инфраструктуре города