Реляционная структура базы данных

ИНФОРМАТИКА И ЯЗЫКИ ПРОГРАММИРОВАНИЯ

Часть I

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

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

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

· указание последовательности выполнения технологических операций;

· перечисление условий, при которых выполняется та или иная операция;

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

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

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

Жизненный цикл программного обеспечения (ПО) — период времени, который начинается с момента принятия решения о необходимости создания программного продукта и заканчивается в момент его полного изъятия из эксплуатации. Этот цикл — процесс построения и развития ПО.

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

· анализ требований,

· проектирование,

· кодирование (программирование),

· тестирование и отладка,

· эксплуатация и сопровождение.

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

В коммерческом программном обеспечении жизненный цикл определяется моментом начала его продаж.

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

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

а) изменению программного продукта и услуг,

б) изменению цены на них,

в) проведению модификации или снятию с продажи и предоставления.

Графическая модель жизненного цикла продукта или услуги, предложенная зарубежными специалистами в 1991 году, приведена на рис. 1.

Рис. 1. Графическая модель жизненного цикла продуктов и услуг.

Обычно, под термином “программный продукт” для компьютерных информационных технологий принято понимать необходимое им программное обеспечение (ПО).

Основной нормативный документ, регламентирующий ЖЦ ПО – международный стандарт ISO/IEC 12207 (ISO, International Organization of Standardization – Международная организация по стандартизации, IEC, International Electrotechnical Commission – Международная комиссия по электротехнике). Он определяет структуру ЖЦ, содержащую процессы, действия и задачи, выполняемые во время создания ПО.

Согласно этому стандарту, структура ЖЦ ПО базируется на трёх группах процессов:

1) основные процессы ЖЦ ПО (приобретение, поставка, разработка, эксплуатация, сопровождение);

2) вспомогательные процессы (документирование, управление конфигурацией, обеспечение качества, верификация, аттестация, оценка, аудит, решение проблем);

3) организационные процессы (управление проектами, создание инфраструктуры проекта, определение, оценка и улучшение самого ЖЦ, обучение).

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

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

Управление проектом связано с вопросами планирования и организации работ, создания коллективов разработчиков; контроля за сроками и качеством выполняемых работ.

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

Обеспечение качества проекта связано с проблемами верификации, проверки и тестирования ПО.

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

Оценка качества (ГОСТ 28195-89) осуществляется на всех этапах жизненного цикла программных средств (ПС) при:

· планировании показателей качества ПС;

· контроле качества на отдельных этапах разработки (техническое задание, технический проект, рабочий проект);

· контроле качества в процессе производства ПС;

· проверке эффективности модификации ПС в процессе сопровождения.

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

Под тестированием понимается процесс исполнения программы с целью обнаружения ошибок.

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

Управление конфигурацией – один из вспомогательных процессов, поддерживающих основные процессы жизненного цикла ПО, прежде всего процессы разработки и сопровождения ПО ИС.

Управление конфигурацией позволяет организовать, систематически учитывать и контролировать внесение изменений в ПО на всех стадиях ЖЦ. Общие принципы и рекомендации конфигурационного учёта, планирования и управления конфигурациями ПО отражены в проекте стандарта ISO/IEC 12207.

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

Одним из базовых понятий проектирования ИС является понятие жизненного цикла её программного обеспечения (ЖЦ ПО) – это непрерывный процесс, начинающийся с момента принятия решения о необходимости создания ПО и заканчивается в момент его полного изъятия из эксплуатации.

ИС входят в состав СУБД и являются специфическим инструментальным и прикладным (пользовательским) программным обеспечением.

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

Анализ требований — это процесс сбора требований к программному обеспечению (ПО), их систематизации, документирования, анализа, выявления противоречий, неполноты, разрешения конфликтов в процессе разработки программного обеспечения. В англоязычной среде также говорят о дисциплине «инженерия требований» (англ. Requirements Engineering). В процессе сбора требований важно принимать во внимание возможные противоречия требований различных заинтересованных лиц, таких как заказчики, разработчики или пользователи.

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

Анализ требований включает три типа деятельности:

· Сбор требований: общение с клиентами и пользователями, чтобы определить, каковы их требования.

