Наши конференции

В данной секции Вы можете ознакомиться с материалами наших конференций

VII МНПК "АЛЬЯНС НАУК: ученый - ученому"

IV МНПК "КАЧЕСТВО ЭКОНОМИЧЕСКОГО РАЗВИТИЯ: глобальные и локальные аспекты"

IV МНПК "Проблемы и пути совершенствования экономического механизма предпринимательской деятельности"

I МНПК «Финансовый механизм решения глобальных проблем: предотвращение экономических кризисов»

VII НПК "Спецпроект: анализ научных исследований"

III МНПК молодых ученых и студентов "Стратегия экономического развития стран в условиях глобализации"(17-18 февраля 2012г.)

Региональный научный семинар "Бизнес-планы проектов инвестиционного развития Днепропетровщины в ходе подготовки Евро-2012" (17 апреля 2012г.)

II Всеукраинская НПК "Актуальные проблемы преподавания иностранных языков для профессионального общения" (6-7 апреля 2012г.)

МС НПК "Инновационное развитие государства: проблемы и перспективы глазам молодых ученых" (5-6 апреля 2012г.)

I Международная научно-практическая Интернет-конференция «Актуальные вопросы повышения конкурентоспособности государства, бизнеса и образования в современных экономических условиях»(Полтава, 14?15 февраля 2013г.)

I Международная научно-практическая конференция «Лингвокогнитология и языковые структуры» (Днепропетровск, 14-15 февраля 2013г.)

Региональная научно-методическая конференция для студентов, аспирантов, молодых учёных «Язык и мир: современные тенденции преподавания иностранных языков в высшей школе» (Днепродзержинск, 20-21 февраля 2013г.)

IV Международная научно-практическая конференция молодых ученых и студентов «Стратегия экономического развития стран в условиях глобализации» (Днепропетровск, 15-16 марта 2013г.)

VIII Международная научно-практическая Интернет-конференция «Альянс наук: ученый – ученому» (28–29 марта 2013г.)

Региональная студенческая научно-практическая конференция «Актуальные исследования в сфере социально-экономических, технических и естественных наук и новейших технологий» (Днепропетровск, 4?5 апреля 2013г.)

V Международная научно-практическая конференция «Проблемы и пути совершенствования экономического механизма предпринимательской деятельности» (Желтые Воды, 4?5 апреля 2013г.)

Всеукраинская научно-практическая конференция «Научно-методические подходы к преподаванию управленческих дисциплин в контексте требований рынка труда» (Днепропетровск, 11-12 апреля 2013г.)

VІ Всеукраинская научно-методическая конференция «Восточные славяне: история, язык, культура, перевод» (Днепродзержинск, 17-18 апреля 2013г.)

VIII Международная научно-практическая Интернет-конференция «Спецпроект: анализ научных исследований» (30–31 мая 2013г.)

Всеукраинская научно-практическая конференция «Актуальные проблемы преподавания иностранных языков для профессионального общения» (Днепропетровск, 7–8 июня 2013г.)

V Международная научно-практическая Интернет-конференция «Качество экономического развития: глобальные и локальные аспекты» (17–18 июня 2013г.)

IX Международная научно-практическая конференция «Наука в информационном пространстве» (10–11 октября 2013г.)

V Международная научно-практическая конференция "Наука в информационном пространстве" (30-31 октября 2009 г .)

К.т.н. Шичкина Ю.А.

Братский государственный университет, Российская Федерация

ОТ МЕТОДА НЕОГРАНИЧЕННОГО ХАОСА К МАТРИЧНОМУ МЕТОДУ ОПТИМИЗАЦИИ РЕЛЯЦИОННЫХ МОДЕЛЕЙ БАЗ ДАННЫХ

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

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

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

2. Аномалия изменения – один и тот же фрагмент данных изменяется в одном кортеже, но остается нетронутым в другом.

3. Аномалия удаления – удаление какого-то фрагмента приводит к потере целого кортежа.

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

