Сложность удовлетворения ограничений

Сложность удовлетворения ограничений — это приложение теории вычислительной сложности к удовлетворению ограничений . Она в основном изучалась для различения поддающихся и неподдающихся регулированию классов задач удовлетворения ограничений в конечных областях.

Решение проблемы удовлетворения ограничений в конечной области в целом является NP-полной проблемой. Исследования показали ряд подслучаев полиномиального времени , в основном полученных путем ограничения либо разрешенных областей, либо ограничений, либо способа, которым ограничения могут быть размещены над переменными. Исследования также установили связь между проблемой удовлетворения ограничений и проблемами в других областях, таких как теория конечных моделей и базы данных .

Обзор

Установление того, имеет ли проблема удовлетворения ограничений в конечной области решения, является NP-полной проблемой в общем случае. Это простое следствие того, что ряд других NP-полных проблем можно выразить как проблемы удовлетворения ограничений. К таким проблемам относятся пропозициональная выполнимость и трехцветность .

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

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

Рассматриваемая исследовательская проблема касается существования дихотомий среди наборов ограничений. Это вопрос о том, содержит ли набор ограничений только полиномиальные ограничения и NP-полные ограничения. Для реляционных ограничений (см. ниже) этот вопрос был решен положительно для булевых областей теоремой Шефера о дихотомии ^[1] и для любой конечной области Андреем Булановым ^[2] и Дмитрием Жуком ^[3] независимо в 2017 году.

Ограничения

Поддающиеся решению подслучаи общей проблемы удовлетворения ограничений могут быть получены путем наложения соответствующих ограничений на проблемы. Были рассмотрены различные виды ограничений.

Структурные и реляционные ограничения:

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

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

Точнее, реляционное ограничение определяет язык ограничений , который является доменом и набором отношений над этим доменом. Задача удовлетворения ограничений соответствует этому ограничению, если она имеет именно этот домен и отношение каждого ограничения находится в заданном наборе отношений. Другими словами, реляционное ограничение ограничивает домен и набор удовлетворяющих значений каждого ограничения, но не то, как ограничения размещены над переменными. Вместо этого это делается структурными ограничениями. Структурное ограничение можно проверить, глядя только на области ограничений (их переменные), игнорируя их отношения (их набор удовлетворяющих значений).

Язык ограничений является разрешимым, если существует полиномиальный алгоритм, решающий все проблемы на основе языка, то есть использующий домен и отношения, указанные в домене. Примером разрешимого языка ограничений является язык бинарных доменов и бинарных ограничений. Формально это ограничение соответствует разрешению только доменов размера 2 и только ограничений, отношение которых является бинарным отношением. Хотя второй факт подразумевает, что области действия ограничений являются бинарными, это не является структурным ограничением, поскольку оно не запрещает накладывать какие-либо ограничения на произвольную пару переменных. Между прочим, задача становится NP-полной, если снять любое из ограничений: бинарные ограничения и тернарные домены могут выражать задачу 3-раскраски графа , в то время как тернарные ограничения и бинарные домены могут выражать 3-SAT ; обе эти задачи являются NP-полными.

Примером разрешимого класса, определенного в терминах структурного ограничения, является класс бинарных ациклических задач. Если задана задача удовлетворения ограничений только с бинарными ограничениями, ее связанный граф имеет вершину для каждой переменной и ребро для каждого ограничения; две вершины соединяются, если они находятся в ограничении. Если граф задачи ациклический, задача также называется ациклической. Задача выполнимости в классе бинарных ациклических задач является разрешимой. Это структурное ограничение, поскольку оно не накладывает никаких ограничений на область определения или на конкретные значения, которые удовлетворяют ограничениям; скорее, оно ограничивает способ наложения ограничений на переменные.

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

Единообразные и неединообразные ограничения

Подслучай, полученный путем ограничения до конечного языка ограничений, называется неоднородной проблемой . Эти проблемы в основном рассматриваются при выражении удовлетворения ограничений в терминах проблемы гомоморфизма, как поясняется ниже. Однородные проблемы также были определены в настройках проблем гомоморфизма; однородная проблема может быть определена как объединение (возможно, бесконечного) набора неоднородных проблем. Однородная проблема, составленная из бесконечного набора неоднородных проблем, может быть неразрешимой, даже если все эти неоднородные проблемы разрешимы.