· Анализ требований: определение, являются ли собранные требования неясными, неполными, неоднозначными, или противоречащими, и затем решение этих проблем.

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

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

Модульное проектирование основано на понятии модуля - логически взаимосвязанной совокупности функциональных элементов, оформленных в виде отдельных программных модулей.

Модуль характеризуют:

· один вход и один выход - на входе программный модуль получает определенный набор исходных данных, выполняет содержательную обработку и возвращает один набор результатных данных, т.е. реализуется стандартный принцип IPO (Input - Process - Output) - вход-процесс-выход;

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

· логическая независимость - результат работы программного модуля зависит только от исходных данных, но не зависит от работы других модулей;

· слабые информационные связи с другими программными модулями - обмен информацией между модулями должен быть по возможности минимизирован;

· обозримый по размеру и сложности программный элемент.

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

Каждый модуль состоит из спецификации и тела. Спецификации определяют правила использования модуля, а тело - способ реализации процесса обработки.

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

· каждый модуль вызывается на выполнение вышестоящим модулем и, закончив работу, возвращает управление вызвавшему его модулю;

· принятие основных решений в алгоритме выносится на максимально "высокий" по иерархии уровень;

· для использования одной и той же функции в разных местах алгоритма создается один модуль, который вызывается на выполнение по мере необходимости. В результате дальнейшей детализации алгоритма создается функционально-модульная схема (ФМС) алгоритма приложения, которая является основой для программирования.

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

В любой типовой структуре блок, кроме условного, имеет только один вход и выход, безусловный переход на блок с нарушением иерархии запрещен (оператор типа GoTo в структурном программировании не используется).

Виды основных управляющих структур алгоритма приведены в табл

Типы управляющей структуры	Применение управляющей структуры
Последовательность Блок 1 Блок 2 Конец	Последовательность включает фиксированный перечень блоков (операторов). Каждый очередной блок обрабатывается после завершения предыдущего без дополнительных условий. Для изменения порядка обработки блоков редактируется последовательность выполняемых
Альтернатива (условие выбора) Начало Да Условие Нет Альтернатива1 Альтернатива2 Конец	В блоке Условие содержится условие выбора альтернативы обработки. Каждая альтернатива выполняется 1 раз; выполнение одной из двух альтернатив - обязательно. Развитие данного типа структуры является множественная альтернатива, когда последовательно проверяются условия выполнения определенных альтернатив. Если очередное условие истинно, обрабатывается соответствующая ему альтернатива, после чего происходит выход. В противном случае - переход к проверке условия следующей альтернативы. Если ни одно из условий не выполнилось, происходит выход.
Цикл ("пока") Начало Условие Нет Да Тело цикла Конец	В блоке Условие задается условие тела цикла - определенной обработки. Если условие не выполняется, цикл прерывается и осуществляется выход. Условие может содержать счетчик повторений тела цикла либо логическое условие. Тело цикла - произвольная последовательность блоков (операторов) обработки

Коди́рование — процесс написания программного кода, скриптов, с целью реализации определённого алгоритма на определённом языке программирования.

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

В узких кругах кодирование также может называться «кодинг» (англ. coding). Однако в литературе этот термин используется редко.

“Тестирование — процесс, подтверждающий правильность программы и демонстрирующий, что ошибок в программе нет.” Основной недостаток подобного определения заключается в том, что оно совершенно неправильно; фактически это почти определение антонима слова “тестирование”. Читатель с некоторым опытом программирования уже, вероятно, понимает, что невозможно продемонстрировать отсутствие ошибок в программе. Поэтому определение описывает невыполнимую задачу, а так как тестирование зачастую все же выполняется с успехом, по крайней мере с некоторым успехом, то такое определение логически некорректно. Правильное определение тестирования таково: Тестирование — процесс выполнения программы с намерением найти ошибки.

Тестирование модуля, или автономное тестирование (module testing, unit testing) — контроль отдельного программного модуля, обычно в изолированной среде (т. е. изолированно от всех остальных модулей). Тестирование модуля иногда включает также математическое доказательство.

Тестирование сопряжении (integration testing) — контроль сопряжении между частями системы (модулями, компонентами, подсистемами).

