№ 6 УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА УДК 004.05 НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ МЕТОДОМ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ 2011 г. И.В. Клименко Ростовский государственный университет путей сообщения Rostov State Transport University Предложен процесс нормализации реляционной модели, основанный на наличии зависимостей между атрибутами исходных отношений,который позволяет снизить избыточность (дублирование) хранимых данных, а следовательно, устранить аномалии добавления, обновления и удаления хранимых записей. <...> Безызбыточные файлы баз данных занимают меньше места на внешних носителях и требуют меньше времени при обработке информационных запросов пользователей базы данных. <...> Формализованный метод нормализации отношений реляционной модели позволяет достичь третьей нормальной формы и оптимизировать и автоматизировать процесс нормализации. <...> Ключевые слова: нормализация отношений реляционной модели; нормальные формы; задача о наименьшем покрытии; первичный ключ; функциональные зависимости. <...> В современной теории баз данных наиболее актуальной считается задача нормализации отношений реляционной модели, так как до настоящего времени не является формализованной. <...> В большинстве фундаментальных трудов отмечается достаточность и целесообразность целям практики достижения третьей нормальной формы (3НФ). <...> Отношение БД находится в 3НФ относительно множества функциональных зависимостей F, если оно удовлетворяет условиям 1НФ и ни один из непервичных атрибутов не является транзитивно зависимым от ключа. <...> Для формализации процесса нормализации отношений реляционной модели можно использовать методы целочисленного программирования и, в частности, задачи о наименьшем покрытии. <...> Так, при анализе определения 3НФ сделан вывод, что целью такой нормализации является устранение транзитивных зависимостей между атрибутами. <...> Пусть дан граф G(X, F), где Х – множество атрибутов интересующей нас предметной области, F – множество <...>