ИЛИ оптимизация предикатов

Question 1

Предположим, у меня есть сущность с 3 атрибутами: A1, A2, A3 такие, что:

A1 может иметь только значения: 1, 2, 3
A2 может иметь только значения: 10, 20, 30, 40, 50
A3 может иметь только значения: 100, 200

И ряд правил, например:

R1: (A1 in (1, 2)) AND (A2 in (20, 40, 50)) AND (A3 IN (100))
R2: (A1 in (1, 3)) AND (A2 in (10, 30)) AND (A3 in (200))
R3: (A1 in (1, 2)) AND (A2 in (10)) AND (A3 in (100))

Тогда есть предикат: R = R1 or R2 or R3, что я хотел бы свести к минимуму. Дело в том, что A1=1 охватывает все возможные варианты A2 и A3, так что мы можем вынести это в отдельный пункт: R = (A1=1) or (the rest)

Я пробовал булевы методы минимизации, объявляя переменные как a=(A1=1), b=(A1=2), ..., k=(A3=200), однако это, похоже, не работает, потому что:

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

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

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

Вы когда - нибудь сталкивались с такой проблемой? Знаете ли вы лучшие способы ее решения? (эвристика тоже в порядке)

Question 2

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

Создайте 2 группы: одну для правил, которые принимают A3 = 100, и одну для правил, которые принимают A3 = 200. Правило может оказаться в обеих группах. Затем измените правило в группе таким образом, чтобы оно принимало значение только для группы, а не для другой.
Сгруппируйте эти группы снова по значениям A1, используя ту же логику.

В итоге вы получите расширенное выражение, подобное этому:

A3 = 100 AND (
    (A1 = 1 AND A2 IN (10, 20, 40, 50)) OR
    (A1 = 2 AND A2 IN (10, 20, 40, 50)))
OR A3 = 200 AND (
    (A1 = 1 AND A2 IN (10, 30)) OR
    (A1 = 3 AND A2 IN (10, 30)))

В основном мы строим дерево со значениями для A3 на глубине 1, значениями для A1 на глубине 2 и значениями для A2 на глубине 3. Если существует путь от корня до конца, использующий значения атрибутов, то правило заполнено полностью, в противном случае это не так.

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

Для вашего примера вы бы в конечном итоге получили это выражение:

A3 = 100 AND A1 IN (1, 2) AND A2 IN (10, 20, 40, 50) OR
A3 = 200 AND A1 IN (1, 3) AND A2 IN (10, 30)

Этот процесс довольно прост и может также сократить выражение, а не только оптимизировать его для оценки. Это может быть не идеально, но это может быть способом начать.

maraca · Answer 1 · 2021-11-22T20:45:00

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

Создайте 2 группы: одну для правил, которые принимают A3 = 100, и одну для правил, которые принимают A3 = 200. Правило может оказаться в обеих группах. Затем измените правило в группе таким образом, чтобы оно принимало значение только для группы, а не для другой.
Сгруппируйте эти группы снова по значениям A1, используя ту же логику.

В итоге вы получите расширенное выражение, подобное этому:

A3 = 100 AND (
    (A1 = 1 AND A2 IN (10, 20, 40, 50)) OR
    (A1 = 2 AND A2 IN (10, 20, 40, 50)))
OR A3 = 200 AND (
    (A1 = 1 AND A2 IN (10, 30)) OR
    (A1 = 3 AND A2 IN (10, 30)))

В основном мы строим дерево со значениями для A3 на глубине 1, значениями для A1 на глубине 2 и значениями для A2 на глубине 3. Если существует путь от корня до конца, использующий значения атрибутов, то правило заполнено полностью, в противном случае это не так.

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

Для вашего примера вы бы в конечном итоге получили это выражение:

A3 = 100 AND A1 IN (1, 2) AND A2 IN (10, 20, 40, 50) OR
A3 = 200 AND A1 IN (1, 3) AND A2 IN (10, 30)

Этот процесс довольно прост и может также сократить выражение, а не только оптимизировать его для оценки. Это может быть не идеально, но это может быть способом начать.

ИЛИ оптимизация предикатов

Вопрос

Лучший ответ

На других языках

Эта страница на других языках

Популярное в этой категории

Популярные вопросы в этой категории