Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

упрощением D -системы и переходом к рассмотрению D -системы меньшей размерности, чем текущая. Состояние задачи в терминах введенных матрицеподобных структур полностью характеризуется с помощью совокупности доменов атрибутов, которые уже элиминированы из D -системы и самой D -системы, представ­ ляющей собой остаток, полученный из исходной D -системы в ходе присваиваний и применения правил редукции, которые представлены ниже утверждениями У1-У6. Если не все вершины дерева поиска являются тупиковыми, то решение записывается в виде совокупности доменов. Зачастую, пространство поиска может быть значительно редуцировано вообще без организации “ветвления” с помощью алгоритмов, преобразующих описание текущего состояния в эквивалентное ему более простое описание. Такие алгоритмы имеют полиномиальную оценку сложности. Далее уточним некоторые особенности процесса редуцирования прост­ ранства поиска на основе матричного представления конечных предикатов, а именно: 1. Каков признак того, что текущая ветвь поиска является тупиковой (соответствующее этой вершине текущее присваивание недопустимо)? 2. Как уменьшить размерность пространства поиска, не прибегая к ветвлению? 3. Что служит признаком успешного завершения процесса поиска? Для ответа на эти вопросы рассмотрим следующие утверждения, приводимые здесь без доказательств: Утверждение 1 (У1). Если хотя бы одна строка D -системы пуста (содержит все пустые компоненты), то D -система пуста (соответствующая система ограничений несовместна). Утверждение 2 (У2). Если все компоненты некоторого атрибута пусты, то данный атрибут можно удалить из D -системы (удаляются все компоненты, стоящие в соответствующем столбце). Утверждение 3 (УЗ). Если в D -системе есть строка (кортеж), содержащая лишь одну непустую компоненту, то все значения, не входящие в эту компоненту, удаляются из соответствующего домена. Утверждение 4 (У4). Если строка D -системы содержит хотя бы одну полную компоненту, то она удаляется (можно удалить соответствующее ограни­ чение из системы ограничений). Утверждение 5 (У5). Если компонента некоторого атрибута D -системы содержит значение, не принадлежащее соответствующему домену, то это значение удаляется из компоненты. Утверждение 6 (У6). Если одна строка D -системы полностью домини­ рует (покомпонентно содержит) другую строку, то доминирующая строка удаляется из D -системы. Ответ на первый из поставленных вопросов дает нам У1, то есть призна­ ком недопустимости частичного присваивания является пустота D -системы. Ответом на второй вопрос служат остальные утверждения, часть из которых позволяет исключать значения из доменов атрибутов (УЗ, У5) или даже сами атрибуты (У2), а часть позволяет исключать из рассмотрения лишние строки (У4, У6). 79