Классика баз данных - статьи

       

Дубликаты, неопределенные значения


Наверное, многим знатокам языка SQL содержимое этой заметки

покажется тривиальным. Особенно тем, кто читает колонку Криса

Дейта в журнале "Database Programming and Design" (www.dbpd.com).

Поверьте, что я не конкурирую с уважаемым господином (и моим

любимым автором) Дейтом, а лишь хочу высказать свои собственные

соображения, возникшие в ходе подготовки практического курса по

языку SQL. Я занимаюсь вопросами, связанными с организацией

доступа к базам данных, уже более 20 лет, и поэтому мне самому

было странно обнаружить в языке SQL некоторые неафишируемые, но

глубоко присущие ему свойства, отстраняющие язык от классической

реляционной теории.

Дубликаты

Будем придерживаться глубоко противной, но прижившейся в мире



популистской терминологии таблиц, строк и столбцов (вместо

классической терминологии отношений, кортежей и атрибутов).

Некуда деваться, поскольку классическая терминология не дает

возможности погрузиться в болезненные отклонения языка SQL.

Поверьте, что я не являюсь противником этого языка. Хотелось бы

лучшего, равно как хотелось бы иметь общественный строй, отличный

от коммунизма и капитализма, но мы не можем быстро изобрести

что-либо законченное и хорошее.

Язык SQL подобно языку Си (покажите мне того, кто его искренне

любит) возник вовремя. Людям нравятся компромиссы. Компромиссы

любят и создаваемые ими предметы. SQL - это классический пример

языка баз данных, с самого начала основанный на компромиссах.

Господа, Вы хотите иметь реляционный язык? OK, вот он, реляционно

полный (доказано!) язык. Господа, Вы хотите сохранить житейскую

правду жизни при ее моделировании в базах данных? OK, вот он -

язык SQL, близкий и полезный неортодоксальным пользователям баз

данных. За что боролись, то и имеем... Примером бескомпромиссного

языка был Quel. Чистый, понятный, основанный исключительно на

реляционном исчислении кортежей. Его не приняли.

Да, язык SQL действительно реляционно полон. То есть, на нем

можно выразить любое выражение классической реляционной алгебры


или любую формулу реляционного исчисления. Но, к сожалению, на

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

относятся расширения - остается непонятным...

Прежде всего это касается возможности таблиц (в модели SQL)

содержать строки-дубликаты. На первый взгляд это кажется мелочью.

На самом деле это принципиально. Вся реляционная теория основана

на теории множеств. Математические множества не допускают наличия

дублирующих элементов. Поэтому в теории реляционных баз данных

отношения, которые определяются как множества кортежей, не могут

содержать кортежи-дубликаты. И дальше все получается прекрасно.

Строится алгебра или исчисление, которые замкнуты относительно

понятия отношения: результат вычисления алгебраического выражения

или интерпретации логической формулы является отношением,

следовательно, везде, где можно использовать хранимое отношение,

можно использовать выражение или формулу. Именно из

фундаментального свойства отсутствия дубликата следует наличие

возможного (а следовательно, и первичного) ключа отношения (быть

может, нескольких возможных ключей).

С другой стороны, требование отсутствия дубликатов в некоторых

случаях приводит к утрате части информации при выполнении

алгебраических операций. Прежде всего это связано с операцией

проецирования отношения. Поскольку не требуется, чтобы в число

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

при выполнении этой операции могут возникать кортежи-дубликаты, а

поскольку в результате должно получиться отношение, то они должны

устраняться. Тем самым, при выполнении операции проекции мы,

вообще говоря, теряем информацию о количестве кортежей,

содержащих одни и те же значения в атрибутах проекции.

Поскольку язык SQL является компромиссом между требованиями

теории и практики, в нем отсутствие в таблицах дублирующих строк

не является абсолютным требованием. То есть хорошим тоном

является отказ от использования таких таблиц, но язык этого не

требует.


