CODEWITHSUNDEEP
datalog
Noah Watkins
Noah Watkins

Reputation: 5540

Building sequence in datalog

I'm using a version of datalog with negation. I'm trying to write a program that assigns increasing sequence numbers of each row in a relation. Example:

Given some EDB

items("a", "b") items("a", "c") items("b", "b")

I'd like to be able to generate the following IDB that assigns a sequence value to each row in items:

items_with_seq("a", "b", 0) items_with_seq("a", "c", 1) items_with_seq("b", "b", 2)

Upvotes: 0

Views: 94

Answers (2)

Quentin
Quentin

Reputation: 46

In Souffle datalog you could use the choice construct:

.decl items(x:symbol, y:symbol)
items("a","b").
items("a","c").
items("b","b").

// choice-domain is key here:
// - couples of (x,y) must be unique
// - seq must be unique
.decl items_with_seq(x:symbol, y:symbol, seq:number) choice-domain (x,y),seq
.output items_with_seq()

.decl items_size(n:number)
items_size(n) :- 
  n = count: {items(_,_)}.

items_with_seq(x,y,seq) :- 
  items(x,y),
  items_size(n),
  seq = range(0,n).

Outputs:

---------------
items_with_seq
x       y       seq
===============
a       b       0
a       c       1
b       b       2
===============

Alternatively if you only need unique identifiers instead of sequence numbers:

items("a","b").
items("a","c").
items("b","b").

.decl items_with_seq(x:symbol, y:symbol, seq:number) choice-domain (x,y)
.output items_with_seq()

items_with_seq(x,y,autoinc()) :-
    items(x,y).

Upvotes: 0

fingerprints
fingerprints

Reputation: 2960

The query evaluation in Datalog is based on first-order logic, for this reason, it has some limitations. It is not possible to characterize countability or uncountability in a first-order language.

Check Countability.

Upvotes: 0

Related Questions