Ограничения, основанные на деревьях

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

Это ограничение основано на первичном графе проблемы, который является графом, вершины которого являются переменными проблемы, а ребра представляют наличие ограничения между двумя переменными. Однако, управляемость может быть также получена путем помещения условия быть деревом к первичному графу проблем, которые являются переформулировками исходного.

Условия эквивалентности

Проблемы удовлетворения ограничений могут быть переформулированы в терминах других проблем, что приводит к эквивалентным условиям трактуемости. Наиболее используемая переформулировка — в терминах проблемы гомоморфизма .

Удовлетворение ограничений и проблема гомоморфизма

Связь между удовлетворением ограничений и теорией баз данных была представлена в форме соответствия между проблемой выполнимости ограничений и проблемой проверки существования гомоморфизма между двумя реляционными структурами. Реляционная структура — это математическое представление реляционной базы данных : это набор значений и набор отношений над этими значениями. Формально, , где каждое из них является отношением над , то есть набором кортежей значений . $A=(V,R_{1}^{A},\ldots ,R_{n}^{A})$ $R_{i}^{A}$ $V$ $V$

Реляционная структура отличается от проблемы удовлетворения ограничений, поскольку ограничение — это отношение и кортеж переменных. Также отличается способ их использования: для проблемы удовлетворения ограничений основной проблемой является нахождение удовлетворяющего назначения; для реляционной структуры основной проблемой является нахождение ответа на запрос.

Проблема удовлетворения ограничений, однако, связана с проблемой установления существования гомоморфизма между двумя реляционными структурами. Гомоморфизм — это функция от значений первого отношения к значениям второго, которая, будучи применена ко всем значениям отношения первой структуры, превращает его в подмножество соответствующего отношения второй структуры. Формально, является гомоморфизмом из в , если это функция из в такая, что, если , то . $ч$ $A=(V,R_{1}^{A},\ldots ,R_{n}^{A})$ $B=(D,R_{1}^{B},\ldots ,R_{n}^{B})$ $V$ $D$ $(x_{1},\ldots ,x_{k})\in R_{i}^{A}$ $(h(x_{1}),\ldots ,h(x_{k}))\in R_{i}^{B}$

Можно установить прямое соответствие между задачей удовлетворения ограничений и задачей гомоморфизма. Для данной задачи удовлетворения ограничений можно построить пару реляционных структур, первая из которых кодирует переменные и сигнатуры ограничений, вторая кодирует домены и отношения ограничений. Выполнимость задачи удовлетворения ограничений соответствует нахождению значения для каждой переменной, такого, что замена значения в сигнатуре делает его кортежем в отношении ограничения. Это возможно в точности в том случае, если эта оценка является гомоморфизмом между двумя реляционными структурами.

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

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

Конъюнктивная оценка и сдерживание запроса

Поскольку проблема гомоморфизма эквивалентна оценке конъюнктивного запроса и включению конъюнктивного запроса, эти две проблемы также эквивалентны удовлетворению ограничений.

Присоединяйтесь к оценке

Каждое ограничение можно рассматривать как таблицу в базе данных , где переменные интерпретируются как имена атрибутов, а отношение — это набор записей в таблице. Решения задачи удовлетворения ограничений являются результатом внутреннего соединения таблиц, представляющих ее ограничения; поэтому проблему существования решений можно переформулировать как проблему проверки того, является ли результат внутреннего соединения ряда таблиц непустым.

Теоремы дихотомии

Известно, что некоторые языки ограничений (или неоднородные проблемы) соответствуют проблемам, разрешимым за полиномиальное время , а некоторые другие, как известно, выражают NP-полные проблемы. Однако возможно, что некоторые языки ограничений не являются ни тем, ни другим. Из теоремы Ладнера известно , что если P не равно NP, то существуют проблемы в NP, которые не являются ни полиномиальными, ни NP-трудными. Для проблем ограничений с фиксированным языком ограничений и без структурных ограничений такие промежуточные проблемы не существуют, как доказали Андрей Булатов ^[2] и Дмитрий Жук ^[3] независимо в 2017 году. Если ни один язык Ладнера не выражается как проблема удовлетворения ограничений, множество всех языков ограничений можно разделить точно на те, которые определяют полиномиальное время, и те, которые определяют NP-полные проблемы; то есть это множество демонстрирует дихотомию .

