Неопределенные значения в SQL

Джон Грант

🕛 06.03.2009, 00:52

Аннотация

В различных публикациях в последние 20 лет, таких как [3], Дейт указывает на то, что SQL производит для некоторых запросов некорректные ответы, если соответствующая таблица содержит неопределенное значение. В недавней статье [8] в ACM SIGMOD Record Рубинсон утверждает, что «Дейт неправильно понимает смысл запроса в своем примере», и что «SQL возвращает на этот запрос корректный ответ». Цель этой статьи состоит в том, чтобы показать, что, вопреки утверждениям Рубинсона, критика Дейта выполнения SQL-запросов в присутствии неопределенных значений является полностью оправданной.
1. Введение

В последние 20 лет в различных публикациях Дейт указывает на дефекты метода выполнения SQL-запросов при наличии неопределенных значений. Проблема кроется в способе использования в SQL трехзначной логики при выполнении таких запросов. В действительности, имеются различные типы неопределенных значений; в данной статье имеется в виду только тот тип, в котором null представляет существующее, но не известное значение.

В недавней статье в ACM SIGMOD Record Рубинсон утверждает, что «Дейт неправильно понимает смысл запроса в своем примере», и что «SQL возвращает на этот запрос корректный ответ». Целью данной статьи является некоторый исторический обзор методов выполнения запросов к реляционным базам данных с неопределенными значениями и опровержение утверждений Рубинсона. На самом деле, критика Дейта корректна и полностью обоснована. С разд. 2 обсуждается пример Дейта, приведенный в [8]. В разд. 3 приводится исторический обзор методов выполнения запросов к реляционным базам данных с неопределенными значениями. В разд. 4 показывается, что критика Дейта поддерживается разнообразными подходами, обобщающими и расширяющими неопределенные значения. В завершающем статью разд. 5 приводится краткое обсуждение.
2. Пример Дейта

Этот материал взят непосредственно из [8], а пример Дейта скопирован из [3] с использованием немного другой нотации. В примерной базе данных имеются две таблицы: Suppliers (sno,city) и Parts (pno,city). Первичными ключами являются sno и pno соответственно. В каждой таблице содержится по одной строке: в Supplier имеется строка <S1, London>, а в Parts - <P1,Null>. Для детали P1 наименование города неизвестно, и, следовательно, обозначается неопределенным значением. Запрос Дейта на естественном языке выглядит следующим образом: «Получить пары sno-pno, для которых либо города поставщика и детали различны, либо городом детали не является Париж (или выполнены оба условия»). На SQL это записывается следующим образом:

Select sno, pno
From Suppliers, Parts
Where Suppliers.city <> Parts.city
Or Parts.city <> ’Paris’;

Для заданных таблиц этот SQL-запрос возвращает пустую таблицу. Однако, как объясняет Дейт, правильным ответом является <s1, p1>. Дейт рассматривает три возможности для города детали P1: Париж, Лондон и некоторый другой город. На самом деле, имеются два уместных случая: либо город детали P1 - это Париж, либо не Париж. В первом случае условие раздела Where истинно, поскольку городом поставщика S1 является Лондон, и сравнение London <> Paris дает true. Во втором случае условие Where истинно, поскольку Parts.city <> ’Paris’ дает true. Не имеет значения то, что название города представлено неопределенным значением; кортеж <S1, P1> удовлетворяет условию запроса и должен присутствовать в ответе. Этот простой пример иллюстрирует дефект, замеченный Дейтом в SQL.
3. Исторический обзор

В начале 1970-х гг. в серии очень влиятельных статей Э.Ф. Кодд представил реляционную модель баз данных, включающую реляционное исчисление, реляционную алгебру и нормализацию реляционных баз данных. У него также была колонка в журнале FDT Bulletin of ACM-SIGMOD, предшествовавшем ACM SIGMOD Record, в которой он разъяснял различные понятия реляционных баз данных.

В [1] он отвечал на вопрос об обработке запросов при наличии с реляционной базе данных неопределенных значений. Для иллюстрации он использовал реляционное исчисление. Кодд предложил трехзначную логику с истинностными значениями ‘True’, ‘False’ и ‘Unknown’. Если в таблице имеется неопределенное значение, то условие, в вычислении которого оно участвует, производит истинностное значение ‘Unknown’. Истинностные значения для сложных условий вычислялись на основе таблиц истинности для связок ‘and’, ‘or’ и ‘not’. Например, значением условия ‘True or Unknown’ является ‘True’, поскольку дизъюнкция истинна при истинности хотя бы одного дизъюнкта. Кодд вычислял условие ‘Uknown or Uknown’ как ‘Uknown’. В примере Дейта оба условия Suppliers.city <> Parts.city и Parts.city <> ‘Paris’ вычисляются для строки P1 в ‘Uknown’; следовательно, по методу Кодда ‘Uknown’ дает и вычисление всего условия.

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

