Запрос уникальности в Datalog?

Можно ли в Datalog написать запрос фактов, где имеется ровно одно значение одной из переменных для каждого возможного значения других переменных?

например найти все X такие, что есть только один X для каждого Y в expr(X, Y)


datalog
person Filip Haglund    schedule 25.10.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

  problem(y) <- expr(x1, y), expr(x2, y), x1 != x2.
  exactly_one_opt1(y) <- expr(_, y), !problem(y).

Большинство систем также поддерживают агрегирование, которое, вероятно, будет более эффективным решением, но синтаксис агрегирования не является стандартным для Datalog. Здесь я использую синтаксис LogiQL (LogicBlox Datalog):

  count[y] = c <- agg<<c = count()>> expr(_, y).
  exactly_one_opt2(y) <- count[y] = 1.
person Martin Bravenboer    schedule 25.10.2016
comment
Вы уверены, что первый из них является стандартным Datalog? Является ли отрицание стандартной функцией? - person Filip Haglund; 26.10.2016
comment
Формального стандарта не существует, но отрицание поддерживается всеми известными мне вариантами Datalog, поэтому я бы сказал, что вы можете считать это стандартной функцией. Этот пример здесь является очень простым использованием отрицания. Семантика отрицания становится сложной только тогда, когда отрицание используется в рекурсии (в большинстве систем реализовано нечто, называемое стратифицированным отрицанием) или когда переменная, используемая в отрицании, не связана положительно в правиле (известное как небезопасное отрицание). - person Martin Bravenboer; 27.10.2016