На самом деле, отказ от полного запрета дублирующих

строк вызывает очень далеко идущие последствия.

Например, по этой причине пришлось переопределить семантику

теоретико-множественных операций над таблицами. В SQL имеются

операции UNION ALL (расширенное объединение), INTERSECT ALL

(расширенное пересечение) и EXCEPT ALL (расширенное вычитание),

выполнение которых не уничтожает строки-дубликаты в результате.

Если такая операция выполняется над таблицами T1 и T2, и

некоторый кортеж C входит в обе таблицы, причем содержит n

дубликатов в таблице T1 и m дубликатов в таблице T2, то в

результате операции T1 UNION ALL T2 будет содержаться n+m

дубликатов C, в результате операции T1 INTERSECT ALL T2 -

min(n, m) дубликатов С, а в результате T1 EXCEPT ALL T2 - max((n-m), 0)

дубликатов C. Похоже, что такая трактовка

"теоретико-мультимножественных" операций введена исключительно

для определенности и не подкрепляется какими-либо здравыми

доводами.

Но это, конечно, далеко не все последствия, которые вызвал отказ

от запрета дубликатов.

Возможные и первичные ключи

Когда читаешь описание языка SQL (например, стандарт SQL/92),

как-то не сразу обращаешь внимание, что при определении схемы

таблицы (оператор CREATE TABLE) разделы PRIMARY KEY и UNIQUE

являются необязательными. Зато сразу бросается в глаза

определение таблицы, в которой не задан первичный ключ. Лично я

впервые в своей практике столкнулся с такими таблицами в

демонстрационной базе данных pubs, поставляемой вместе с

Microsoft SQL Server. В этих таблицах, естественно, нет

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

в них не существует ни одного возможного ключа. Но сам факт

наличия подобных таблиц заставил меня по-новому оценить

необязательность разделов PRIMARY KEY и UNIQUE в определении

таблицы.

На самом деле, как мы увидим ниже, компания Microsoft могла

немного по-другому спроектировать схему базы данных pubs,

добившись того, чтобы у каждой таблицы существовал хотя бы один



возможный ключ. Более того, можно было бы потребовать

использовать только такие базовые таблицы, у которых возможный

ключ существует. Но все дело в том, что это противоречило бы

принципам ортогональности компонентов языка SQL. В описании языка

утверждается, что базовые таблицы, динамически создаваемые

таблицы (хранимые таблицы, порождаемые при выполнении оператора

выборки) и представляемые таблицы (таблицы, материализуемые

только при выполнении адресованного к ним оператора языка SQL)

могут использоваться равноправно. Даже если мы потребуем, чтобы в

таблицах, входящих в основную схему базы данных, отсутствовали

дубликаты, а тем самым существовал хотя бы один возможный ключ,

мы никогда не сможем гарантировать отсутствие дубликатов (а

следовательно, наличие возможного ключа) в порождаемых (хранимых

и представляемых) таблицах. Поскольку все виды таблиц

равноправны, неразумно требовать наличия возможного ключа у

базовых таблиц. Все это звучит логично, и в некоторой степени

оправдывает необязательность разделов PRIMARY KEY и UNIQUE.

Но с другой стороны, возможность существования таблицы без

первичного ключа в достаточной степени противоречит здравому

смыслу. Базы данных существуют для хранения информации о реально

существующих или воображаемых объектах окружающей

действительности. В классическом реляционном подходе принято

считать, что каждый кортеж каждого отношения описывает свойства,

присущие некоторой сущности реального мира. В реальном мире не

бывает двух полностью одинаковых объектов, поэтому и любые два

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

из этого следует существование возможного (и первичного) ключа.

Можно взглянуть на это и с другой точки зрения. Первичный ключ

является своего рода адресом кортежа отношения. Используя

соответствующее значение (может быть, составное) мы можем сказать

системе управления базами данных, информация о каком объекте нас

интересует. Конечно, все эти здравые соображения становятся



