Охарактеризуйте понятие реляционного исчисления.

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

Предположим, что мы работаем с базой данных, содержащей отношения Студенты (Студент_Номер, Студент_Имя, Студент_Стипендия, Группа_Номер) и Группы (Группа_Номер, Группа_Наименование, Группа_Количество, Группа_Староста), и хотим узнать имена и номера студентов, являющихся старостами групп с количеством студентов в них больше 20.

Выдать Студент_Имя и Студент_Номер для студентов таких, что существует группа с таким же значением Группа_Староста и значением Группа_Количество большим 20.

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

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

Охарактеризуйте понятие нормализации.

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

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

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

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

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

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

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

Формально, для приведения схемы в 3НФ необходимо исключить все транзитивные зависимости.

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

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

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

Опишите нормальные формы.

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

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

Вторая нормальная форма

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

Третья нормальная форма

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

Выделите общие свойства отношений в реляционной базе данных.

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

Основные свойства отношения

¾ В отношении нет двух одинаковых элементов (кортежей).

¾ Порядок кортежей в отношении не определён.

¾ Порядок атрибутов в заголовке отношения не определён.

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

Охарактеризуйте процесс хранения отношений и индексов.

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

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

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

Индексы

B-деревья

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

Хэширование

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