\set ECHO none
\pset format unaligned

-- Recursive queries over cyclic data under the 'absorptive' provenance
-- class: the fixpoint stops once every minimal (tuple-repetition-free)
-- derivation is covered -- longer derivations are absorbed in any
-- absorptive semiring (Deutch, Milo, Roy & Tannen, ICDT 2014) -- and
-- the resulting tokens carry the 'absorptive' assumption marker.
-- Absorptive evaluations (probability, nonnegative min-plus) proceed
-- exactly; non-absorptive ones (counting, plain tropical) refuse.

SET provsql.provenance = 'absorptive';

-- Triangle 1->2->3->1 with a tail 3->4; probabilities and costs.
CREATE TABLE absr_edge(src int, dst int, p float8, cost float8);
INSERT INTO absr_edge VALUES
  (1,2,0.5,3),(2,3,0.5,4),(3,1,0.5,1),(3,4,0.5,5);
SELECT add_provenance('absr_edge');
DO $$ BEGIN PERFORM set_prob(provenance(), p) FROM absr_edge; END $$;
SELECT create_provenance_mapping('absr_cost', 'absr_edge', 'cost');

CREATE TABLE absr_r AS
  WITH RECURSIVE reach(node) AS (
      SELECT 1
    UNION
      SELECT e.dst FROM absr_edge e JOIN reach r ON e.src = r.node
  )
  SELECT node, get_gate_type(provenance()) AS root_type,
         get_extra(provenance()) AS assumption,
         round(probability_evaluate(provenance())::numeric, 6) AS prob,
         sr_tropical(provenance(), 'absr_cost', nonnegative => true)
           AS min_cost
  FROM reach;
SELECT remove_provenance('absr_r');
SELECT * FROM absr_r ORDER BY node;
DROP TABLE absr_r;

-- Non-absorptive evaluation refuses the tagged tokens: counting (the
-- number of derivations is genuinely infinite on cyclic data) and the
-- unrestricted tropical semiring (negative costs would make cyclic
-- min-cost unbounded).
CREATE TABLE absr_t AS
  WITH RECURSIVE reach(node) AS (
      SELECT 1
    UNION
      SELECT e.dst FROM absr_edge e JOIN reach r ON e.src = r.node
  )
  SELECT node, provenance() pv FROM reach;
SELECT remove_provenance('absr_t');
SELECT sr_counting(pv, 'absr_cost') FROM absr_t WHERE node = 4;
SELECT sr_tropical(pv, 'absr_cost') FROM absr_t WHERE node = 4;
-- Formula is not refused: it serialises the circuit rather than evaluating
-- it, so it renders the tagged sub-circuit as it is.
SELECT sr_formula(pv, 'absr_cost') IS NOT NULL AS formula_renders
  FROM absr_t WHERE node = 4;
-- ... and the nonnegative variant rejects negative costs.
CREATE TABLE absr_neg(v float8);
INSERT INTO absr_neg VALUES (-1);
SELECT add_provenance('absr_neg');
SELECT create_provenance_mapping('absr_negmap', 'absr_neg', 'v');
SELECT sr_tropical(provenance(), 'absr_negmap', nonnegative => true)
FROM absr_neg;
DROP TABLE absr_t;
DROP TABLE absr_neg;

-- Acyclic data under the 'absorptive' class: the reachability shape
-- routes through the decomposition-aligned compilation like any
-- other, so the tokens are tagged -- exact for absorptive evaluations
-- (min-plus below) and refused for counting.
CREATE TABLE absr_dag(src int, dst int, n int);
INSERT INTO absr_dag VALUES (1,2,1),(2,3,1),(1,3,1);
SELECT add_provenance('absr_dag');
SELECT create_provenance_mapping('absr_dagmap', 'absr_dag', 'n');
CREATE TABLE absr_d AS
  WITH RECURSIVE reach(node) AS (
      SELECT 1
    UNION
      SELECT e.dst FROM absr_dag e JOIN reach r ON e.src = r.node
  )
  SELECT node, provenance() pv FROM reach;
