Действия над отношениями

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

Объединение ‑ отношение, содержащее все наборы значений пе­ременных, которые имеются либо в , либо в , или в обоих отноше­ниях.

Разностью называется отношение, содержащее наборы значе­ний переменных, содержащиеся в , но не содержащиеся в .

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

Соединение отношений. Оператор соединения из двух отноше­ний с диапазоном и с диапазоном строит новое отноше­ние, состоящее из их общих переменных в и . Набор из соединения отношений и можно построить, используя следующие шаги: (1) взять набор из ; (2) выбрать набор из такой, что компоненты и согласуются по переменным из , общим для и ; (3) образо­вать новый набор , комбинируя компоненты и , сохраняя лишь один из полученных одинаковых наборов. Диапазон получающегося отношения ‑ . Соединение двух отношений с одинаковыми диапазонами эквива­лентно пересечению этих отношений.

Виды ограничений

Рассмотрим различные виды ограничений. Простейшим типом ограни­чения является унарное ограничение, которое ограничивает значение единст­венной переменной. Каждое унарное ограничение можно устранить, выпол­няя предварительную обработку области определения соответствующей пе­ременной, чтобы удалить значения, нарушающие это ограничение. Бинарное ограничение связывает между собой две переменные, например, . Бинарной задачей УО называется задача, в кото­рой имеются только бинарные ограничения; она может быть представ­лена в виде графа ограничений. В ограничениях высокого порядка участвуют три или больше переменных. Одним из известных примеров таких задач яв­ляются криптоарифметические головоломки, называемые также числовыми ребусами (см. раздел 10.1.2). Обычно накладывается требование, чтобы каждая буква в криптоарифметической головоломке представляла отдельную цифру. В случае задачи SEND+MORE=MONEY из примера 10.7 раздела 10.1.2, такое требование может быть выражено с помощью ограничения с восемью переменными all-different(S, E, N, D, M, O, R, Y). Иным образом это требование может быть представлено в виде набора бинарных ограниче­ний, таких как .