Некоторые частные случаи результата Булатова и Жука уже были известны. Наиболее известным таким результатом является теорема Шефера о дихотомии , которая доказывает существование дихотомии в наборе языков ограничений на бинарном домене. Точнее, она доказывает, что ограничение отношения на бинарном домене является разрешимым, если все его отношения принадлежат одному из шести классов, и является NP-полным в противном случае. Булатов доказал теорему о дихотомии для доменов из трех элементов. ^[4]

Другая теорема дихотомии для языков ограничений — теорема Хелла–Несетрила, которая показывает дихотомию для задач на бинарных ограничениях с одним фиксированным симметричным отношением . В терминах проблемы гомоморфизма каждая такая задача эквивалентна существованию гомоморфизма из реляционной структуры в заданный фиксированный неориентированный граф (неориентированный граф можно рассматривать как реляционную структуру с одним бинарным симметричным отношением). Теорема Хелла–Несетрила доказывает, что каждая такая задача является либо полиномиальной по времени, либо NP-полной. Точнее, задача является полиномиальной по времени, если граф является 2-раскрашиваемым, то есть двудольным , и NP-полной в противном случае.

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

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

Журнал данных

Достаточное условие для трактуемости связано с выразимостью в Datalog . Запрос Boolean Datalog дает значение истинности набору литералов по заданному алфавиту, причем каждый литерал является выражением формы ; в результате запрос Boolean Datalog выражает набор наборов литералов, поскольку его можно считать семантически эквивалентным набору всех наборов литералов, которые он оценивает как истинные. $L(a_{1},\ldots ,a_{n})$

С другой стороны, неоднородную задачу можно рассматривать как способ выражения подобного набора. Для заданной неоднородной задачи набор отношений, которые могут использоваться в ограничениях, фиксирован; в результате им можно дать уникальные имена. Затем экземпляр этой неоднородной задачи можно записать как набор литералов в форме . Среди этих экземпляров/наборов литералов некоторые являются выполнимыми, а некоторые — нет; выполнимость набора литералов зависит от отношений, которые указаны неоднородной задачей. С другой стороны, неоднородная задача сообщает, какие наборы литералов представляют выполнимые экземпляры, а какие — невыполнимые. После того, как отношения названы, неоднородная задача выражает набор наборов литералов: тех, которые связаны с выполнимыми (или невыполнимыми) экземплярами. $R_{1},\ldots ,R_{n}$ $R_{i}(x_{1},\ldots ,x_{n})$

Достаточным условием трактуемости является то, что неоднородная проблема трактуема, если множество ее невыполнимых экземпляров может быть выражено булевым запросом Datalog. Другими словами, если множество наборов литералов, которые представляют невыполнимые экземпляры неоднородной проблемы, также является множеством наборов литералов, которые удовлетворяют булевскому запросу Datalog, то неоднородная проблема трактуема.

Локальная согласованность

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

Следующие условия используют первичный граф проблемы, который имеет вершину для каждой переменной и ребро между двумя узлами, если соответствующие переменные находятся в ограничении. Ниже приведены условия на бинарных задачах удовлетворения ограничений, где обеспечение локальной согласованности является поддающимся обработке и позволяет установить выполнимость:

обеспечение согласованности дуг, если первичный граф ацикличен;
обеспечение направленной согласованности дуг для упорядочения переменных, которое делает упорядоченный граф ограничений имеющим ширину 1 (такое упорядочение существует тогда и только тогда, когда первичный граф является деревом, но не все упорядочения дерева генерируют ширину 1);
обеспечение строгой направленной согласованности пути для упорядочения переменных, что делает первичный граф имеющим индуцированную ширину 2.