SELECT remove_provenance('absr_d');
SELECT node, get_gate_type(pv) AS root_type,
       sr_tropical(pv, 'absr_dagmap', nonnegative => true) AS min_cost
FROM absr_d ORDER BY node;
SELECT sr_counting(pv, 'absr_dagmap') FROM absr_d WHERE node = 3;
DROP TABLE absr_d;

-- Under the 'semiring' class the same acyclic recursion reaches the
-- structural fixpoint: the circuit is universal, untagged, and
-- counting works (2 derivations of node 3: direct and via the
-- shortcut).
SET provsql.provenance = 'semiring';
CREATE TABLE absr_d AS
  WITH RECURSIVE reach(node) AS (
      SELECT 1
    UNION
      SELECT e.dst FROM absr_dag e JOIN reach r ON e.src = r.node
  )
  SELECT node, get_gate_type(provenance()) AS root_type,
         sr_counting(provenance(), 'absr_dagmap') AS nb_derivations
  FROM reach;
SELECT remove_provenance('absr_d');
SELECT * FROM absr_d ORDER BY node;
DROP TABLE absr_d;
DROP TABLE absr_dag;
SET provsql.provenance = 'absorptive';
DROP TABLE absr_edge;

-- Absorptive folds: under the 'absorptive' class the load-time
-- simplification applies the rules sound in every absorptive semiring
-- (plus-idempotence, plus-with-one, plus-absorbs-times), marking the
-- rewritten gates; the value is unchanged for absorptive evaluations
-- and refused for the rest -- including when the fold collapses the
-- marked gate onto a preloaded input leaf.
CREATE TABLE absf_a(x int, c float8);
CREATE TABLE absf_b(x int, c float8);
INSERT INTO absf_a VALUES (1, 2.0);
INSERT INTO absf_b VALUES (1, 10.0);
SELECT add_provenance('absf_a');
SELECT add_provenance('absf_b');
DO $$ BEGIN PERFORM set_prob(provenance(), 0.5) FROM absf_a; END $$;
DO $$ BEGIN PERFORM set_prob(provenance(), 0.5) FROM absf_b; END $$;
SELECT create_provenance_mapping('absf_amap', 'absf_a', 'c');
SELECT create_provenance_mapping('absf_bmap', 'absf_b', 'c');
CREATE TABLE absf_map AS TABLE absf_amap UNION ALL TABLE absf_bmap;

-- plus(a, times(a, b)): 2 + 2*10 = 22 under 'semiring' counting...
SET provsql.provenance = 'semiring';
CREATE TABLE absf_u AS
  SELECT x FROM absf_a
  UNION SELECT absf_a.x FROM absf_a JOIN absf_b ON absf_a.x = absf_b.x;
CREATE TABLE absf_u_p AS
  SELECT x, sr_counting(provenance(), 'absf_map') AS cnt
  FROM absf_u GROUP BY x, provenance();
SELECT remove_provenance('absf_u_p');
SELECT * FROM absf_u_p;
DROP TABLE absf_u_p;
-- ... while under 'absorptive' the fold absorbs the times into its
-- dominating sibling: min-plus reads the (identical) min-cost, and
-- counting refuses the folded gate rather than returning 2.
SET provsql.provenance = 'absorptive';
CREATE TABLE absf_u_t AS
  SELECT x, sr_tropical(provenance(), 'absf_map', nonnegative => true)
    AS min_cost
  FROM absf_u GROUP BY x, provenance();
SELECT remove_provenance('absf_u_t');
SELECT * FROM absf_u_t;
DROP TABLE absf_u_t;
SELECT x, sr_counting(provenance(), 'absf_map') AS must_refuse
FROM absf_u GROUP BY x, provenance();
SELECT remove_provenance('absf_u');
DROP TABLE absf_u;
DROP TABLE absf_map;
DROP TABLE absf_amap;
DROP TABLE absf_bmap;
DROP TABLE absf_a;
DROP TABLE absf_b;

