Лекция 4. Теория реляционных БД

Использование компьютера для реализации какого-либо процесса возможно лишь при наличии теоретического математического описания этого процесса. Сказанное относится и к процессам в базах данных.

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

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

Теоретические инструменты первых двух процедур – реляционная алгебра и реляционное исчисление. Реляционная алгебра (РА) является теоретической основой алгоритмических языков программирования, сложных для начинающего пользователя, тогда как на реляционном исчислении (РИ) построены (см. § 1.1.) более удобные декларативные языки программирования SQL и QBE.

В то же время РА позволяет наглядно отобразить процессы преобразования в базе данных одних таблиц в другие. Именно поэтому рассмотрение теории начнем с реляционной алгебры.

Математические основы теории

Полезно провести аналогию РА и школьного курса алгебры. В последнем в качестве элементов априори вводятся буквы, а операции над ними – сложение, вычитание (прямые) и умножение, деление (обратные). В то же время фундаментальная теория алгебры, включающая связи между операциями, такие основные свойства, как коммутативность ab = ba, ассоциативность (ab)c = a(bc), дистрибутивность (a + b)c – ab + bс, идемпотентность a2 = a, изучаются в вузовском курсе высшей алгебры.

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

Основы реляционной алгебры

Основные понятия. В основе реляционной БД лежит понятие "отношение", "связь".

Отношением r называется подмножество декартова произведения. Поля отношения (таблицы) могут располагаться в произвольном порядке. Чтобы установить определенный порядок для какой- либо конкретной реализации, вводят понятие "схема" R – множество упорядоченных имен атрибутов R(A1, ..., Аn). Говорят о схеме R отношения r или r(R). Любому имени Аi. ставится в соответствие множество Di (домен или dom(Ai)). Схема – конечное множество кортежей t Î r, при этом t(Ai) = Di.

Парадигмой реляционных БД является ключ r отношения R – подмножество К = {В1, ..., Bm} R, m ≤ n с ограничениями:

1) для любых двух кортежей t1 и t2 существуют B Î К, такое, что t1(B) ≠ t2 (В);

2) t1(K) ≠ t2(K);

3) ни одно собственное подмножество К' с К не обладает свойством ключа.

Ключи, явно перечисленные вместе с реляционной схемой, называются явными; в противном случае – неявными. Один из выделенных ключей называется первичным. Если ключ К' Ì К Ì R, то К – суперключ (составной ключ).

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

Например, пусть имеется отношение

R(Город, Адрес, Почтовый_индекс).

Очевидно, что атрибуты: Город Адрес → Почтовый_индекс. В то же время Почтовый_индекс → Город (хотя и не адрес). Оба множества могут быть возможными ключами.

Универсум U множество значений всех атрибутов. С учетом ключей схема R над U – совокупность отношений {R1, ..., RT}, где

Тогда реляционной БД d со схемой данных R называется совокупность отношений (r1, ..., rn}, где для любой схемы R = {S, К} существует отношение в d, являющееся отношением со схемой S,• удовлетворяющее любому ключу.

В реляционной БД, как это видно, оперируют таблицами, простейшим элементом является кортеж (запись).

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

Возникает вопрос: каковы должны быть правила создания и преобразования таблиц.

Фактически для таблиц выделяют следующие составляющие:

1) создание;

2) обновление и запрос;

3) синхронизация процессов доступа.

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

Начнем обсуждение с операций преобразования таблиц.

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

1) предикатами первого порядка;

2) использованием правил реляционной алгебры (РА) и реляционного исчислении (РИ).

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