Когнитивные модели языков программирования
За последние два десятилетия усложнение синтаксиса и семантики языков программирования вышло на качественно новый уровень. Широко используются иноязычные вставки, например, в серверных страницах и языках, допускающих встроенный SQL (англ, structured quere language — язык структурированных запросов).
SQL — формальный непроцедурный язык программирования, применяемый для создания, модификации и управления данными в произвольной реляционной базе данных (БД), управляемой соответствующей системой управления БД (СУБД). SQL основывается на исчислении кортежей, т. е. упорядоченных наборов данных, с элементами фиксированной длины.
Язык SQL (Structured Query Language — структурированный язык запросов) представляет собой стандартный высокоуровневый язык описания данных и манипулирования ими в СУБД, построенных на основе реляционной модели данных.
Язык SQL был разработан фирмой IBM в конце 1970-х гг. Первый международный стандарт языка был принят международной стандартизирующей организацией ISO в 1989 г., а новый (более полный) — в 1992 г. В настоящее время все производители реляционных СУБД поддерживают с различной степенью соответствия стандарт SQL92.
Единственной структурой представления данных (как прикладных, так и системных) в реляционной базе данных (РБД) является двумерная таблица. Любая таблица может рассматриваться как одна из форм представления теоретикомножественного понятия отношение (relation), отсюда название модели данных — реляционная. В реляционной модели данных таблица обладает следующими основными свойствами, рассмотренными в 18.4.
Реляционная модель данных: определение, индексирование
Реляционная модель данных (РМД) некоторой предметной области представляет собой набор отношений, изменяющихся во времени. Элементы РМД и формы их представления приведены в табл. 18.1.
Элементы реляционной модели
Элемент реляционной модели
Строка заголовков столбцов таблицы
Заголовок столбца таблицы
Множество допустимых значений атрибута
Один или несколько атрибутов
Тип значений элементов таблицы
Отношение является важнейшим понятием и представляет собой двумерную таб- лицу, содержащую некоторые данные.
Сущность — объект любой природы, данные о котором хранятся в БД. Данные о сущности хранятся в отношении.
Атрибуты представляют собой свойства, характеризующие сущность. В структуре таблицы каждый атрибут именуется и ему соответствует заголовок некоторого столбца таблицы.
Математически отношение можно описать следующим образом. Пусть даны п множеств Di, D2, D3. Dn, тогда отношение R есть множество упорядоченных кортежей , где dk е Dk, dk — атрибут, a Dk -домен отношения R.
В табл. 18.2 приведен пример представления отношения СОТРУДНИК.
Пример представления отношения СОТРУДНИК
Домен представляет собой множество всех возможных значений определенного атрибута отношения. Отношение СОТРУДНИК включает 4 домена. Домен 1 содержит фамилии всех сотрудников, домен 2 — номера всех отделов фирмы, домен 3 — названия всех должностей, домен 4 — даты рождения всех сотрудников. Каждый домен образует значения одного типа данных, например, числовые или символьные.
Отношение СОТРУДНИК содержит 3 кортежа. Кортеж рассматриваемого отношения состоит из 4 элементов, каждый из которых выбирается из соответствующего домена. Каждому кортежу соответствует строка таблицы (табл. 2).
Схема отношения (заголовок отношения) представляет собой список имен атрибутов. Например, для приведенного примера схема отношения имеет вид СОТРУДНИК (ФИО, отдел, должность, дата_рождения). Множество собственно кортежей отношения часто называют содержимым (телом) отношения.
Первичным ключом (ключом отношения, ключевым атрибутом) называется атрибут отношения, однозначно идентифицирующий каждый из его кортежей. Например, в отношении СОТРУДНИК (ФИО, отдел, должность, дата рождения) ключевым является атрибут «ФИО». Ключ может быть составным (сложным), т. е. состоять из нескольких атрибутов.
Возможны случаи, когда отношение имеет несколько комбинаций атрибутов, каждая из которых однозначно определяет все кортежи отношения. Все эти комбинации атрибутов являются возможными ключами отношения. Любой из возможных ключей может быть выбран как первичный.
Ключи обычно используют для достижения следующих целей:
- • исключения дублирования значений в ключевых атрибутах (остальные атрибуты в расчет не принимаются);
- • упорядочения кортежей по возрастанию или убыванию значений всех ключевых атрибутов, а также смешанное упорядочение (по одним — возрастание, а по другим — убывание);
- • ускорения работы к кортежами отношения;
- • организации связывания таблиц.
Пусть в отношении Ri имеется не ключевой атрибут А, значения которого являются значениями ключевого атрибута В другого отношения R2. Тогда говорят, что атрибут А отношения R1 есть внешний ключ.
С помощью внешних ключей устанавливаются связи между отношениями. Например, имеются два отношения СТУДЕНТ (ФИО. Группа, Специальность) и ПРЕДМЕТ (название, предмет, часы), которые связаны отношением СТУДЕНТ — ПРЕДМЕТ (ФИО, Название Предмета, оценка) (рис. 17.1). В связующем отношении атрибуты ФИО и Название. Пр образуют составной ключ. Эти атрибуты представляют собой внешние ключи, являющиеся первичными ключами других отношений.
Рис. 18.1. Установление связей между отношениями
Реляционная модель накладывает на внешние ключи ограничение для обеспечения целостности данных, называемое ссылочной целостностью. Это означает, что каждому значению внешнего ключа должны соответствовать строки в связывае-мых отношениях.
Существуют условия, при которых таблица будет являться отношением.
- • все строки таблицы должны быть уникальны, т. е. не может быть строк: с одинаковыми первичными ключами;
- • имена столбцов таблицы должны быть различны, а значения их простыми, т. е. недопустима группа значений в одном столбце одной строки;
- • все строки одной таблицы должны иметь одну структуру, соответствующую именам и типам столбцов;
- • порядок размещения строк в таблице может быть произвольным.
Если задаваемое таблицей отношение имеет ключ, то считается, что таблица тоже имеет ключ и ее называют ключевой или таблицей с ключевыми полями.
Основной единицей обработки данных в РБД является отношение, а не отдельные его кортежи (записи).
Индексирование. Как отмечалось выше, определение ключа для таблицы означает автоматическую сортировку записей, контроль отсутствия повторений значений в ключевых полях записей и повышение скорости выполнения операций поиска в таблице. Для реализации этих функций в СУБД применяют индексирование.
Термин «индекс» тесно связан с понятием «ключ», хотя между ними есть и некоторое отличие.
Под индексом понимают средство ускорения операции поиска записей в таблице, а следовательно, и других операций, использующих поиск: извлечение, модификация, сортировка и т. д. Таблицу, для которой используется индекс, называют индексированной.
Индекс выполняет роль оглавления таблицы, просмотр которого предшествует обращению к записям таблицы. В некоторых системах, например Paradox, индексы хранятся в индексных файлах, хранимых отдельно от табличных файлов.
Варианты решения проблемы организации физического доступа к информации зависят в основном от следующих факторов:
- • вида содержимого в поле ключа записей индексного файла;
- • типа используемых ссылок (указателей) на запись основной таблицы;
- • метода поиска нужных записей.
В поле ключа индексного файла можно хранить значения ключевых полей индексируемой таблицы либо свертку ключа (так называемый хеш-код). Преимущество хранения хеш-кода вместо значения состоит в том, что длина свертки независимо от длины исходного значения ключевого поля всегда имеет некоторую постоянную и достаточно малую величину (например, 4 байта), что существенно снижает время поисковых операций. Недостатком хеширования является необходимость выполнения операции свертки (требует определенного времени), а также борьба с возникновением коллизий (свертка различных значений может дать одинаковый хеш- код).
Для организации ссылки на запись таблицы могут использоваться три типа адресов:
На практике для создания индекса для некоторой таблицы БД пользователь указывает поле таблицы, которое требует индексации. Ключевые поля таблицы во многих СУБД как правило индексируются автоматически. Индексные файлы, создаваемые по ключевым полям таблицы, часто называются файлами первичных индексов.
Индексы, создаваемые пользователем для не ключевых полей, иногда называют вторичными (пользовательскими) индексами. Введение таких индексов не изменяет физического расположения записей таблицы, но влияет на последовательность просмотра записей. Индексные файлы, создаваемые для поддержания вторичных индексов таблицы, обычно называются файлами вторичных индексов.