ответы к зачёту по Базам Данных (2009), страница 2

Тип данных — некая база, как в языках программирования (целые числа, строки), множество значений, над которыми определены операции, а также представление этих чисел при выводе (литералы).

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

Схема отношения (заголовок отношения, отношение-схема) Hr — конечное именованное множество пар {имя атрибута, имя домена (или типа, если понятие домена не поддерживается)}. Степень или "арность" схемы отношения — мощность этого множества. Степень отношения СОТРУДНИКИ равна четырем, то есть оно является 4-арным.

Кортеж, соответствующий данной схеме отношения tr(Hr) — множество пар {имя атрибута, значение}, которое содержит одно вхождение каждого имени атрибута, принадлежащего схеме отношения. "Значение" является допустимым значением домена данного атрибута (или типа данных, если понятие домена не поддерживается). Тем самым, степень или "арность" кортежа, т.е. число элементов в нем, совпадает с "арностью" соответствующей схемы отношения. Попросту говоря, кортеж — это набор именованных значений заданного типа.

Отношение (тело отношения) — это множество кортежей, соответствующих одной схеме отношения.

Эволюция схемы базы данных — определение новых и изменение существующих схем отношения.

Реляционная база данных — набор отношений, имена которых совпадают с именами схем отношений в схеме БД.

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

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

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

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

Требование целостности сущности (entity integrity): значение первичного ключа не может быть не определено. Что же такое не определено? Вводится NULL - неопределенное значение для любого типа данных. Для булевских вводится значение unknown.

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

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

1. Реляционная алгебра Кодда. Перечислить все операции. Приоритет операций. Замкнутость реляционной алгебры.

Отношения, с которыми идет работа в реляционных БД, являются множествами. У Кодда появилась идея составить на них алгебру. Есть общие операции (теоретико-множественные), а есть специальные (реляционные операции). Везде вместо «отношение»  «тело отношения» можно читать «таблица», так проще понять.

В состав теоретико-множественных операций входят операции:

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

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

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

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

Специальные реляционные операции включают:

• Ограничение (WHERE) отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию.

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

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

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

Дополнительно:

• Переименование (RENAME) производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены.

• Присваивание (:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.

Приоритеты:

RENAME   WHERE = PROJECT   TIMES = JOIN = INTERSECT = DIVIDE BY   UNION = MINUS Алгебра не является замкнутой в математическом смысле (например, TIMES в случае одинаковых заголовков не является отношением). Но применение операции RENAME позволяет использовать алгебру Кодда почти как замкнутую алгебру.

Реляционное деление: объяснение для людей. Пусть заданы два отношения - A с заголовком {a₁, a₂, ..., a_n, b₁, b₂, ..., b_m} и B с заголовком {b₁, b₂, ..., b_m}. Будем считать, что атрибут b_i отношения A и атрибут b_i отношения B не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {a_j} составным атрибутом a, а множество атрибутов {b_j} - составным атрибутом b. После этого будем говорить о реляционном делении бинарного отношения A(a,b) на унарное отношение B(b).

Результатом деления A на B является унарное отношение C(a), состоящее из кортежей v таких, что в отношении A имеются кортежи <v, w> такие, что множество значений {w} включает множество значений атрибута b в отношении B.

Предположим, что в базе данных сотрудников поддерживаются два отношения: СОТРУДНИКИ ( ИМЯ, ОТД_НОМЕР ) и ИМЕНА ( ИМЯ ), причем унарное отношение ИМЕНА содержит все фамилии, которыми обладают сотрудники организации. Тогда после выполнения операции реляционного деления отношения СОТРУДНИКИ на отношение ИМЕНА будет получено унарное отношение, содержащее номера отделов, сотрудники которых обладают всеми возможными в этой организации именами.

1. Реляционная алгебра Кодда. Теоретико-множественные операции. Совместимость отношений по объединению и по расширенному декартовому произведению.

Подробнее — вопрос 7. Теоретико-множественные операции: объединение (UNION), пересечение (INTERSECT), разность (MINUS) и декартово произведение (TIMES). Два отношения совместимы по объединению в том и только в том случае, когда обладают одинаковыми заголовками (схемами отношений ). Более точно, это означает, что в заголовках обоих отношений содержится один и тот же набор имен атрибутов, и одноименные атрибуты определены на одном и том же домене. Тогда к ним можно применять объединение и получить правильное отношение. Иначе – нет. Но если типы одни и те же, а только названия полей отличаются, то можно применить RENAME.

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

1. Реляционная алгебра Кодда. Специальные реляционные операции.

Подробнее — вопрос 7. Ограничение, пример: СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 WHERE (СЛУ_ЗАРП > 20000.00 AND (СЛУ_ОТД_НОМ = 310 OR СЛУ_ОТД_НОМ = 315)).

Проекция (возвращает не всю таблицу (отношение), а только часть ее): PROJECT СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 {СЛУ_ОТД_НОМ} – вернет отношение с одним полем «СЛУ_ОТД_НОМ».

Соединение: берем два отношения, строим их декартово произведение, к нему применяем условие. Пример: СЛУЖАЩИЕ JOIN ПРОЕКТЫ WHERE (СЛУ_ЗАРП > ПРО_ЗАРП). В результате будут поля из таблицы СЛУЖАЩИЕ и ПРОЕКТЫ, и строки, которые удовлетворяют условию.

Реляционное деление: есть два отношения, в них есть пересекающиеся поля в заголовке (например, отношение СЛУЖАЩИЕ и ПРОЕКТЫ и домен НОМЕРА_ПРОЕКТОВ). В результате СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ получим тех служащих, которые участвуют в перечисленных проектах (1 или 2).

1. Реляционная алгебра А. Базовые операции подробно с примерами.

Идеи Кодда были переработаны несколько лет тому назад Дейтом и Дарвеном и была предложены новая алгебра А (притом этот алгебра в математическом смысле).

Небольшое повторение. Пусть r — отношение, A — имя атрибута отношения r, T — имя соответствующего типа (т. е. типа или домена атрибута A), v — значение типа T. Тогда:

заголовком Hr отношения r называется множество атрибутов, т.е. упорядоченных пар вида <A, T>. По определению никакие два атрибута в этом множестве не могут содержать одно и то же имя атрибута A;