Теория реляционных БД

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

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

При строгом подходе рассмотрение третьей процедуры (как это сделал Э. Кода) является как бы автономным и не входит в теорию реляционных БД. Однако, поскольку работа во все более широко используемом многопользовательском доступе к данным без теоретической проработки процедуры синхронизации невозможна, ее изучение также включим в теорию реляционных БД [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®. Любому имени Аi. ставится в соответствие множество Di (домен или dom (Ai)). Схема — конечное множество кортежей t I r, при этом t (Ai) = Di.

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

• 1) для любых двух кортежей t1 и t2 существуют B I К, такое, что t1(B)? t2 (В);
• 2) t1(K)? t2(K);
• 3) ни одно собственное подмножество К' с К не обладает свойством ключа.

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

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

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

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

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

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

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

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

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

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

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

• 1) создание;
• 2) обновление и запрос;
• 3) синхронизация процессов доступа.

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

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

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

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

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