Тестирование внешних функций (external function testing) — контроль внешнего поведения системы, определенного внешними спецификациями.

Комплексное тестирование (system testing) — контроль и/или испытание системы по отношению к исходным целям. Комплексное тестирование является процессом контроля, если оно выполняется в моделируемой среде, и процессом испытания, если выполняется в среде реальной, жизненной.

Тестирование приемлемости (acceptance testing) — проверка соответствия программы требованиям пользователя.

Тестирование настройки (installation testing) — проверка соответствия каждого конкретного варианта установки системы с целью выявить любые ошибки, возникшие в процессе настройки системы.

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

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

Сопровождаемость программного обеспечения — характеристики программного продукта, позволяющие минимизировать усилия по внесению в него изменений:

· для устранения ошибок;

· для модификации в соответствии с изменяющимися потребностями пользователей.

Объектно-ориентированное программирование. Основные понятия и принципы. Наследование, инкапсуляция и полиморфизм.

Объе́ктно-ориенти́рованное, или объектное, программи́рование (ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов. В случае языков с прототипированием вместо классов используются объекты-прототипы.

Основные понятия

Абстракция

Абстрагирование — это способ выделить набор значимых характеристик объекта, исключая из рассмотрения незначимые. Соответственно, абстракция — это набор всех таких характеристик.

Инкапсуляция

Инкапсуляция — это свойство системы, позволяющее объединить данные и методы, работающие с ними, в классе и скрыть детали реализации от пользователя.

Класс

Класс является описываемой на языке терминологии (пространства имён) исходного кода моделью ещё не существующей сущности (объекта). Фактически он описывает устройство объекта, являясь своего рода чертежом. Говорят, что объект — это экземпляр класса. При этом в некоторых исполняющих системах класс также может представляться некоторым объектом при выполнении программы посредством динамической идентификации типа данных. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.

Наследование

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

Объект

Сущность в адресном пространстве вычислительной системы, появляющаяся при создании экземпляра класса или копирования прототипа (например, после запуска результатов компиляции и связывания исходного кода на выполнение).

Полиморфизм

Полиморфизм — это свойство системы использовать объекты с одинаковым интерфейсом без информации о типе и внутренней структуре объекта.

Прототип

Прототип — это объект-образец, по образу и подобию которого создаются другие объекты. Объекты-копии могут сохранять связь с родительским объектом, автоматически наследуя изменения в прототипе; эта особенность определяется в рамках конкретного языка.

В центре ООП находится понятие объекта. Объект — это сущность которой можно посылать сообщения, и которая может на них реагировать, используя свои данные. Данные объекта скрыты от остальной программы. Сокрытие данных называется инкапсуляцией.

Наличие инкапсуляции достаточно для объектности языка программирования, но ещё не означает его объектной ориентированности — для этого требуется наличие наследования.

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

Язык Self, соблюдая многие исходные положения объектно-ориентированного программирования, ввёл альтернативное классам понятие прототипа, положив начало прототипному программированию, считающемуся подвидом объектного.

Реляционные базы данных. Нормальные формы. Таблицы. Основные операции над таблицами. Разрешение коллизии.

База данных - набор сведений, хранящихся некоторым упорядоченным способом. Можно сравнить базу данных со шкафом, в котором хранятся документы. Иными словами, база данных - это хранилище данных. Сами по себе базы данных не представляли бы интереса, если бы не было систем управления базами данных (СУБД).

Система управления базами данных - это совокупность языковых и программных средств, которая осуществляет доступ к данным, позволяет их создавать, менять и удалять, обеспечивает безопасность данных и т.д. В общем СУБД - это система, позволяющая создавать базы данных и манипулировать сведениями из них. А осуществляет этот доступ к данным СУБД посредством специального языка - SQL.

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

Реляционная структура базы данных

Все данные представлены в виде простых таблиц, разбитых на строки и столбцы, на пересечении которых расположены данные.

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

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

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

В теории реляционных БД обычно выделяют следующие нормальные формы:

первая нормальная форма (1NF);

· вторая нормальная форма (2NF);

· третья нормальная форма (3NF);

· нормальная форма Байса-Кодда (BCNF);

· четвертая нормальная форма (4NF);

· пятая нормальная форма или форма проекции - соединения (5NF или PYNF).

Основные свойства нормальных форм:

· каждая следующая нормальная форма в некотором смысле лучше предыдущей;

· при переходе к следующей нормальной форме свойства предыдущих нормальных свойств сохраняются.

Схемы БД называются эквивалентными, если содержание исходной БД можно получить естественным соединением отношений, входящих в результирующую схему, и при этом не появляется новых кортежей в исходной БД.

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

· Аномалии вставки (INSERT) – хранение в одном отношении разнородной информации.

· Аномалии обновления (UPDATE) –избыточность данных отношения из-за хранения разнородной.

· Аномалии удаления (DELETE) – хранение разнородной информации в одном отношении.

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

Нормализация – разбиение таблицы на несколько, которые обладают лучшими свойствами при обновлении, вставке и удалении данных. Т.е. нормализация представляет собой процесс последовательной замены таблицы ее полными декомпозициями до тех пор, пока все они не будут находиться в 5НФ, однако, на практике достаточно привести таблицы к НФБК.

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

Если заменить на время нормализации коды первичных (внешних) ключей, то следует рассмотреть 2 случая:

1. Таблица имеет составной первичный ключ, например и поле , которое функционально зависит от части этого ключа, например, от (от полного ключа не зависит). Рекомендуется сформировать другую таблицу, содержащую и ( – первичный ключ), и удалить из первоначальной таблицы:

Заменить , первичный ключ , ФЗ

на , первичный ключ

и , первичный ключ .

2. Таблица имеет первичный (возможный) ключ , поле , которое не является возможным ключом, но функционально зависит от , а также – другое неключевое поле , функционально зависящее от : . Рекомендуется сформировать таблицу содержащую и ( - первичный ключ), и – удалить из первоначальной таблицы:

Заменить , первичный ключ ,

ФЗ

на , первичный ключ ,

и , первичный ключ .

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

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

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

По опр.1, любое отношение будет находиться в 1НФ, т.е. отношение, удовлетворяющее свойствам отношений: в отношении нет одинаковых кортежей; кортежи не упорядочены; атрибуты не упорядочены и различаются по наименованию; все значения атрибутов атомарны.

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

Если потенциальный ключ является простым, то отношение автоматически находится в 2НФ.

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

Атрибуты отношения называются взаимно-независимыми, если ни один из них не является функционально зависимым от другого.

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

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

При приведении отношений при помощи алгоритма нормализации к отношениям в 3НФ предполагается, что все отношения содержат один потенциальный ключ. Это не всегда верно. Бывают случаи, когда отношение может содержать несколько ключей.

Опр.4. Отношение находится в нормальной форме Байса-Кодда (НФБК) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами (либо - если любая функциональная зависимость между его палями сводится к полной функциональной зависимости от возможного ключа).

Если отношение находится в НФБК, то оно автоматически находится в 3НФ, что следует из определения 4. Чтобы устранить зависимость от детерминантов, не являющихся потенциальными ключами, следует провести декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение.

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

Опр.5. Отношение находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.

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

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

Опр.6. Отношение находится в пятой нормальной форме (5НФ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.

Опр.6. тождественно также следует определению.

Опр.7. Отношение не находится в 5НФ, если в отношении найдется нетривиальная зависимость соединения.

Т.о. если в каждой полной декомпозиции все проекции исходного отношения содержат возможный ключ, можно сделать вывод о том, что отношение находится в 5НФ. Отношение, не имеющее ни одной полной декомпозиции также находится в 5НФ.

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

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

Взаимно-независимые атрибуты – это атрибуты, не зависящие один от другого. Если в отношение существует несколько ФЗ, то каждый атрибут или набор атрибутов, от которого зависит другой атрибут, называется детерминантом отношения.

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

Существует несколько способов разрешения коллизий.

Разрешение коллизий при помощи цепочек.

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

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

При предположении, что каждый элемент может попасть в любую позицию таблицы H с равной вероятностью и независимо от того, куда попал любой другой элемент, среднее время работы операции поиска элемента составляет Θ(1 + α), где α — коэффициент заполнения таблицы.