Expressing prefix sum

[amirsh]

It seems that the parser misses some features to express prefix sum.

Here are two versions that use MAX instead of SUM due to the earlier mentioned issue with typing SUM: #4

Stratified:

EDB_DECL:
arc(x int, y int)

IDB_DECL:
elems(x int, y int, w int)
presum_stratified(x int, y int)

RULE_DECL:
elems(t, t, w) :- arc(t, w).
elems(t, j, w) :- arc(t, _), arc(t-1, _), elems(t-1, j, w), 1 <= j, j < t.
presum_stratified(x, MAX(y)) :- elems(x, _, y).

Parser error:

line 10:34 no viable alternative at input 'arc(t-1'
line 10:34 no viable alternative at input 't-1'
line 10:34 missing '(' at '-1'
line 10:40 mismatched input ',' expecting ':-'
line 10:49 no viable alternative at input 't-1'
line 10:49 missing '(' at '-1'
line 10:58 mismatched input ',' expecting ':-'
line 10:66 mismatched input ',' expecting '('

Non-stratified:

EDB_DECL:
arc(x int, y int)

IDB_DECL:
presum(x int, y int)

RULE_DECL:
presum(x, MAX(y)) :- x=0, y=0.
presum(i, MAX(z+v)) :- presum(i-1,z), arc(i,v).

Parser error:

line 9:31 no viable alternative at input 'presum(i-1'
line 9:31 no viable alternative at input 'i-1'
line 9:31 missing '(' at '-1'
line 9:36 mismatched input ',' expecting ':-'
line 9:46 missing ':-' at '.'

[Hacker0912]

Hi Amir, thanks for your interest in RecStep - SUM used in the head of the Datalog rule should be supported (after some offline discussion and implementation on #4).

The issue was actually caused by i-1 in atoms like presum(i-1, z), using the Non-stratified one as an example. I don't think arithmetic expressions such as minus (e.g., (i-1)) are currently supported, neither in the head nor body atoms.

While supporting such binary expressions (e.g., A(a+b)) in the rule head might be doable (with no guarantee for convergence though - just as SUM, users will be responsible for that at the moment), supporting arbitrary mathematical expressions (e.g., A(a-b*a)) that are beyond binary ones does need some significant efforts. We have no plan to add that to RecStep any time soon due to the deprecation of the backend (i.e., QuickStep).

Supporting binary expressions in the rule body for recursion does look interesting. I will try to make your examples work when I get some time (no promise for the fully generalized version though).

I hope I explain well regarding the reported issues. Let me know if you need further help.

[Hacker0912]

Hi Amir,

After some effort, the support for the binary mathematical join (the name does not sound formal, but let's call it this way for now until you educate me on the more formal name) is finally here! As promised, I implemented features that support the simple binary cases (e.g., T(x, y), S(x-1, z); T(2+x, y), S(x, y)) - which should be enough to run the examples you provided.

To avoid messing up with the existing implementation since I do not have the bandwidth to perform a full functionality test - I put all the implementation supporting your provided rules in the new branch named binary_math_expr_join - so please just check out this repo to run your example.

For your convenience, I added the example Datalog programs (with the right RecStep syntax) you provided earlier under the directory benchmark_datalog_programs (both stratified and non-stratified examples; both SUM and MAX versions). You may notice that to make the prefix sum work, the corresponding attribute type of the relation is specified to be long null - a historical issue left by the backend QuickStep (well, it might not really be an issue - the team just didn't get the time to provide a simpler interface without hiding all the intricate details). I also added test data under Input named amir_example.

Here is an example command of running the stratified presum example with the example input:

recstep --program ./benchmark_datalog_programs/stratified_amir_presum_example.datalog --input ./Input/amir_example

After the execution completes, you should be able to see the output relation file named presum_stratified.csv since I also set the field write_to_csv in Output section of Config.json to be true.

I wish this is helpful and please let me know if you have further questions.