Условие, расширяющее последнее, справедливо для небинарных проблем удовлетворения ограничений. А именно, для всех проблем, для которых существует упорядочение, делающее первичный граф имеющим индуцированную ширину, ограниченную константой i, обеспечение сильной направленной i-согласованности является поддающимся обработке и позволяет установить выполнимость.

Условия, связанные с деревьями

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

Если первичный граф задачи ацикличен, установление выполнимости задачи является разрешимой проблемой. Это структурное ограничение, так как его можно проверить, глядя только на области действия ограничений, игнорируя их отношения и домен. Ациклический граф — это лес , но связность обычно предполагается; в результате обычно рассматривается условие, что первичные графы являются деревьями .

Это свойство древовидных задач удовлетворения ограничений используется методами декомпозиции , которые преобразуют задачи в эквивалентные, которые содержат только бинарные ограничения, организованные в виде дерева. Переменные этих задач соответствуют наборам переменных исходной задачи; область определения такой переменной получается путем рассмотрения некоторых ограничений исходной задачи, область действия которых содержится в соответствующем исходном наборе переменных; ограничения этих новых задач представляют собой равенство переменных, которые содержатся в двух наборах.

Если граф одной такой эквивалентной задачи представляет собой дерево, то задача может быть решена эффективно. С другой стороны, создание одной такой эквивалентной задачи может быть неэффективным из-за двух факторов: необходимости определения объединенных эффектов группы ограничений по набору переменных и необходимости хранения всех кортежей значений, которые удовлетворяют заданной группе ограничений.

Необходимое условие для сговорчивости

Доказано необходимое условие для трактуемости языка ограничений, основанного на универсальном гаджете . Универсальный гаджет — это частная проблема удовлетворения ограничений, которая изначально была определена для выражения новых отношений посредством проекции.

Универсальный гаджет

Отношение, отсутствующее в языке ограничений, может быть «симулировано» ограничениями, использующими отношения в языке. В частности, новое отношение может быть создано путем размещения набора ограничений и использования только некоторых из их переменных. Если все другие ограничения используют только эти переменные, этот набор ограничений заставляет эти переменные принимать только определенные значения, фактически имитируя новое отношение.

Каждая проблема удовлетворения ограничений и подмножество ее переменных определяют отношение, которое состоит из всех кортежей значений переменных, которые могут быть расширены на другие переменные для формирования решения. Технически это отношение получается путем проецирования отношения, имеющего решения в виде строк, на рассматриваемые переменные.

Универсальный гаджет основан на наблюдении, что каждое отношение, содержащее -кортежи, может быть определено путем проецирования отношения, содержащего все возможные столбцы элементов из домена. В качестве примера, следующие таблицы показывают такую проекцию: $к$ $к$

abcdefghbd--------------- ---1 1 1 1 0 0 0 0 -> 1 11 1 0 0 1 1 0 0 1 01 0 1 0 1 0 1 0 0 0

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

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

Например, если язык содержит бинарное отношение, представляющее булеву дизъюнкцию (отношение, содержащее все кортежи из двух элементов, которые содержат по крайней мере 1), это отношение помещается в качестве ограничения на и , поскольку их значения в таблице выше снова равны и . Поскольку все эти значения удовлетворяют ограничению, ограничение помещается. С другой стороны, ограничение с этим отношением не помещается на и , поскольку ограничение таблицы выше на эти две переменные содержит в качестве третьей строки, и эта оценка нарушает это ограничение. $а$ $б$ $(1,1)$ $(1,1)$ $(1,0)$ $б$ $д$ $(0,0)$

Универсальный гаджет порядка — это задача удовлетворения ограничений, содержащая все ограничения, которые можно разместить для получения таблицы выше. Решения универсального гаджета включают строки этой таблицы, но могут содержать и другие строки. Если решения — это в точности строки таблицы, каждое отношение можно выразить путем проецирования на подмножество переменных. Однако, даже если решения включают другие строки, некоторые отношения все равно можно выразить. Свойство универсального гаджета заключается в том, что он способен выразить путем проецирования каждое отношение, которое можно выразить путем проецирования из произвольной задачи удовлетворения ограничений на основе того же языка. Точнее, универсальный гаджет порядка выражает все отношения строк, которые можно выразить на языке ограничений. $к$ $к$ $к$