бессмысленными, когда речь идет о таблицах со

строками-дубликатами. Самое интересное состоит в том, что если

реляционная теория наводит на мысль о том, как правильно,

корректно и полезно использовать базы данных, то язык SQL, якобы

давая пользователям большую свободу, ничего не предлагает

относительно способов полезного использования этой свободы.

Первичные ключи и неопределенные значения

Как мы обещали выше, рассмотрим реальные причины того, что в двух

таблицах базы данных pubs отсутствует первичный ключ. Для

определенности выберем одну из этих таблиц - discounts (скидки).

Схема таблицы выглядит следующим образом:

CREATE TABLE discounts

(discounttype varchar(40) NO NULL, stor_id char(4),

lowqty smallint, highqty smallint, discount float NO NULL,

FOREIGN KEY stor_id REFERENCES stores)

Как видно, строка таблицы описывает скидку, назначенную для

указанного магазина. Однако в то же время строки таблицы могут

описывать и потенциально возможные скидки, даже если они не

назначены никакому магазину (поэтому столбцы stor_id, lowqty и

highqty могут содержать неопределенные значения). С другой

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

магазинов. Тем самым, пара столбцов (discounttype и discount),

которые могли бы служить первичным ключом, на самом деле таковыми

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

потому что потенциально содержать неопределенные значения). Тем

самым, мы имеем таблицу, принципиально не содержащую первичного

ключа и потому (опять же потенциально) включающую

строки-дубликаты (смысла в них нет, но ничто не запрещает их

появление).

Как мы уже говорили, компания Microsoft могла бы сделать схему

базы данных pubs более соответствующей рецептам реляционной

теории. Например, можно было бы вместо таблицы discount сделать

две таблицы:

CREATE TABLE discounts

(discount_id int NO NULL, discounttype varchar(40) NO NULL,

discount float NO NULL,

PRIMARY KEY (discount_id))

CREATE TABLE discountsstores



( discount_id int NO NULL, stor_id char(4) NO NULL,

lowqty smallint NO NULL, highqty smallint NO NULL,

PRIMARY KEY (discount_id, stor_id),

FOREIGN KEY (discount_id) REFERENCES discounts,

FOREIGN KEY (stor_id) REFERENCES stores)

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

SQL никаким образом не стимулирует такое более правильное

проектирование баз данных. И именно потому, что в таблицах могут

содержаться дубликаты. Раз все равно могут существовать таблицы

без первичного ключа, то зачем навязывать первичные ключи при

определении таблицы. Компромиссы...

Первичные, возможные, внешние ключи, функциональные зависимости и

операция группирования


Я снова воспользуюсь примером из базы данных pubs. В базе данных

имеются таблицы sales и stores, определяемые следующим образом:

CREATE TABLE sales (stor_id char(4) NO NULL,

ord_num varchar(20) NO NULL, ord_date datetime NO NULL,

qty smallint NO NULL, payments varchar(12) NO NULL,

title_id tid NO NULL,

PRIMARY KEY (stor_id, ord_num, title_id),

FOREIGN KEY (stor_id) REFERENCES stores,

FOREIGN KEY (title_id) REFERENCES titles)

CREATE TABLE stores (stor_id char(4) NO NULL,

stor_name varchar(40), stor_address varchar(40),

city varchar(20), state char(2), zip char(5),

PRIMARY KEY (stor_id))

Возникает естественное желание выполнять запросы с

эквисоединением этих двух таблиц, получая некоторую агрегатную

информацию о заказах, выполняемых некоторыми магазинами. Примером

такого запроса может быть следующий: "Выдать названия, адреса и

общий объем заказов для магазинов, расположенных в штате

Калифорния". На языке SQL хочется написать такой запрос:

SELECT stor_name, stor_address, sum(qty)

FROM stores A, sales B

WHERE state = 'CA' AND A.stor_id = B.stor_id

GROUP BY A.stor_id

Мы-то понимаем, что хотим сказать: результат соединения