Качество проектируемой схемы отношения позволяет улучшить анализ зависимостей одних атрибутов от других. Анализ схемы на наличие аномалий избыточности проводится с помощью функциональных зависимостей. К сожалению, этот процесс – оптимизации схемы отношения – на сегодняшний день является единственным неавтоматизированным этапом в проектировании баз данных. Большинство проектировщиков баз данных этот этап просто пропускают, другие тратят достаточно много времени на исследование функциональных зависимостей, больше полагаясь на свой опыт и интуицию, чем на математический аппарат. В то же время существуют инструментарий в области математики, который позволяет не только формализовать этот этап, но и выстроить алгоритм, с одной стороны, обеспечивающий нахождение оптимального решения задачи сведения к минимуму аномалии избыточности, с другой стороны, позволяющий переложить решение этой задачи на «плечи» компьютера, тем самым, сделав процесс создания базы данных автоматизированным на всех этапах проектирования: от построения ER -модели (например, в ERWin ) до создания физической базы данных на SQL -сервере.

Метод ограниченного хаоса

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

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

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

1 ) существенно ускорить поиск нужного объекта в группе объектов;

2 ) увеличить достоверность информации (в частности, снизить вероятность появления объектов-близнецов);

3 ) сделать заполненность групп этой классификации элементом анализа системы и ее текущего состояния.

Основной характерной чертой онтологического анализа является, в частности, разделение реального мира на классы объектов (at its joints) и определение их онтологий, или же совокупности фундаментальных свойств, которые определяют их изменения и поведение.

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

Формализация метода с помощью теории графов

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

Теория графов достаточно хорошо развита, однако прямое ее применение для представления данных до сих пор встречало затруднения, вызванные следующими обстоятельствами:

1) связи в моделях представления данных относительно просты, матрицы смежности получаются разреженными, что снижает ценность их использования;

2) в графах отражается чаще всего один тип связи (например, 1:1);

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

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

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

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

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

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

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

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

Таким образом, несвязный подграф представляет собой совокупность отдельных частей (подграфов), называемых компонентами k(G). Каждая такая компонента представляется своей матрицей смежности Формула , а общая матрица смежности Формула несвязного графа (при соответствующей группировке его вершин и ребер) имеет блочную диагональную (квазидиагональную) форму:

Формула

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

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

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

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

Всего в реляционной теории насчитывается 6 нормальный форм: 1 NF , 2 NF , 3 NF , BCNF (нормальная форма Бойса-Кодда), 4 NF , 5 NF . Каждое из последующих правил ( NF ) дополняет предыдущее (что собственно, и позволяет разбить процесс преобразования исходной БД к нормальной форме на этапы и производить его однократно, не возвращаясь к предыдущим этапам).

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

Алгоритм декомпозиции отношения

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

Алгоритм

1. Провести стягивание подграфов в деревья.

2. Найти все узлы, удовлетворяющие всем трем правилам точки декомпозиции. Допустим это узлы Формула и Формула .

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

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

5. Из орграфа удалить:

a) все узлы-потомки точки декомпозиции;

b) все дуги, исходящие из точки декомпозиции.

Точку декомпозиции и все дуги, входящие в нее остаются в орграфе.

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

7. Повторить алгоритм для второго отношения.

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

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

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

Граф можно представить матрицей смежности. Строки и столбцы этой матрицы соответствуют вершинам графа, а ее Формула - элемент равен 1, если вершины Формула и Формула являются смежными (или если вершина Формула является концом дуги, соединяющей вершины Формула и Формула в орграфе).

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

1. Провести стягивание строк.

a) Найти строку Формула , содержащую всего одну единицу.

b) Определить столбец Формула , в котором находится эта единица.

c) Если в столбце Формула больше нет единиц, то логически прибавить ее к строке или строкам, содержащим атрибут с именем равным имени столбца Формула .

d) Удалить i -ю строку из матрицы A . Удалить элемент Формула из матрицы S . Повторить эти шаги для каждой строки с единственной единицей.

2. Найти строку, содержащую единицы только в тех столбцах, имена которых отсутствуют среди элементов массива S . Если такой строки нет, перейти к шагу 6.

3. Включить в новое отношение все атрибуты, соответствующие столбцам с единицами в найденной строке и атрибуты, соответствующие этой строке.

4. Удалить из матрицы столбцы с единицами в найденной строке и саму строку.

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

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

Заключение

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

Список литературы:

1. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 1088с.

2. Риккарди Г. Системы баз данных. Теория и практика использования в Internet и среде Java.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 480с.