2009 г.
Неопределенные значения в SQL
Джон Грант
Перевод: Сергей Кузнецов
Оригинал: John Grant. Null Values in SQL. SIGMOD Record, Vol. 37, No. 3, September 2008.
См. вступительную заметку Сергея Кузнецова «И снова о вечной проблеме отсутствующей информации»
Аннотация
В различных публикациях в последние 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-запросов.
6. Литература
[1] E. F. Codd. Understanding relations (installment #7). FDT Bulletin of ACM-SIGMOD, 7(3-4):23–28, 1975.
[2] C. J. Date. An Introduction to Database Systems. Addison-Wesley Publishing Co., Reading, MA, 1975.
[3] C. J. Date. An Introduction to Database Systems, 7th Edition. Addison-Wesley Publishing Co., Reading, MA, 2000. Имеется перевод на русский язык: К. Дейт. Введение в системы баз данных (7-е издание). Вильямс, 2001.
[4] J. Grant. A non-truth-functional 3-valued logic. Mathematics Magazine, 47(4):221–223, September-October 1974.
[5] J. Grant. Null values in a relational data base. Information Processing Letters, 6(5):156–157, October 1977.
[6] J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. The MIT Press, Cambridge, MA, 1992.
[7] D. Maier. The Theory of Relational Databases. Computer Science Press, Rockville, MD, 1983. Имеется перевод на русский язык: Мейер Д.
Теория реляционных баз данных. М., Мир, 1987.
[8] C. Rubinson. Nulls, three-valued logic, and ambiguity in sql: Critiquing Date’s critique. ACM SIGMOD Record, 36(4):13–17, December 2007. См. также перевод: Клод Рубинсон. NULL, трехзначная логика и неопределенность в SQL: критика критики Дейта.
[9] D. Suciu and N. Dalvi. Foundations of probabilistic answers to queries. In Tutorial at SIGMOD’05, 2005. http://www.cs.washington.edu/homes/suciu/tutorial-sigmod2005.pdf.