СИСТЕМА И СПОСОБ ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ В СИСТЕМЕ АДМИНИСТРИРОВАНИЯ ИНФОРМАЦИОННО-ЗАВИСИМЫХ ОГРАНИЧЕНИЙ

1. Способ построения условно-зависимого вычислительного плана (102) для сети (100) информационно-зависимых ограничений, представленной двудольным графом (106), содержащим входные узлы-переменные (120), выходные, узлы-переменные (128) и узлы-отношения (114), причем входные узлы-переменные (120) и узлы-отношения (114) соединены дугами (110), при этом способ содержит следующие шаги:
задание, посредством спецификатора узла-переменной (120), по меньшей мере одного выходного узла-переменной (128), для которого необходим план (102); и
построение плана (102), посредством планировщика плана (102), от входных узлов-переменных (120) до выходного узла-переменной (128) посредством обратного поиска по ветвям двудольного графа (106).
2. Способ по п.1, дополнительно содержащий следующие шаги:
задание входных узлов-переменных (120), от которых необходимо построить вычислительные шаги плана (102) для вычисления значений выходного узла-переменной (128); и
построение плана (102) от всех входных узлов-переменных (120) в сети (100) ограничений, влияющих на значение выходного узла-переменной (128), если входные узлы-переменной (120) не заданы.
3. Способ по п.1, дополнительно содержащий следующие шаги:
задание, посредством спецификатора набора (140) пространств, набора (140) пространств, в котором необходим вычислительный план (102); и
построение набора (140) пространств, в котором выходной узел-переменная (128) находится в определенном состоянии, если набор (140) пространств не задан.
4. Способ по п.1, в котором шаг построения плана (102) включает:
создание входного списка (220), выходного списка (218), очереди заглушки и очереди плана (102), при этом
входной список (220) содержит связь входной (122) переменной с набором (140) пространств входной (122) переменной, причем набор (140) пространств входной (122) переменной является максимальным набором (140) пространств, в котором входная (122) переменная является независимой и одна или более выходных (122) переменных являются зависимыми от указанной входной (122) переменной в указанном наборе (140) пространств;
выходной список (218) содержит элементы, включающие связь узла-переменной (120) с максимальным набором (140) пространств, в котором этот узел-переменная (120) определен;
очередь плана (102) содержит список шагов плана (102) с элементами, включающими связь шага плана с набором (140) пространств, в котором этот шаг плана (102) должен быть выполнен;
причем шаг плана (102) содержит один из следующих элементов:
дугу (110), связанную со способом вычисления значения одного из узлов-переменных (120); и
компоненту (132), связанную с вычислительным способом одновременного вычисления значений множества узлов-переменных (120) в этой компоненте (132); и
очередь заглушки содержит элементы, являющиеся связью узла-переменной (120) заглушки с набором (140) пространств, при этом переменная (122) заглушки - это любая переменная (122), которая необходима в одном или нескольких шагах плана (102), но которая является независимой от любых конкретных входных (122) переменных, а набор (140) пространств, связанный с этой переменной (122) заглушки, является набором (140) пространств, в котором переменная (122) заглушки необходима, для того чтобы оценить один или несколько шагов плана (102).
5. Способ по п.4, который, если входные узлы-переменные (120) задаются как аргументы, дополнительно включает шаг
обновления входного списка (220) изменением набора (140) пространств, связанного с заданной входной переменной (122), посредством объединения формирующегося набора (140) пространств, полученного на маршруте поиска, с набором (140) пространств, связанным с указанной входной переменной (122); и
в котором шаг построения плана, использующего обратный поиск по ветвям двудольного графа (106), включает:
начало с выходного узла-переменной (128), причем этот выходной узел-переменная (128) имеет заданный набор (140) пространств и одну или более входных дуг (110); и
обновление выходного списка (218) посредством добавления выходного узла-переменной (128) и заданного набора пространств к выходному списку (218), если выходной узел-переменная (128) находится в определенном состоянии для всего заданного набора (140) пространств.
6. Способ по п.1, в котором этап построения плана (102) посредством обратного поиска по ветвям двудольного графа (106) включает:
обновление плана (102) во время продвижения по каждой из входящих дуг (110) обратно маршруту поиска посредством рекурсивного выполнения, для данного набора (140) пространств, следующих операций: поиск плана (102) для узла-переменной (120), поиск плана (102) для компоненты (132), поиск плана (102) для узла-отношения (114) и поиск плана (102) для дуги (110), при этом наборы пространств, предоставляющие возможность входящим дугам (110), связанным с заданным узлом-переменной (120), разъединяться;
поддержку, во время обновления плана (102), соответствующего набора (140) пространств на маршруте поиска посредством пересечения формирующегося набора (140) пространств с включенными наборами (140) пространств дополнительных элементов на маршруте поиска, причем дополнительные элементы являются узлами-переменными (120), компонентами (132), узлами-отношениями (114) и дугами (110); и
поиск, для каждой входящей дуги (110), плана (102) для компоненты (132), если входящая дуга (110) является частью компоненты (132), или плана (102) для узла-отношения (114), если входящая дуга (110) не является частью компоненты (132).
7. Способ по п.6, в котором шаг поиска, для каждой входящей дуги (110), плана (102) для компоненты или плана (102) для узла-отношения (114) включает:
поиск плана (102) для всех предшественников дуг (110) компоненты (132);
поиск плана (102) для всех входящих дуг (110) узлов-отношений (114); и
исключение зависимости набора (140) пространств от переменной состояния (124), причем переменная состояния (124) включает одну из следующих переменных: булеву переменную (122), категориальную переменную (122), имеющую дискретные значения на конечной области определения.
8. Способ по п.6, в котором шаг построения плана (102), использующего обратный поиск по ветвям двудольного графа (106), включает
обновление очереди плана (102) посредством добавления дуг (110) или компонент (132) и связанных наборов (140) пространств при следовании по маршруту поиска в обратном направлении сразу после достижения заданного входного узла-переменной (120) или после достижения независимого входного узла-переменной (120), если заданный входной узел-переменная (120) не предоставляется; и
в котором шаг построения плана (102) посредством обратного поиска по ветвям двудольного графа (106) включает:
выяснение, заканчивается ли любой маршрут поиска, начинающийся с предшествующей дуги (110) планового (102) шага, на заданном входном узле-переменной (120), и если это так, выполнение обновления очереди заглушки с помощью переменной (122) заглушки и связанного набора (140) пространств заглушки; при этом
переменная заглушки является переменной, связанной с любой другой предшествующей дугой (110), чьи маршруты поиска не заканчиваются на какой-либо из заданных входных переменных (122); и
набор (140) пространств заглушки содержит объединение наборов (140) пространств указанных поисковых путей.
9. Автоматизированная система для построения условно-зависимого вычислительного плана (102) для сети (100) информационно-зависимых ограничений, представленной двудольным графом (106), содержащим входные узлы-переменные (120), выходные узлы-переменные (128), и узлы-отношения (114), при этом узлы-переменной (120) и узлы-отношений (114) связаны дугами (110) и автоматизированная система включает:
спецификатор узла-переменной (120), сконфигурированный для задания узлов-переменных (120) в качестве входных данных, представляющих начальную точку вычислительного плана (102), и узлов-переменных (120) в качестве выходных данных, которые должны быть вычислены планом (102); и
планировщик плана (102), сконфигурированный для построения плана (102) от входных узлов-переменных (120) к выходным узлам-переменным (128) посредством обратного поиска по ветвям двудольного графа (106).
10. Система по п.9, в которой:
планировщик, если входные узлы-переменной (120) не заданы, конфигурируется для построения плана от всех входных узлов-переменных (120) в сети (100) ограничений, воздействуя на значение выходного узла-переменной (128);
и дополнительно включающая:
спецификатор набора (140) пространств, сконфигурированный для задания набора (140) пространств, в котором необходим вычислительный план (102); и
планировщик плана (102), если набор (140) пространств не задан, конфигурируется так, чтобы определить набор (140) пространств, в котором выходной узел-переменная (128) находится в определенном состоянии.
11. Система по п.9, в которой:
планировщик, сразу после построения плана, конфигурируется для предоставления входного списка (220), выходного списка (218), очереди заглушки и очереди плана (102), при этом
входной список (220) содержит связь входной переменной и набора (140) пространств, причем набор (140) пространств входной переменной является максимальным набором (140) пространств, в котором эта входная переменная является независимой и в котором одна или более выходных переменных (122) являются зависимыми от указанной входной переменной (122) в указанном наборе (140) пространств;
выходной список (218) имеет элементы, содержащие связь узла-переменной (120) с максимальным набором (140) пространств, в котором этот узел-переменная (120) определен;
очередь плана (102) содержит список шагов плана (102) с элементами, содержащими связь шага плана с набором (140) пространств, в котором шаг плана (102) должен быть выполнен;
шаг плана включает один из следующих элементов:
дугу (110), связанную со способом расчета значения одного единственного узла-переменной (120);
компоненту (132), связанную со способом одновременного вычисления значений множества узлов-переменных (120) в компоненте (132); и
очередь заглушки с элементами, содержащими связь узла-переменной (120) заглушки с набором (140) пространств, где переменная (122) заглушки - это любая переменная (122), которая необходима в одном или более шагах плана (102), но независима от любых заданных входных переменных (122), а набор (140) пространств, связанный с этой переменной (122) заглушки - это набор (140) пространств, в котором переменная (122) заглушки необходима для вычисления одного или нескольких шагов плана; и
планировщик плана (102), если входные узлы-переменные (120) заданы как аргументы, дополнительно конфигурируется для обновления набора (140) пространств, связанного с заданной входной переменной (122), посредством объединения формирующегося набора (140) пространств, полученного на маршруте поиска, с набором (140) пространств, связанным с этой входной переменной (122).
12. Система по п.11, в которой:
планировщик плана (102), во время обратного поиска по ветвям двудольного графа (106), конфигурируется для запуска с выходного узла-переменной (128), при этом выходной узел-переменная (120) имеет заданный набор (140) пространств и одну или несколько входящих дуг (110); и
планировщик, сконфигурированный для обновления выходного списка (218) посредством добавления выходного узла-переменной (128) и заданного набора (140) пространств к выходному списку (218), если выходной узел-переменная (128) находится в определенном состоянии для всего заданного набора (140) пространств.
13. Система по п.12, в которой:
планировщик плана (102), во время обратного поиска, конфигурируется для обновления плана в процессе следования по каждой из входящих дуг (110) обратно маршруту поиска посредством рекурсивного выполнения, для заданного набора (140) пространств, следующих операций: поиск плана (102) для узла-переменной (120), поиск плана для компоненты (132), поиск плана для узла-отношения (114) и поиск плана для дуги (110) - при этом наборы (140) пространств, которые активируют входящие дуги (110), связанные с заданным узлом-переменной (120), распадаются;
планировщик плана (102) конфигурируется для поддержи, в процессе обновления плана (102), подходящего набора (140) пространств по маршруту поиска посредством пересечения формирующегося набора (140) пространств с включенными наборами пространств дополнительных элементов на маршруте поиска, при этом дополнительными элементами являются узлы-переменных (120), компоненты (132), узлы-отношений (114) и дуги (110); и
планировщик плана (102), конфигурируется для поиска, для каждой входящей дуги (110), плана для компоненты (132), если входящая дуга является частью компоненты (132), или плана (102) для узла-отношения (114), если входящая дуга (110) не является частью компоненты (132).
14. Система по п.13, в которой:
планировщик плана (102) сконфигурирован для поиска плана (102) для всех дуг (110) предшественников компоненты (132), поиска плана (102) для всех входящих дуг (110) узлов-отношений (114) и исключения зависимости набора (140) пространств от переменной (124) состояния; и
при этом переменная (124) состояния содержит по меньшей мере одну из следующих переменных: булеву переменную (122), категориальную переменную (122), имеющую дискретные значения в конечной области определения.
15. Система по п.11, в которой:
планировщик плана (102), в процессе обратного поиска, конфигурируется для обновления очереди плана (102) посредством добавления дуг (110) или компонентов (132) и связанных наборов (140) пространств в порядке обратном маршруту поиска сразу после достижения заданного входного узла-переменной (120), или сразу после достижения независимого входного узла-переменной (120), если заданный входной узел-переменная (120) не предоставлен;
планировщик плана (102), в процессе обратного поиска, конфигурируется так, чтобы выяснить, заканчивается ли любой поисковый маршрут, начинающийся от предшествующей дуги (110) шага плана (102), в заданном входном узле-переменной (120), и, если это так, обновить очередь заглушки с переменной (122) заглушки и связанным набором (140) пространств заглушки;
переменная (122) заглушки является переменной (122), связанной с любой другой предшествующей дугой (110), чьи поисковые маршруты не заканчиваются на каких-либо из заданных входных переменных (122); и
набор пространств заглушки содержит объединение наборов (140) пространств на указанных маршрутах поиска.