Для случая неопределенных значений в реляционной базе данных это означает, что истинностные таблицы, используемые Коддом (как и в трехзначной логике Клини), не всегда приводят к корректным ответам на запросы. Сначала я написал доктору Кодду, разъяснив проблему, а после получения его ответа написал короткую статью [5] с описанием этой проблемы. На самом деле, в своем примере я использовал таблицу Suppliers и условие Suppliers.city = ‘Paris’ из пионерского учебника Дейта [2] (первое издание!).

Я также предложил в [4] решение, специально приспособленное для запросов к реляционным базам данных: для корректной обработки запросов при наличии неопределенных значений должны рассматриваться все различные случаи. Это именно то, что я делал с примером Дейта в предыдущем разделе, где имелись два случая - либо город - это Париж, либо не Париж. Если во всех случаях условие для некоторого кортежа дает ‘True’, то этот кортеж должен войти в ответ на запрос.

Кстати, в [5] я также показал, как следует обращаться со случаем, когда неопределенное значение обозначает неприменимый атрибут, такой как имя жены неженатого мужчины.

В конце 1970-х гг. неопределенные значения обобщались несколькими исследователями (включая меня самого) до понятия неполной или частичной информации (понятие, которое я изучал в начале 1970-х в контексте логики). В начале 1980-х гг. в своей пионерской книге по теории баз данных [7] Мейер посвятил этой теме целую главу.

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

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

За последние 30 лет исследователи баз данных проделали огромную работу по добавлению различных возможностей к реляционным базам данных. В некоторых из этих работ разными способами обобщалось понятие неопределенных значений. В этом разделе рассматриваются два таких обобщения: дизъюнктивные и вероятностные базы данных. Анализируется, как трактовался бы пример Дейта на основе этих подходов.

В дизъюнктивной базе данных [6] допускаются дизъюнктивные факты, такие как (для примера Дейта) P1.city = ’Paris’ or P1.city = ’London’ or P1.city = ’New York’. Если только эти города для P1 являются допустимыми, то смысл такого условия является таким же, что и условия P1.city = Null, но если для P1 допустимы и другие города, то первое условие является более строгим, поскольку оно ограничивает город детали P1 одним из трех возможных значений. Такие факты могут записываться следующим образом:

Suppliers(s1, london) ← Parts(p1, paris) ∨ Parts(p1, london) ∨ Parts(p1, newyork)

Из-за наличия дизъюнкции запрос записывается как два определения предиката запроса Q:

Q(Sno, Pno) ← Suppliers(Sno,City1), Parts(Pno,City2), City1 ≠ City2
Q(Sno, Pno) ← Suppliers(Sno,City1), Parts(Pno,City2), City2 ≠ paris

На запрос ← Q(Sno, Pno) дизъюнктивная база данных выдаст ответ <s1, p1>.

В вероятностной базе данных можно определить распределение вероятностей на множестве экземпляров [9]. В данном случае информация об индивидуальности неопределенного значения является вероятностной. Предположим, например, что в примере Дейта имеются три разных мира: во всех трех имеется Supplier (S1,London), но для деталей пусть будут назначены вероятности - Pr(Parts(P1,London)) = 0.5, Pr(Parts(P1,Paris)) = 0.3, Pr(Parts(P1, New York)) = 0.2.

Теперь рассмотрим запрос Дейта. Для всех разновидностей семантики построения ответа и семантики допустимых кортежей мы получим значение Pr(<s1, p1>) = 1. То есть опять с вероятностью 1 ответом является <s1, p1>. Тот же ответ будет получен независимо от числа возможных городов и распределения вероятностей между городами детали P1.
5. Обсуждение

Много лет Дейт критикует подход к обработке запросов, принятый в SQL, включая неопределенные значения. В этой статье объясняется, что обработка таких запросов в SQL следует из предложения Кодда, некорректность которого (в некоторых случаях) я показал более 30 лет тому назад. Семантика многочисленных расширений реляционных баз данных, предложенных исследователями за последние 30 лет, согласуется со смыслом примерного запроса Дейта. Утверждение Рубинсона о том, что «Дейт ошибается», некорректно.

Стоит закончить эту статью еще одной демонстрацией несостоятельности статьи Рубинсона. Следующая цитата ясно показывает его непонимание сути проблемы: «Запрос Дейта невозможно правильно оттранслировать в SQL, потому что в нем предполагается использование традиционной двухзначной логики, а в SQL применяется трехзначная логика». Конечно, запрос Дейта можно оттранслировать в SQL, что Дейт и сделал (см. разд. 2). Кажется, Рубинсон полагает, что метод выполнения запросов, используемый в SQL, является присущим этому языку, но это вовсе не так. Как я разъяснил в разд. 3, метод выполнения запросов, используемый в SQL, вообще не является присущим для реляционных баз данных; это всего-навсего результат выбора, сделанного комитетом по стандартизации. Так что проблема вовсе не в том, что в SQL используется трех-, а не двухзначная логика. Проблема кроется в способе использования трехзначной логики при выполнении SQL-запросов.