группируется по значениям столбца stor_id, но мы знаем, что

идентификатору магазина в таблице stores однозначно соответствует

его название и адрес (более точно, существуют функциональные



зависимости stor_id -> stor_name и stor_id -> stor_address,

потому что stor_id - первичный ключ таблицы stores). Эти

зависимости сохраняются и в соединенной таблице (stores INNER

JOIN sales ON (stores.store_id = sales.stor_id)). Тем самым,

значения полей stor_name и stor_address являются общими

характеристиками группы c одинаковыми значениями stor_id

соединенной таблицы. Однако при попытке выполнить запрос мы

получим диагностику о недопустимости включения в список выборки

имен столбцов, не входящих в список группирования. И формально

это совершенно правильно, поскольку язык SQL не обязывает

реализацию выводить зависимости для порождаемых таблиц, и система

не имеет информации о существующих функциональных зависимостях.

Более того, язык SQL не предоставляет средств для выражения таких

функциональных зависимостей.

Мне казалось, что ситуация изменится, если мы огрубим ситуацию и

объявим столбцы stor_name и stor_address возможными ключами. Для

этого в языке SQL используется раздел UNIQUE определения таблицы.

В частности, в определении таблицы stores добавились бы строчки

UNIQUE (stor_name),

UNIQUE (stor_address)

Теперь уже система имеет полную информацию об однозначном

соответствии значений столбцов stor_id, stor_name и stor_address.

Однако запрос по-прежнему не выполняется, и диагностика

сохраняется той же самой. И опять-таки это формально правильно,

поскольку в спецификациях языка четко сказано, что если в запросе

используется раздел GROUP BY, то в списке выборки могут

участвовать только имена столбцов, входящих в список

группирования, и агрегатные функции, применяемые к другим

столбцам таблиц, которые перечислены в разделе FROM. Но

пользователям от этого не легче. Похожие таблицы очень вероятно

используются в практических базах данных, и запросы, подобные

приведенному выше, вполне естественны. Для того, чтобы получить

запрос, правильно воспринимаемый системой, его придется

переформулировать следующим образом:

SELECT stor_name, stor_address, sum(qty)



FROM stores A, sales B

WHERE state = 'CA' AND A.stor_id = B.stor_id

GROUP BY A.stor_id, A.stor_name, A.stor_address

В общем- то ничего страшного, можно написать и так. Но, во-первых,

это неестественно: мы вторично сообщаем системе то, что уже было

сказано при создании таблицы stores. Во-вторых, если совершенно

очевиден способ выполнения операции группирования по столбцу

stores.stor_id (поскольку это первичный ключ, то в любой СУБД для

столбца stor_id будет создан уникальный индекс), то не очень

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

(оптимизатор сможет выбирать стратегии сортировки соединенной

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

использования одного из трех индексов; поскольку мы объявили

stor_name и stor_address возможными ключами, то для этих столбцов

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

И последнее в этой заметке наблюдение. Если классики реляционной

теории говорят, что в любом отношении должен существовать хотя бы

один возможный ключ, а первичный ключ выбирается неформализуемым

образом из набора возможных ключей, то в языке SQL это не так. В

соответствии со стандартом, первичный ключ не может содержать

неопределенных значений, а ключи, объявляемые с использованием

спецификации UNIQUE, - могут содержать неопределенные значения.

Следовательно, вообще говоря в таблице SQL-ориентированной базы

данных может существовать возможный ключ и одновременно не

существовать первичного ключа. Кстати, именно так обстоит дело в

исходным вариантом таблицы discounts (если еще раз внимательно

посмотреть на ее определение, то можно убедиться, что возможный

ключ в смысле языка SQL в этой таблице существует).

Вывод, который мне хотелось бы сделать, совпадает с призывом

одного из прогрессивных деятелей: "Люди, будьте бдительны!" (даже

если вы пользуетесь стандартным языком баз данных SQL).


Содержание раздела