67 std::vector<gate_t> stack{g};
70 std::unordered_map<gate_t, std::vector<typename S::value_type> > systems;
72 while(!stack.empty()) {
73 const gate_t u = stack.back();
91 "The requested semiring does not admit a homomorphism "
92 "from Boolean functions; this gate's wires were rewritten "
93 "under a Boolean-only rule (times-idempotence or "
94 "times-absorbs-plus, applied under the 'boolean' "
95 "provenance class) and the evaluation is unsound under "
96 "this semiring. Re-run under a more general provenance "
97 "class, or pick a Boolean-compatible semiring (boolean, "
98 "boolexpr, formula, ...).");
106 && !
semiring.compatibleWithBooleanRewrite())
108 "The requested semiring is not absorptive; this gate's "
109 "wires were rewritten under an absorptive rule "
110 "(plus-idempotence, plus-with-one absorber or "
111 "plus-absorbs-times, applied under the 'absorptive' or "
112 "'boolean' provenance class) and the evaluation is "
113 "unsound under this semiring. Re-run under the "
114 "'semiring' provenance class, or pick an absorptive "
115 "semiring (probability, boolean, nonnegative "
118 if(provenance_mapping.find(u) != provenance_mapping.end()) {
129 provenance_mapping.emplace(u,
semiring.one());
141 provenance_mapping.emplace(u,
semiring.zero());
170 const std::string assumption =
getExtra(u);
171 if(assumption.empty() || assumption ==
"boolean") {
172 if(!
semiring.compatibleWithBooleanRewrite())
174 "The requested semiring does not admit a homomorphism "
175 "from Boolean functions; the wrapped sub-circuit was "
176 "computed under a Boolean-provenance assumption "
177 "(typically by the safe-query rewrite, "
178 "provenance class 'boolean') and the evaluation is "
179 "unsound under this semiring. Re-run the query under "
180 "a more general provenance class, or pick a "
181 "Boolean-compatible semiring (boolean, boolexpr, "
183 }
else if(assumption ==
"absorptive") {
187 "The wrapped sub-circuit only represents the absorptive "
188 "quotient of a recursive query's provenance (fixpoint "
189 "truncation or compiled reachability circuit), whose "
190 "products are not in the order of the query, and the "
191 "requested semiring is not commutative. Re-run the "
192 "query under the 'semiring' provenance class.");
200 "The requested semiring is not absorptive; the "
201 "wrapped sub-circuit only represents the absorptive "
202 "quotient of a recursive query's provenance "
203 "(fixpoint truncation or compiled reachability "
204 "circuit), so its value is only defined for "
205 "absorptive semirings (probability, boolean, "
206 "nonnegative tropical, ...) and for formula, "
207 "which renders it as it is. Counting and why-provenance of such a "
208 "recursion are genuinely infinite: a tuple derived "
209 "through itself gains a derivation per round, which "
210 "cyclic data does and so does a null-padded row that "
211 "re-derives itself or a projection onto constants, on "
237 "Unknown assumption marker '" + assumption +
"'");
248 "gate_fixpoint must have exactly one child, a gate_fixsystem");
249 auto it = systems.find(w[0]);
250 if(it == systems.end()) {
251 it = systems.emplace(
254 w[0], std::make_shared<std::vector<typename S::value_type> >(it->second));
256 const unsigned idx =
getInfos(u).first;
257 if(idx < 1 || idx > it->second.size())
259 provenance_mapping.emplace(u, it->second[idx-1]);
266 "An equation system or one of its unknowns has no value of "
267 "its own; it is read through a gate_fixpoint");
274 "Comparison operator OID " +
287 if(provenance_mapping.find(c) == provenance_mapping.end()) {
295 const auto childValue = [&](
int i) ->
const typename S::value_type & {
296 return provenance_mapping.at(
getWires(u)[i]);
304 using V =
typename S::value_type;
305 std::vector<const V *> children;
307 children.push_back(&provenance_mapping.at(c));
309 const auto drop = [&children](
const V &e) {
310 children.erase(std::remove_if(children.begin(), children.end(),
311 [&e](
const V *x) { return *x == e; }),
316 provenance_mapping.emplace(u,
semiring.plus_of(children));
319 if(std::any_of(children.begin(), children.end(),
320 [&zero](
const V *x) { return *x == zero; }))
321 provenance_mapping.emplace(u, zero);
324 provenance_mapping.emplace(u,
semiring.times_of(children));
327 if(*children[0]==
semiring.zero() || *children[0]==*children[1])
328 provenance_mapping.emplace(u,
semiring.zero());
330 provenance_mapping.emplace(u,
semiring.monus(*children[0], *children[1]));
336 provenance_mapping.emplace(u,
semiring.delta(childValue(0)));
347 provenance_mapping.emplace(u, childValue(0));
354 provenance_mapping.emplace(u,
semiring.cmp(childValue(0), op, childValue(1)));
359 provenance_mapping.emplace(u,
semiring.semimod(childValue(0), childValue(1)));
368 std::vector<typename S::value_type> vec;
370 vec.push_back(provenance_mapping.at(c));
371 provenance_mapping.emplace(u,
semiring.agg(op, vec));
384 std::vector<typename S::value_type> vec;
386 vec.push_back(provenance_mapping.at(c));
387 provenance_mapping.emplace(u,
semiring.conditioned(vec));
403 const std::string key =
"L:";
404 std::size_t p = ex.find(key);
405 if(p != std::string::npos) {
406 std::size_t e = ex.find(
' ', p);
407 const std::string luid =
408 ex.substr(p + key.size(),
409 e == std::string::npos ? std::string::npos : e - p - key.size());
411 if(
getUUID(c) == luid) { lineage = c;
break; }
414 provenance_mapping.emplace(u, provenance_mapping.at(lineage));
416 provenance_mapping.emplace(u, childValue(0));
427 std::vector<typename S::value_type> vec;
429 vec.push_back(provenance_mapping.at(c));
430 provenance_mapping.emplace(u,
semiring.guarded_case(vec));
441 std::vector<typename S::value_type> params;
443 params.push_back(provenance_mapping.at(c));
453 "Arithmetic operator tag " +
456 std::vector<typename S::value_type> vec;
458 vec.push_back(provenance_mapping.at(c));
470 std::vector<double> probs;
471 std::vector<std::string> outcomes;
472 for(std::size_t i = 1; i < w.size(); ++i) {
473 probs.push_back(
getProb(w[i]));
476 provenance_mapping.emplace(
477 u,
semiring.categorical(childValue(0), probs, outcomes));
481 "gate_mixture must have exactly three children "
482 "[p_token, x_token, y_token]");
483 provenance_mapping.emplace(
484 u,
semiring.mixture(childValue(0), childValue(1), childValue(2)));
493 "gate_observe must have exactly one child (the observed leaf)");
494 provenance_mapping.emplace(u,
semiring.observe(childValue(0),
getExtra(u)));
507 if constexpr(std::is_same_v<typename S::value_type, std::string>) {
508 const std::size_t size = provenance_mapping.at(u).size();
511 "the formula is too large to return (over 1 GB): a sub-circuit "
512 "shared by several gates is written out at each of them");
520 return provenance_mapping.at(g);
526 using V =
typename S::value_type;
531 const std::size_t n = w.size() / 2;
533 std::unordered_map<gate_t, std::size_t> unknown;
534 for(std::size_t i = 0; i < n; ++i) {
537 "The first half of a gate_fixsystem's wires must be its "
538 "gate_fixvar unknowns");
539 unknown.emplace(w[i], i);
543 const auto plus2 = [&](
const V &a,
const V &b) -> V {
544 if(
semiring.equal(a, zero))
return b;
545 if(
semiring.equal(b, zero))
return a;
546 return semiring.plus(std::vector<V>{a, b});
548 const auto times2 = [&](
const V &a,
const V &b) -> V {
550 if(
semiring.equal(a, one))
return b;
551 if(
semiring.equal(b, one))
return a;
552 return semiring.times(std::vector<V>{a, b});
555 const auto times3 = [&](
const V &l,
const V &x,
const V &r) -> V {
556 return times2(times2(l, x), r);
563 std::unordered_map<gate_t, bool> dep;
565 std::vector<gate_t> st;
566 for(std::size_t i = n; i < w.size(); ++i)
569 const gate_t u = st.back();
570 if(dep.count(u)) { st.pop_back();
continue; }
573 if(!unknown.count(u))
575 "An unknown of another equation system occurs in this one");
576 dep.emplace(u,
true);
581 dep.emplace(u,
false);
587 if(!dep.count(c)) { st.push_back(c); ready =
false; }
609 std::vector<Term> terms;
611 std::unordered_map<gate_t, Lin> lin;
612 std::function<
const Lin &(
gate_t)> linear = [&](
gate_t u) ->
const Lin & {
613 auto it = lin.find(u);
619 "The requested semiring does not admit a homomorphism from "
620 "Boolean functions; a gate of this recursion's equations was "
621 "rewritten under a Boolean-only rule");
623 && !
semiring.compatibleWithBooleanRewrite())
625 "The requested semiring is not absorptive; a gate of this "
626 "recursion's equations was rewritten under an absorptive rule");
632 r.terms.push_back(Term{unknown.at(u), one, one});
638 const Lin &l = linear(c);
639 r.c = plus2(r.c, l.c);
640 r.terms.insert(r.terms.end(), l.terms.begin(), l.terms.end());
648 V kl = one, kr = one;
655 "This recursion's equations are not linear: a product "
656 "has two factors depending on the recursive relation");
663 const Lin &l = linear(var);
665 r.c = times3(kl, l.c, kr);
666 for(
const auto &t : l.terms)
667 r.terms.push_back(Term{t.j, times2(kl, t.l), times2(t.r, kr)});
673 const std::string assumption =
getExtra(u);
674 if((assumption.empty() || assumption ==
"boolean")
675 && !
semiring.compatibleWithBooleanRewrite())
677 "The requested semiring does not admit a homomorphism from "
678 "Boolean functions; part of this recursion's equations was "
679 "computed under a Boolean-provenance assumption");
680 if(assumption ==
"absorptive" &&
semiring.absorptive() &&
684 "Part of this recursion's equations was computed under an "
685 "absorptive assumption, whose products are not in the "
686 "order of the query, and the requested semiring is not "
687 "commutative. Re-run the query under the 'semiring' "
688 "provenance class.");
689 if(assumption ==
"absorptive" && !
semiring.absorptive()
690 && !
semiring.compatibleWithBooleanRewrite())
692 "The requested semiring is not absorptive; part of this "
693 "recursion's equations was computed under an absorptive "
708 std::string(
"This recursion's equations are not linear "
709 "semiring expressions in the recursive relation "
713 return lin.emplace(u, std::move(r)).first->second;
718 std::vector<V> b(n, zero);
719 std::vector<std::vector<Term> > in(n), out(n);
720 for(std::size_t i = 0; i < n; ++i) {
721 const gate_t f = w[n + i];
723 const Lin &l = linear(f);
725 for(
const auto &t : l.terms)
728 out[t.j].push_back(Term{i, t.l, t.r});
736 std::vector<std::vector<std::size_t> > comps;
738 std::vector<std::vector<std::size_t> > adj(n);
739 for(std::size_t j = 0; j < n; ++j)
740 for(
const auto &e : out[j])
741 adj[j].push_back(e.j);
745 std::vector<V> x(n, zero);
746 std::vector<std::size_t> comp_of(n);
747 for(std::size_t c = 0; c < comps.size(); ++c)
748 for(
const auto v : comps[c])
753 const auto better = [&](
const V &a,
const V &b) ->
bool {
757 for(std::size_t ci = 0; ci < comps.size(); ++ci) {
759 const auto &comp = comps[ci];
763 std::vector<V> entry;
764 entry.reserve(comp.size());
765 bool cyclic = comp.size() > 1;
766 for(
const auto i : comp) {
768 for(
const auto &t : in[i]) {
769 if(comp_of[t.j] != ci)
770 v = plus2(v, times3(t.l, x[t.j], t.r));
780 x[comp[0]] = entry[0];
787 for(
const auto i : comp)
788 x[i] =
semiring.symbolic_unknown(i + 1);
789 for(std::size_t k = 0; k < comp.size(); ++k) {
791 for(
const auto &t : in[comp[k]])
792 if(comp_of[t.j] == ci)
793 v = plus2(v, times3(t.l, x[t.j], t.r));
803 "This recursion's equations are cyclic (a tuple is derived "
804 "through itself), and the requested semiring is neither "
805 "absorptive nor gives the sum of the powers of a value: the "
806 "least solution is an infinite sum it has no value for.");
817 bool left_ok =
true, right_ok =
true;
818 for(
const auto i : comp)
819 for(
const auto &t : in[i])
820 if(comp_of[t.j] == ci) {
821 left_ok = left_ok &&
semiring.equal(t.r, one);
822 right_ok = right_ok &&
semiring.equal(t.l, one);
824 if(!left_ok && !right_ok)
827 "This recursion's equations put the recursive relation "
828 "between factors, or on both sides of them, and the "
829 "requested semiring is not commutative: its least "
830 "solution is not given by the star of a value. Write the "
831 "recursive relation at the same place of every recursive "
832 "FROM clause (first, or last).");
836 const auto mul = [&](
const V &a,
const V &b) -> V {
837 return right ? times2(b, a) : times2(a, b);
847 const std::size_t k = comp.size();
848 std::unordered_map<std::size_t, std::size_t> at;
849 for(std::size_t p = 0; p < k; ++p)
850 at.emplace(comp[p], p);
851 std::vector<std::map<std::size_t, V> > row(k);
852 std::vector<std::set<std::size_t> > col(k);
853 std::vector<V> e(entry);
854 for(std::size_t p = 0; p < k; ++p)
855 for(
const auto &t : in[comp[p]]) {
856 if(comp_of[t.j] != ci)
858 const V a =
semiring.commutative() ? times2(t.l, t.r)
860 const std::size_t q = at.at(t.j);
861 auto it = row[p].find(q);
862 row[p][q] = it == row[p].end() ? a : plus2(it->second, a);
866 std::vector<char> gone(k, 0);
867 std::vector<std::size_t> order;
868 for(std::size_t step = 0; step < k; ++step) {
870 std::size_t v = k, best = 0;
871 for(std::size_t p = 0; p < k; ++p) {
874 const std::size_t cost = row[p].size() * col[p].size();
875 if(v == k || cost < best) {
881 auto self = row[v].find(v);
882 if(self != row[v].end()) {
888 for(
auto &[j, b] : row[v])
891 for(
const auto p : std::vector<std::size_t>(col[v].begin(), col[v].end())) {
892 if(gone[p] || p == v)
894 const V c = row[p].at(v);
896 for(
const auto &[j, b] : row[v]) {
897 auto it = row[p].find(j);
898 const V t = mul(c, b);
899 row[p][j] = it == row[p].end() ? t : plus2(it->second, t);
902 e[p] = plus2(e[p], mul(c, e[v]));
907 for(std::size_t r = order.size(); r-- > 0; ) {
908 const std::size_t v = order[r];
910 for(
const auto &[j, b] : row[v])
911 val = plus2(val, mul(b, x[comp[j]]));
917 std::unordered_map<std::size_t, std::size_t> pos;
918 for(std::size_t k = 0; k < comp.size(); ++k) {
919 pos.emplace(comp[k], k);
920 x[comp[k]] = entry[k];
928 const auto worse = [&](
const std::pair<V, std::size_t> &p,
929 const std::pair<V, std::size_t> &q) {
930 return better(q.first, p.first);
932 std::priority_queue<std::pair<V, std::size_t>,
933 std::vector<std::pair<V, std::size_t> >,
934 decltype(worse)> heap(worse);
935 std::vector<char> settled(comp.size(), 0);
936 for(
const auto i : comp)
938 heap.emplace(x[i], i);
939 while(!heap.empty()) {
940 auto [v, j] = heap.top();
942 const std::size_t pj = pos.at(j);
943 if(settled[pj] || !
semiring.equal(v, x[j]))
946 for(
const auto &t : out[j]) {
947 const std::size_t i = t.j;
948 if(comp_of[i] != ci || settled[pos.at(i)])
950 const V w = plus2(x[i], times3(t.l, x[j], t.r));
957 }
else if(
semiring.exact_equality()) {
964 std::size_t nedges = 0;
965 for(
const auto i : comp)
966 nedges += in[i].size();
967 const std::size_t bound = (comp.size() + 1) * (nedges + 1);
968 std::size_t steps = 0;
969 std::vector<char> queued(comp.size(), 0);
970 std::deque<std::size_t> queue;
971 for(
const auto i : comp)
974 queued[pos.at(i)] = 1;
976 while(!queue.empty()) {
978 const std::size_t j = queue.front();
980 queued[pos.at(j)] = 0;
981 for(
const auto &t : out[j]) {
982 const std::size_t i = t.j;
987 "Value iteration over this recursion's equations does "
988 "not converge; the semiring does not behave "
990 const V w = plus2(x[i], times3(t.l, x[j], t.r));
993 if(!queued[pos.at(i)]) {
995 queued[pos.at(i)] = 1;
1007 for(std::size_t r = 1; r < comp.size(); ++r) {
1009 std::vector<V> next(entry);
1010 for(std::size_t k = 0; k < comp.size(); ++k)
1011 for(
const auto &t : in[comp[k]])
1012 if(comp_of[t.j] == ci)
1013 next[k] = plus2(next[k], times3(t.l, x[t.j], t.r));
1014 for(std::size_t k = 0; k < comp.size(); ++k)
1015 x[comp[k]] = next[k];