При наличии конкретного отношения его выразимость в языке можно проверить, рассмотрев произвольный список переменных, столбцы которых в таблице выше («идеальные» решения универсального гаджета) образуют это отношение. Отношение может быть выражено в языке тогда и только тогда, когда решения универсального гаджета совпадают с отношением при проекции на такой список переменных. Другими словами, можно проверить выразимость, выбрав переменные «как если бы» решения универсального гаджета были такими, как в таблице, а затем проверить, является ли ограничение «реальных» решений фактически тем же самым, что и отношение. В примере выше выразимость отношения в таблице справа можно проверить, посмотрев, являются ли решения универсального гаджета, ограниченные переменными и , в точности строками этой таблицы. $б$ $д$

Решения как функции в универсальном гаджете

Необходимое условие для трактуемости может быть выражено в терминах универсального гаджета. Решения такого гаджета могут быть представлены в виде следующей таблицы:

abcdefgh---------------1 1 1 1 0 0 0 01 1 0 0 1 1 0 0 (решения, которые существуют по определению)1 0 1 0 1 0 1 0---------------....1 0 0 1 1 1 0 0 (возможны другие решения)....

Эта таблица состоит из двух частей. Первая часть содержит решения, которые существуют по определению этой проблемы; вторая часть (которая может быть пустой) содержит все остальные решения. Поскольку столбцы таблицы по определению связаны с возможными -кортежами значений домена, каждое решение можно рассматривать как функцию от -кортежа элементов к одному элементу. $к$ $к$

Функция, соответствующая решению, может быть вычислена из первой части таблицы выше и решения. Например, для последнего решения, отмеченного в таблице, эта функция может быть определена для аргументов следующим образом: во-первых, эти три значения являются первой частью строки "c" в таблице; значение функции является значением решения в том же столбце, то есть 0. $1,0,1$

Необходимым условием для трактуемости является существование решения для универсального гаджета некоторого порядка, который является частью некоторых классов функций. Однако этот результат справедлив только для редуцированных языков, которые определены ниже.

Сжатие функций и сокращенные домены

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

Формально, если задано разбиение домена , содержащее по крайней мере набор размера больше единицы, то сжимающая функция — это функция, такая что для каждого в том же разбиении и для каждого кортежа она имеет место . $D_{1},\ldots ,D_{n}$ $D$ $s:D\rightarrow D$ $s(x)=s(y)$ $x,y$ $\langle x_{1},\ldots ,x_{n}\rangle \in R$ $\langle s(x_{1}),\ldots ,s(x_{n})\rangle \in R$

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

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

Необходимое условие для сговорчивости

Необходимое условие для трактуемости, основанное на универсальном гаджете, выполняется для редуцированных языков. Такой язык является трактуемым, если универсальный гаджет имеет решение, которое, если рассматривать его как функцию указанным выше способом, является либо постоянной функцией, либо функцией большинства, либо идемпотентной бинарной функцией, либо аффинной функцией, либо полупроекцией.

Ссылки

^ Шефер, Томас Дж. (1978). «Сложность проблем выполнимости». Симпозиум по теории вычислений 1978 г. С. 216–226. doi :10.1145/800133.804350.
^ ab Булатов, Андрей А. (2017). «Теорема дихотомии для неоднородных CSP». FOCS . С. 319–330.
^ ab Жук, Дмитрий (2017). ". Доказательство гипотезы дихотомии CSP". FOCS . стр. 331–342.
^ Булатов, Андрей А. (2006). «Теорема дихотомии для задач удовлетворения ограничений на множестве из 3 элементов». Журнал ACM . 53 (1): 66–120. doi :10.1145/1120582.1120584. S2CID 18220438.

Дехтер, Рина (2003). Обработка ограничений. Морган Кауфманн. ISBN 1-55860-890-7
Варди, Моше Й. (2000). «Удовлетворение ограничений и теория баз данных: учебник». Симпозиум по принципам систем баз данных 2000 г. , стр. 76–85.