-- A tuple derived through itself on ACYCLIC data: the recursive term reads its
-- own rows through an outer join, so a null-padded row re-derives itself at
-- every round (a null key matches nothing), and the annotation gains a term
-- each round although the rows settle.  Plain SQL returns three rows, so this
-- is the same situation as cyclic data and not a divergence of the query:
-- the null-padded row is the one tuple of the recursion's equations derived
-- through itself, and it alone is a fixpoint, whose value the evaluating
-- semiring decides; the other two rows have ordinary circuits.
--   e = {(1,2), (2,3)}, both at p = 0.5, so over the four worlds
--   n=2 needs (1,2)            -> 0.5, one derivation
--   n=3 needs both             -> 0.25, one derivation
--   n=NULL needs (1,2), since 2 has no successor in {(1,2)} and 3 has none
--     in {(1,2),(2,3)}         -> 0.5, infinitely many derivations: the
--                                 count is refused
RESET provsql.provenance;
CREATE TABLE absp_e(src int, dst int);
INSERT INTO absp_e VALUES (1,2),(2,3);
SELECT add_provenance('absp_e');
DO $$ BEGIN PERFORM set_prob(provenance(), 0.5) FROM absp_e; END $$;
SELECT create_provenance_mapping('absp_one', 'absp_e', '1');
CREATE TABLE absp_r AS
  WITH RECURSIVE r(n) AS (
      SELECT dst FROM absp_e WHERE src = 1
    UNION
      SELECT x.dst FROM r LEFT JOIN absp_e x ON x.src = r.n)
  SELECT n, get_gate_type(provenance()) AS root_type,
         round(probability_evaluate(provenance())::numeric, 6) AS prob,
         provenance() AS tok
  FROM r;
SELECT remove_provenance('absp_r');
SELECT n, root_type, prob FROM absp_r ORDER BY n NULLS LAST;
DO $$
DECLARE r record; c text;
BEGIN
  FOR r IN SELECT n, tok FROM absp_r ORDER BY n NULLS LAST LOOP
    BEGIN
      c := sr_counting(r.tok, 'absp_one')::text || ' derivation(s)';
    EXCEPTION WHEN OTHERS THEN c := 'count refused';
    END;
    RAISE NOTICE 'n=%: %', coalesce(r.n::text, 'NULL'), c;
  END LOOP;
END $$;
DROP TABLE absp_r, absp_one;
SET provsql.provenance = 'absorptive';
CREATE TABLE absp_r AS
  WITH RECURSIVE r(n) AS (
      SELECT dst FROM absp_e WHERE src = 1
    UNION
      SELECT x.dst FROM r LEFT JOIN absp_e x ON x.src = r.n)
  SELECT n, get_gate_type(provenance()) AS root_type,
         round(probability_evaluate(provenance())::numeric, 6) AS prob
  FROM r;
SELECT remove_provenance('absp_r');
SELECT * FROM absp_r ORDER BY n NULLS LAST;
DROP TABLE absp_r;
SELECT remove_provenance('absp_e');
DROP TABLE absp_e;

-- The all-pairs closure of a cycle: every pair is derived through the cycle.
-- Expected: (1,2) 0.5 / 3, (2,1) 0.5 / 4, (1,1) and (2,2) 0.25 / 7.
CREATE TABLE absg_e(src int, dst int, p float8, cost float8);
INSERT INTO absg_e VALUES (1,2,0.5,3),(2,1,0.5,4);
SELECT add_provenance('absg_e');
DO $$ BEGIN PERFORM set_prob(provenance(), p) FROM absg_e; END $$;
SELECT create_provenance_mapping('absg_cost', 'absg_e', 'cost');
CREATE TABLE absg_r AS
  WITH RECURSIVE absg_pair(a, b) AS (
      SELECT src, dst FROM absg_e
    UNION
      SELECT r.a, e.dst FROM absg_e e JOIN absg_pair r ON e.src = r.b)
  SELECT a, b, round(probability_evaluate(provenance())::numeric, 6) AS prob,
         sr_tropical(provenance(), 'absg_cost', nonnegative => true) AS min_cost
  FROM absg_pair;
SELECT remove_provenance('absg_r');
SELECT * FROM absg_r ORDER BY a, b;
DROP TABLE absg_r;
SELECT remove_provenance('absg_e');
DROP TABLE absg_e;
DROP TABLE absg_cost;

RESET provsql.provenance;