Provenance in databases #
This Lean 4 library provides formal definitions and proofs relevant for provenance in databases, following the semiring framework of Green, Karvounarakis & Tannen and Green & Tannen.
One of the goals of this library is to provide a formal, machine-checked semantics for the provenance-aware relational database system ProvSQL described in Sen, Maniu & Senellart.
Contents #
Core theory
Provenance.SemiringWithMonus– definition of a semiring with monus (m-semiring), the algebraic structure underlying annotated database semantics, together with general theorems about itProvenance.Util.Kleene– Kleene's three-valued logic:Kleenewith its negation, conjunction and disjunction (the minimum and maximum offalse < unknown < true). Every law of a De Morgan algebra holds; what fails is the excluded middle, and exactly atunknown– a row on which a predicate is unknown is selected by neither the predicate nor its negation, which no two-valued reading can imitateProvenance.Util.ValueTypeNull– value domains with a null:ValueTypeNullextendsValueTypewith a null distinct from the domain's zero and null-strict arithmetic, andWithNull Tadjoins one value to any value type, strictness holding by construction.CompOp.eval3is the three-valued comparison,unknownas soon as an operand is null;CompOp.eval3_eq_true_iffrecovers the two-valued reading away from the null, andCompOp.negate_eval3says the operator negator is the three-valued negation – unconditionally, since at the null both readings areunknownand Kleene negation fixes it. A comparison isstrictwhen a null operand makes it unknown, whichCompOp.syneqandCompOp.synne– SQL'sIS [NOT] DISTINCT FROM– are not: they compare two values of the domain, two nulls being identical, and never returnunknown(CompOp.syneq_eval3_eq_true_iff). That is the equality grouping, partitioning, duplicate elimination and difference use, and the one the rewritings join onProvenance.Database– tuples, relations, and plain databasesProvenance.Query– relational algebra (select, project, join, union, difference…), with selections read in Kleene's three-valued logic:BoolTerm.eval3andSelection.eval3give the truth value,evalkeeps the rows on which it is true, and a row on which a predicate is unknown is kept by neither the predicate nor its negation (Selection.eval_not). Where nothing is null the reading is two-valued (Selection.eval3_ne_unknown,Selection.eval_not_iff). Beside the six comparisons the language hasBoolTerm.SYNEQandBoolTerm.SYNNE, SQL'sIS [NOT] DISTINCT FROM, the first written≐: they compare two values with two nulls identical, are never unknown, and are what a join on a key column needs. A term is an index or a constant combined by arithmetic, by SQL's searchedCASE(TermIn.caseWhen, whoseELSEis a term, so that the constructor asks nothing of the value domain) and byTermIn.coalesce: with those two, a guard that is a Boolean combination of comparisons needs no more – a conjunction is a nestedCASE, a disjunction aCOALESCE, a negationCompOp.negate. Also the aggregate catalogSeqAggFuncand the two of SQL's three input policies that a null makes visible:SeqAggFunc.sqlOf, the null-skipping one (SUM,MIN,MAX,AVG), which drops the nulls and givesNULLwhen nothing is left, andSeqAggFunc.counting, the counting one (COUNT(t)), which drops them and gives0– the third, null-keeping, being the aggregate itself.SeqAggFunc.Countssays what it takes for an aggregate to count – never null, and zero exactly over nothing but nulls – andcounts_countingsupplies it from the counting policy over a plain count.SeqAggFunc.countisCOUNT(*),COUNTover a term that is never null, and needs neither. On a domain where nothing is null the counting policy is the count itself (counting_of_noNulls). That is what the scalar convention needed and could not have – an aggregation without grouping over an empty input, and a frame excluding the row it is computed for, both read their value there, andSUM,MIN,MAXover no row areNULLand not the zero the domain happened to offer.COUNTstays unwrapped, being the one aggregate SQL does not read that way, andsqlOf_eq_of_no_nullrecovers the results proved over a domain with no null. Which aggregates read their input as a multiset is settled bySeqAggFunc.Symmetric:SUM,COUNT,MINandMAXare,sqlOfpreserves it, andPICKFIRSTis not (not_symmetric_pickFirst) – it is the aggregate for which the order a group or a frame is read in is the answer, and the reason the interface is a function on sequences at allProvenance.AnnotatedDatabase– databases annotated with values in an m-semiringKProvenance.QueryAnnotatedDatabase– semantics of relational algebra over annotated databases via m-semiring operationsProvenance.QueryAnnotatedDatabaseHom– evaluation commutes with m-semiring homomorphisms (Green, Karvounarakis & Tannen, Proposition 3.5; Geerts & Poggi, Proposition 1)Provenance.QueryAdequacy– data-part adequacy of the annotated semantics: forgetting annotations turns annotated evaluation into plain evaluation of the difference-stripped query, exactly on the positive fragment (the annotation-generic analogue of theℕ-adequacy theorem of Benzaken, Cohen-Boulakia, Contejean, Keller & Zucchini) and as a sub-multiset inclusion in general The general framework (primary)
The kind-indexed general syntax is the library's primary query
framework. Its three column kinds – regular values, aggregate tokens,
provenance values – mirror the three data types through which ProvSQL
enforces its own discipline (regular SQL values, agg_token, uuid), so
the system's scope restrictions on aggregate results (no deduplication,
difference or re-grouping over them) are static typing here, not a
formalization convenience. The classical query layer below remains the
proven engine several general results reuse internally.
Provenance.AggValue– symbolic aggregate tokens for the general (non-fused) HAVING semantics:AggValue T Kpackages an aggregate function with the ≼-sorted occurrence payload of its originating group, with the world-faithful (specialize), per-world (valOn) and deterministic (collapse) readings, the predicate provenance of a comparison against the token (predProv, agreeing withhavingProvon a group viapredProv_ofGroup), its scalar counterpartpredProvScalarsumming over all worlds, the empty one included, where the aggregate reads the empty sequence (valOn_empty) – the reading a row needs when it exists independently of its aggregate having anything to range over, the two differing by exactly that one term (predProvScalar_eq_predProv_add) – with the choice between them carried by the token's ownscalarfield, since a comparison may be far downstream of the operator that built it:ofGroupandofScalarGroupsettle it, the pushforward and the composite transport preserve it, andpredProvOfreads a token in its own convention, commuting with homomorphisms either way (predProvOf_mapAnn); the annotation pushforward (mapAnn), and lifted column valuesT ⊕ AggValue T Kmixing key and token columns. A count compared to zero collapses to a single reading:predProvScalar_count_eq_zerogives𝟙 ⊖ ⊕ᵢ αᵢwith no hypothesis onKat all – the comparison holds in the empty world and in no other, so there is no family of worlds to collapse (predProvScalar_of_only_empty) – andpredProvScalar_count_ne_zerogives⊕ᵢ αᵢunder absorptivity, the worlds it sums over being the non-empty ones, whichHaving.sum_ann_meetcollapses. Both are stated of an arbitrary occurrence family, so they hold of a family gathered from several sources as well as of one group. Two comparisons of one token are another matter: a predicate conjoining them multiplies their provenances, each summed over the worlds separately, andpredProvAnd(withpredProvScalarAnd,predProvOfAnd) names the joint sum over the worlds where both hold instead.predProvOf_mul_predProvOfsays the two agree exactly whenKis exclusive and its multiplication is idempotent –𝔹[X]has both,ℕis exclusive and not idempotent, and an absorptive domain such as Viterbi is not exclusive. It is the shape a truncation's range test and aHAVINGlikecount(*) > 2 AND count(*) < 5have. When the two atoms read disjoint families instead – several subquery conditions, say – what is needed is not that butcomplemented, the De Morgan law𝟙 ⊖ (a ⊕ b) = (𝟙 ⊖ a) ⊗ (𝟙 ⊖ b), under which a world's annotation splits along a partition of its family (Having.worldAnn_split).Having.relAnnis the relative form that composes, andrelAnn_split_unionsplits the union of two overlapping families into the shared part and the two private ones – the third regime, whose two known cases are its degenerate ones.Having.sum_mul_sum_of_splitis the disjoint case at the level of the sums rather than of one world: the product of the two families' world-sums is the single sum over the worlds of their union, needingcomplementedand nothing else, on the reindexingHaving.sum_splitof the worlds of a family by the pairs of worlds of its halves.Having.sum_mul_sum_of_overlapsettles the third regime, families that overlap without being equal: the same equality holds under the hypotheses of both settled cases, each on the part it governs –complementedsplits the two private parts off (sum_family_split,sum_split_of_union3), and exclusivity with an idempotent⊗collapses the shared part, which each side reads (relAnn_mul_eq_zero_of_ne). The disjoint case is where the shared part is empty and the same-family case where the private parts are, so the two known regimes are its degenerate ones. The The∨rule is not a decomposition at all: over two grouped families the⊕of the two atoms differs from the one-sum reading already in𝔹(bool_or_ne_joint), because a world of the disjunction must meet each family while the⊕fires where one group is empty – so what makes it sound is the row's group-existence factors, not the families' independence. The two hypotheses are independent:ℕis complemented and not multiplicatively idempotent (Nat.not_mulIdempotent), so it separates the same-family readings and leaves the disjoint ones alone. The domains that satisfy the same-family hypothesis are the exclusive ones whose⊗is idempotent, which of the catalog are𝔹,𝔹[X], lineage and interval union (Bool.mulIdempotent,BoolFunc.mulIdempotent,Which.mulIdempotent,IntervalUnion.mulIdempotent) – the lattice-like ones.predProvWithreads an arbitrary three-valued test on the token's value in place of a comparison, which is the form an atom takes once a range is one atom rather than two;predProvOf_mul_predProvOf_withis then the∧rule in its proper shape, a decomposition of one sum into two rather than a definition.Provenance.AggExpr– aggregate expressions, and with them what a predicate annotates: the joint evaluation of its Boolean function in every world.AggExpr.predProvis the⊕, over the worlds of the union of the families the expression reads, of the world's annotation times the truth of the comparison there; sincegmay be any deterministic function of SQL, a Boolean combination among them, this is one rule for∧,∨,¬, a Boolean-valued aggregate column and a searchedCASEalike, and it is the semantics – ProvSQL's too – that the structural rules ofGenPredIn.predsemare a short cut for: agreeing on an atom, a decomposition of the joint reading for∧under hypotheses, and not a theorem at all for∨, where the sum has to be computed instead. What a term that mentions a column of aggregate kind produces:AggExpris the formalg(a₁, …, a_p)– the function the term computes, applied to the aggregate values it reads, the regular ones being constants ofg– over one shared occurrence family, which is what makes the leaves answer together: two aggregates over the same group are read over the same occurrences, so an expression of them is not a function of their values separately. A world meets the occurrences of every grouped leaf and is free of the scalar ones (IsWorld, the case splitpredProv/predProvScalaralready make), the value there isvalOn, anddispis the displayed value: the reading in the family of occurrences the database as it is keeps, which is what SQL returns and is smaller thancollapseexactly where occurrences come through a difference or a rejected comparison.ofValueembeds a token as the expression of itself andpredProv_ofValue,collapse_ofValue,disp_ofValuesay the embedding changes no reading. A unary expression is again a token:AggValue.postcompreads a token's aggregate through a function, keeping its occurrences and its convention, andvalOn_ofUnarysays it reads in each world whatg(a)reads there – which is what a term over one aggregate column producesProvenance.Nested– nested aggregate values: what an aggregation builds when its term reads an aggregate column. Its occurrences are those of its own family together with those of every value it reads, at every storey, which anAggValuecannot hold – its reading consults its own list alone. A nested value is a tower:NestInner T K jis what an occurrence of a value of storeyjreads (an aggregate expression at storey0, and at storeyj + 1either something storeyjreads or a node,NestNode, aggregating a bag of storey-jvalues), andNestedValueis an outer aggregate over a bag of such occurrences. Everything is a bag:≼orders plain tuples, and an occurrence of a nested value carries a tuple with an aggregate column, so the family a nested value aggregates has no sequence to be listed in. Its aggregate is accordingly a function of a bag (SeqAggFunc.onBagmakes one of a symmetric aggregate). An occurrence is one object however many times it is read, so a world decides each family once: its own occurrences (root), each expression family by its key (leafKey) and each inner node by its key (NestNode.key);worldsenumerates the decisions off the bags, the steps being left-commutative, so nothing has to list the occurrences and nothing has to be proved invariant under relisting them. A world meets the family of each grouped inner value that it reads, which is to say along a path of present occurrences (World.IsWorld): an absent outer occurrence contributes nothing, and asking its inner family to be met would ask a group to be non-empty while the row carrying it is absent. The converse, barring a world from meeting a family no present occurrence reads (World.IsWorldCoherent), is refuted: it removes the world a valuation realizes, andWorld.IsWorldWithkeeps the predicate a parameter so that the refuted reading can be stated.valOn_fullsays the world with everything present reads as the collapse. A world's annotation isWorld.ann, the product of what is present at every storey times𝟙 ⊖the sum of what is absent, the monus taken once. The readings the value owes are there too:NestedValue.predProvWithandpredProvOffor a test of its value, andrealizedWorld/specializefor the world-faithful reading under a valuation – withspecialize_of_forallsaying the two agree where every occurrence is realized, andpredProvWith_of_neverthat a test no value satisfies annotates𝟘. The structure degenerates as it should:ofAggValuenests an ordinary token – a symmetric one, its aggregate becoming the outer one on the bag – by giving each occurrence an inner value that reads nothing (constInner), andann_worldOfsays a world of it (worldOf, from a subfamily of the token's own occurrences) carries exactlyHaving.worldAnnof the token's own family – so nesting adds weight only where something is actually nestedProvenance.JointFamily– two occurrence families as one, which is what a predicate reading two aggregate values reads. The two families are indexed separately, so the union is built:Having.catAnnconcatenates the annotation functions onFin (m + n),leftFam/rightFamare the parts inside it,catWorldpairs a world of each andleftPart/rightPartread them back, withcatWorldEquivandsum_catWorldre-summing a sum over the worlds of the union as the double sum over pairs. Reading a part of the concatenation is reading the family it came from and needs nothing ofK(relAnn_catWorld_leftand its twin); from that, a world of the union carries the product of its halves' annotations exactly whereKis complemented (worldAnn_catWorld).Having.jointPairis then what a predicate reading two tokens annotates – the⊕over the worlds of the union that meet each grouped family – andjointPair_eq_splitsays it is the split double sum in which such a reading is usually written, complementedness being what that costs.jointPair_and_constsays a test that does not depend on the world – a regular atom, reading no family – factors out of the joint reading, which is what makes a selection on regular columns transparent to a chain of aggregate selections.Having.row_absorb_singletonsettles the row-level absorption for two singleton grouped families: whereδis the identity and⊕is idempotent, the existence factors do absorb the∨rule's difference –⊗-idempotence collapsing the repeated factor where one test holds, whichδ = idgives free fromδ(x) ⊗ x = x, and⊕-idempotence the two copies where both do. Families of several occurrences are not covered, andChainFiveshows an idempotent⊕alone is not enough (chain_row_ne)Provenance.SubWorlds– the subfamilies of a listing as a bag (subWorlds, equal to the enumeration of the subsets of positions byuniv_map_eq_subWorlds), blind to a tie-block permutation of the listing once the selected occurrences are read through a map that cannot tell tied ones apart (subWorlds_tiePerm), and pushed through a map of annotations (subWorlds_map); an aggregate expression read off the occurrences a world selects (AggExpr.isWorld_iff_okSeq,valOn_eq_valSeq)Provenance.AggValueCongr– congruence of the token readings under tie-block permutations of the payload:TiePerm, the guarded analogue ofList.Permwhose swaps only exchange adjacent elements with equal sort keys (tiePerm_of_perm_of_sortedproduces one from two sorted permuted lists), a recursion form of the predicate provenance (AggValue.predProvAux, equal to the world-sum byAggValue.predProvWith_eq_predProvAux), and the congruences (AggValue.predProv_congr,collapse_congr,annSum_congr) making the annotation tie-break of the group sort semantically invisibleProvenance.AggQuery– the general (non-fused) HAVING semantics: kind-indexed queriesAggQueryover three column kinds – regular values, aggregate tokens, provenance values, ProvSQL's regular /agg_token/ uuid data types – enforcing the scope conditions statically (Gammaover all-regular inputs only, noDedup/Diffover token columns, normal-form projections and selections), the empty relationEmptyof arity0– the one leaf that belongs to the query and not to the instance, from which the unit relation (AggQueryIn.unit, its scalar aggregation with no aggregate: one empty tuple annotated𝟙, PostgreSQL'sSELECT;) and SQL'sVALUES(AggQueryIn.values, a union of projections of the unit onto constants, withevaluatePlain_valuesandevaluateAnnotated_valuesreading them) are derived, so a constant relation needs no leaf of its own – aggregation without grouping (GammaScalar, whose single row survives an empty input: annotated𝟙with no group-existence factor, its tokens read in the scalar convention), second-level aggregation (GammaNest: the term aggregated reads an aggregate column, so the column built is a nested token whose occurrences are the group's rows as a bag, each carrying the aggregate expression read there –Provenance.NestedExamplewrites it; an occurrence may itself carry a nested value, at any storey, a world deciding each inner occurrence once (NestedValue.World); the random world, the PQE results and the hom commutation ask nothing of it, andnoGammaNestis left excluding only the two syntactic token fences it is the counterexample to), the token-building groupingGammaTokand provenance aggregationProvSumof rewritten plans, the generalized selection grammarGenPredmixing regular and aggregate atoms (∧ ↦ ⊗,∨ ↦ ⊕,¬by operator complementation – the short cut the joint reading ofProvenance.AggExprlicenses, semiring permitting), and the general evaluatorAggQueryIn.evaluatewith factored row annotationsGenAnnimplementing the replace-the-δ-factor combination rule:Gammaleaves its group-existence factor pending, an aggregate selection supersedes exactly the compared groups' factors with the predicate provenance, and projections cash the factors of dropped token columns. Also the plain evaluatorAggQueryIn.evaluatePlain(classical filtering, aggregates computed over the whole group) and the strippingAggQueryIn.stripAgg. The two recursionsMu(SQL'sWITH RECURSIVE … UNION ALL) andMuSet(… UNION) bind a relation name to the previous round –AnnotatedDatabase.assign, a cons, since a database is searched front to back – and iterate:Musums its rounds,MuSetruns the fixpoint iteration ofε(q₀ ⊎ q₁). The two operators are partial: what each denotes is the value its rounds settle at – the sum up to the first empty round (muSumFix) and the first fixpoint of the iteration (muFix), both taken throughNat.sInf– and a recursion that does not settle has no value. Nothing in the syntax bounds the rounds: a recursion that stopped at a count rather than at its own rounds would not be this operator. Settling is a hypothesis,AggQueryIn.recSettles, which the four results that evaluate a recursion carry (adequacy, the homomorphism commutation, the random world and the PQE results off it); it also asksstep 0 = 0atMu, which is what makes an empty round a fixpoint – SQL buys it by requiring the recursive reference to occur in the body, and the bare syntax does not. The rounds carry their own lemmas (muSum,muIter,muSumFix,muFix,muSumFix_map,muFix_map,muSumFix_congr,muFix_congr), which is what carries adequacy, the random-world commutation and the homomorphism through them round by round. Taking the fixpoint makes the evaluatorsnoncomputable, so the worked examples check their values bydeciderather than printing them. Recursion is outside the (R1)–(R5) rewriting fragment (AggQueryIn.classical): a rewritten body carries the provenance column, so the bound name would have to be bound to the rewritten relation and the fixpoint would be over another schema. A projection column may also compute over one aggregate column (ProjColIn.aggTerm), which produces an aggregate column again – the unary aggregate expression ofProvenance.AggExpr– and is whatcount(*) + 1and the ranks need; over plain relations it is an ordinary term, and its token is the input's read through the function, so every reading of it is the input's read through the function too. Predicates are read three-valuedly throughout –GenPredIn.eval3,evalPlain3,HavingPred.evalOnSeq,GenPredIn.evalRew3– withholds,holdsPlain,holdsOnSeqandholdsRewkeeping the rows on which the predicate is true.Having.chicontributes𝟘to a provenance on an unknown comparison, andpredsemneeded no change at all: its polarity flag, the⊗/⊕swap at∧/∨and the operator negator at the atoms were already Kleene's reading (CompOp.negate_eval3). The window operatorWingives every row of its input a further column holding the aggregate over that row's frame: it removes no row, merges none and changes no annotation, so it creates no group and leaves nothing pending.AggQueryIn.evaluate_Win_eqandAggQueryIn.evaluatePlain_Win_eqread its output off the relation – the input mapped row by row, each row gaining the token (ValueFrame.tokenOf) or the value (ValueFrame.windowValue) that the relation gives it – which is the form every theorem about the operator uses. Every aggregating operator carries SQL'sFILTERclause:Gamma'skeep, one per aggregate,Win'skeep,WinExpr'skeeps, one per leaf of the expression, andGammaTok's in the rewritten world. A clause reads regular columns only, SQL forbidding an aggregate inside theFILTERof an aggregate, so its truth at an occurrence is the same in every world and survives any transport that keeps the data columns – which is why no result below asks anything about what a clause reads. What a clause may change is what its own aggregate reads, and nothing else: the worlds stay the group's or the frame's, every occurrence carrying its annotation to them, so the world in which only rejected rows are present is still a world and the aggregate readsf []there – which is the row SQL emits for a group whose rows the clause all rejects. A multi-frame window reads it that way:AggExprkeeps the group and the clause apart (AggExpr.inFrame, whichIsWorldasks about, andAggExpr.reads, which the value reads), andValueFrame.exprOfWhencuts only the second, so a clause that keeps everything is no clause. Every reading covers it with no new hypothesis: the deterministic one (ValueFrame.collapse_exprOfWhen), the pushforward (ValueFrame.occs_exprOfWhen– a clause tests the occurrence's own tuple, which a tie-block permutation does not move) and the random world (exprOfWhen_specialize, a restriction to a world not moving a row). A grouping reads it the same way, throughAggExpr.ofGroupWhen: one leaf over the whole group, whose clause cuts what it reads, soGamma's filtered column is an expression and not an ordinary token – which is whyAggQueryIn.evaluate_ordinaryTokensasks fornoFilter. A single-frame window reads it the same way (ValueFrame.exprWhen), with the kept part merged by value underDISTINCTand the rejected occurrences left unmerged and unread, so no clause anywhere cuts a family.chain_count_zero_when_nemeasures what a cut family cost, againstchainExprNone_zero,chainExprMixed_zeroandchainWinMixed_zerofor what the expression reading gives, andnatWinDistinct_ne_unmergedrecords that aDISTINCTaggregate's classes carry the⊕of their occurrences rather than deduplicating inside each world. A filtered aggregate builds an expression and not an ordinary token, soAggQueryIn.noFilteris whatAggQueryIn.evaluate_ordinaryTokensasksProvenance.AggQuerySubst– substituting the outer columns: the apply is defined by substitution – its right side is read, for each rowuof the left, as the closed queryq₂[u]– while the evaluators read it under an outer valuation, which is what makes them structurally recursive.AggQueryIn.substMapperforms the substitution (generally enough to close only the ambient part of a nested context, which is what passing under an apply needs) andAggQueryIn.evaluatePlain_substMapsays the two readings agree, so that reading the apply by substitution (AggQueryIn.evaluatePlain_Apply_subst) is a theorem about the evaluator rather than a second semantics; in the annotated semanticsAggQueryIn.evaluate_substMapholds for renamings of the outer columns, a constant in a parameter's place being no parameterProvenance.Occurrence– relations as families of occurrences:OccFam, a relation read as an indexed family rather than a multiset, so that two copies of a row are two occurrences. The row type is a parameter, since the rows a window produces carry a token where the rows it reads carry only values. A multiset discards that identity, which three things need: an operator that gives equal rows different results (a window frame excluding the row it is computed for reads its twin, not itself), a comparison reading two aggregate values whose occurrence families overlap, and a statement quantifying over the ways equal rows could be told apart.OccFam.toMultisetforgets the index andCongrsays when two indexings are the same family, so that an operator defined on families is meaningful exactly when it respectsCongr(toMultiset_congr). It sits besideAnnotatedRelationrather than replacing itProvenance.Frame– window frames determined by values:ValueFrame, a frame given by a relationρbetween order values and a predicatesdeciding whether an occurrence is in its own frame. Its point isframe_inter, the restriction property – the frame of an occurrence among the present rows is its frame in the whole relation intersected with them – which is what a positional frame lacks and what lets a window be read world by world.ContainsSelfnames the conditions o = ρ o o, under which membership stops mentioning the occurrence (mem_of_containsSelf) and the frame depends only on the tuple (frame_eq_of_key_eq); the frames that fail it are exactlyEXCLUDE CURRENT ROWandEXCLUDE TIES, which are exactly the ones needing occurrences told apart. The frames of SQL that are determined by values come in two families. Against the domain's own order on the order values:whole,upTo,before(the rows strictly preceding the current row's peers) andexcludeCurrent. Against an explicitORDER BY(Provenance.OrderSpec):rangeUpTo,rangeBefore, their mirrorsrangeFromandrangeAfter– which are the first two under the reversed clause (rangeUpTo_reverse,rangeBefore_reverse) –peerGroupand the modifiersexcludeGroupandexcludeTies, each classified byContainsSelf– and the classification lands where the general theory says it must,EXCLUDE GROUPkeeping a frame readable off the relation andEXCLUDE TIESnot. The two families agree where every column isASCand nothing is null (rangeUpTo_asc,rangeBefore_asc); theROWSframes with offsets are not among them and cannot be, since which row is the previous one depends on which rows are present.frameOfreads a frame off the relation rather than off an indexing – the rows of the partition the frame's relation accepts, the row's own copy taken out and put back exactly asssays – andframeSeq_eq_sortListproves the two readings agree, sotokenOfgives a token to a row of a relation with no indexing in sight. What a token actually holds isframeSeqOn, that sequence put into the order the window'sORDER BYasks for (Provenance.OrderSpec), the canonical order breaking the clause's ties;sortSeq_map_fstandsortSeq_mapAnnsay the clause survives forgetting the annotations and changing the semiring, since it reads only the rows. What that buys isframeOf_map(a map keeping the values carries every frame to the image of its frame: changing the semiring, or forgetting the annotations) andframeOf_filter(the restriction property again, on relations), which are what the window's metatheorems run onProvenance.Window– the token a window gives a row: the aggregate over that row's frame, built as a grouping builds one from its group, with the convention decided per row by whether the row is in its own frame (token,token_scalar_of_mem,token_scalar_of_not_mem). A row that is never reads its aggregate over nothing; a row that is not may have an empty frame in a world where it is itself present. The window removes no row, merges none and leaves every annotation alone, so no group-existence factor arises.windowis the operator itself, on families: every occurrence keeps its row and its annotation and gains its frame's token, andwindow_congrproves it well defined on occurrences rather than on indices – congruent inputs give congruent outputs, so nothing it produces depends on which indexing was chosen. That is the obligation the family reading exists to impose, and the reason two equal rows may legitimately receive different aggregates.windowRelapplies it to a relation by reading one as a family, andwindow_toMultiset_congrsays the answer is about the relation: exchanging two equal rows exchanges their tokens, so which of them receives which is not observable. That rests onOccFam.Congr_of_toMultiset_eq, proved fromList.Perm.exists_get_equiv– a permutation of rows gives a bijection of positions carrying one to the other, which Mathlib states only for lists without repeats.window_toMultiset_eqcashes the family reading into the relation reading the evaluator uses: the output is the input mapped row by row throughwindowRowProvenance.Notation– surface syntax for kind-indexed queries: a bracketedRA[ … ]with categories of its own for terms, predicates and queries, so that∧,∨,¬,<and=are read as the query language's and not as their meanings onProp, comparisons elaborate straight toGenPredatoms, column references#icarry their own regularity proof, andεand∖retag their argument to the all-regular kind vector their constructors ask for (allReg). A column reference says which column and not what is in it:atomAtandprojAtdecide by computation on the kind vector whether#iis a value comparison or an aggregate atom, a projected term or a token carried through, so the syntax of a query does not change with the kinds of its columns, as it does not in SQL. A grouping with no keys,γ[ ; t : f], is aggregation without grouping, the absence of aGROUP BYbeing what makes an aggregation scalar here as it is there. Grouping reads its keys and its aggregated columns as two lists,γ[#i, … ; t : f, …], the aggregates being ordinary Lean terms so that the catalog stays open; the same term syntax is read intoTermGunder a selection and into the classicalTermunder a grouping, which is what the aggregated columns of an all-regular input are. A window is written⊞[#i, … ; #j, … ; w ; t : f], the three lists before the aggregated column being the partition columns, the order columns and the frame – an ordinary Lean term, so that the catalog of frames stays open as the catalog of aggregates does. What a query costs to write is then the queryProvenance.AggQueryAdequacy– data-part adequacy of the general evaluator: forgetting the annotations ofQuery.evaluateAnnotatedyields the plain evaluation of the stripped query (AggQueryIn.evaluateAnnotated_toPlain), the aggregate tokens contributing through their deterministiccollapsereading and the fused group sequence projecting onto the plain one (havingGroup_map_fst). A window's added column is adequate for the same reason: its token collapses to the plain aggregate over the frame (ValueFrame.collapse_token), the frame projecting onto the plain frame because sorting annotated tuples and projecting is sorting the tuples (ValueFrame.sorted_map_fst)Provenance.OrderSpec– what anORDER BYorders by: a direction and a null placement per order column (OrderCol,OrderSpec), read lexicographically down the columns. It is a total preorder (OrderSpec.le_rfl,le_trans,le_total) and not an order: the values it does not separate are SQL's peers, and every null is a peer of every other whichever side the clause puts them on. Where every column isASCand nothing is null the clause is the library's own tuple order (OrderSpec.asc_le). Two things are defined from the clause that the domain's order cannot supply: the bound of a frame, which lives with the frames inProvenance.Frame, and the order a frame is read in –OrderSpec.readLe, the clause on the order values with the canonical order on rows breaking its ties, andOrderSpec.sortSeq, which puts a listing of a frame into it.sortSeq_tiePermis what makes the second usable: two listings of one frame come out related by a tie-block permutation whose blocks are the occurrences of one row, which is exactly the freedom every reading of a token is invariant under;map_eq_of_sortedis the working form andfilter_sortSeq_map_eqsays cutting a frame down to a possible world and sorting commute on the values read off. A window with noORDER BYisOrderSpec.unordered, which separates nothing, and its frame is read as a group is (ValueFrame.frameListOf_of_peer).OrderSpec.reversereads the clause backwards, direction and null placement together, which is whatlast_valuereads its frame inProvenance.Derived– the operators that add nothing: each is an abbreviation, a query of the basis, and its semantics – plain and annotated – is that of the query it abbreviates, so every theorem proved of the basis applies to it as it stands.padreplaces columns by the null (padRight,padLeftare what an outer join does to an unmatched arm);interis SQL'sINTERSECT, the two deduplicated arms joined on all their columns syntactically, which annotates a shared tuple by the product of the two⊕-sums – the provenance of a conjunction of the two memberships, and not whatε(q₁ - (q₁ - q₂))would give – all three characterized over plain relations (evaluatePlain_pad,evaluatePlain_inter,evaluatePlain_leftOuterand its companions, withmem_matchedLeft/mem_matchedRightsaying which rows of an arm have a match);leftOuter,rightOuterandfullOuteradd to the matching rows the unmatched ones of either arm, padded.semijoinandantijoinapply the left arm to the scalar aggregationmatchCountof the filtered right one, so that each occurrence of the left arm keeps its multiplicity – a grouping on its columns would merge duplicates, whichWHERE EXISTSdoes not – and so that a row with no match still has its row, with count𝟘; comparing that count against𝟘is what tells the two apart.firstValue,lastValue,lagandleadare the window operator withPICKFIRST: what tells them apart is the frame and the order it is read in, which the operator keeps separate because the frame is an argument of its own;nthValue,lagAtandleadAtare the same three overSeqAggFunc.pickNth, which reads a position of the frame other than its end – solastValuereverses the reading clause and leaves a clause-bounded frame bounded as it stands.rankis one plus the count over the rows the clause sorts strictly before the current row's peers, the+ 1being a term over the window's aggregate column (overWindow);evaluatePlain_ranksays so over plain relations.truncateisλ, the rank filtered to a range and the rank column dropped again (truncateFromfor an infinite count), which keeps a row tied with the last one kept – SQL'sFETCH FIRST c ROWS WITH TIES;evaluatePlain_truncate_noNullsreads it as the filter on the rank it is, anddistinctOnisλ^{P,O}_{0,1}, SQL'sDISTINCT ON. The range it filters on is a single atom,GenPredIn.aggRange, so its predicate provenance is the one⊕-sum over the worlds where the rank is in range (predsem_rankRange), with no hypothesis on the m-semiring – where a conjunction of two atoms would give the product of two sums. Noprovsql_havinggate carries a range, so the site rewriting is stated on range-free predicates (GenPredIn.rangeFree): the term it would emit denotes the product, which an evaluator may resolve back to the range's own sum by recognizing that the two gates read one family, but which the term itself does not denote.gammaSetsis SQL'sGROUPING SETS: the union of one aggregation per set of the family, each padded back onto the columns of the whole key, so that a key column a set drops reads as the null (gsRowsays which row each arm contributes).filterTermis SQL'sFILTERclause: the aggregated term read through aCASE, which the null-skipping and counting input policies then drop, so thatgammaFilterandwinFilterread exactly the occurrences the clause keeps (sqlOf_map_filterTerm,counting_map_filterTerm) while the group, its key and its annotation stay those of all the occurrences. A null-keeping aggregate is not covered: it reads the null as a value and so cannot tell a rejected occurrence from a null one. Over annotated relations the clause changes only what the token reads in each world (aggValOn_filterTerm_sqlOf,valOn_ofGroup_filterTerm_sqlOfand their counting companions inProvenance.DerivedAnn): the token carries every occurrence of the group, so its key and its existence factor are those of all of them.gammaDistinctandgammaScalarDistinctare SQL'sDISTINCTaggregates: deduplicate the key columns together with the aggregated term, then aggregate the added column, which annotates each distinct value by the⊕of the occurrences it stands for;evaluatePlain_gammaDistinctreads them over plain relations as the aggregate over the distinct values (SeqAggFunc.distinct), for a symmetric aggregate.distinctreads the distinct values sorted: deduplication leaves one value per class and not a sequence, so nothing but the values can fix the order, which is SQL's own rule –array_agg(DISTINCT t)is legal and ordered by the values, whilearray_agg(DISTINCT t ORDER BY u)is rejected – and it makesdistinct_symmetrichold of every aggregate. TheDISTINCTof a window aggregate is thedistflag theWinoperator carries: it merges the occurrences of a frame by value (AggValue.mergeByValue, one occurrence per class carrying the⊕of its members, the classes in the domain's order), which no reading of a token recovers, so the operator has to say it. Over plain relations it isSeqAggFunc.distinct(ValueFrame.collapse_tokenDist), and reading the classes in the domain's order is what makes it world-faithful with no condition on the aggregate – that order restricted to the classes a world holds is the world's own order (AggValue.specialize_mergeByValue,tokenOfDist_specialize). The metatheorems go through onclassSum_mapandmergeByValue_congr: the merge commutes with the annotation pushforward and is blind to a tie-block permutation of the payloadProvenance.DerivedAnn– what the derived operators annotate, which is what the choice of each definition is answerable for.annSumis the⊕-sum of the annotations a query gives one tuple, what duplicate elimination accumulates (evaluate_Dedup), andevaluateAnnotated_intersays intersection annotates a shared tuple by the product of the two sums – the provenance of a conjunction of the two memberships, whichε(q₁ - (q₁ - q₂))would not give. The reusable step isevaluateAnnotated_Proj: a projection carries the finalized annotation across, what it cashes of the pending group factors coming out of the pending part and into the concrete one. From it andevaluate_Diff– difference subtracts the⊕-sum of the annotations a tuple carries on the right, and removes no row – come the outer joins: a matching pair is annotated by the product, and a padded row byα ⊖ ⊕(α' ⊗ β)over the matches of every copy of its tuple (evaluateAnnotated_leftOuterand its right and full companions). That subtracted form is the definition;α ⊗ (𝟙 ⊖ ⊕β)equals it only when⊗distributes over⊖andKis absorptive. The semijoin and the antijoin read their row off one count site (evaluateAnnotated_countSite): a semijoin multiplies each occurrence of its left arm by the⊕-sum of the annotations of the rows it matches (evaluateAnnotated_semijoin, over an absorptiveK), an antijoin by𝟙 ⊖that sum (evaluateAnnotated_antijoin, over anyK) – the comparison being read in the scalar convention, so that no pending group factor is supersededProvenance.PlainBasis– which operators a query cannot do without:OpKindnames the classes an operator belongs to,AggQueryIn.usesOnlysays a query stays inside a set of them, andPlainEquivis agreement of the plain semantics on every instance. Six invariants bound a generating set from below, each with a query that breaks it: a query over the empty schema that uses no empty relation is impossible (usesEmpty_of_overSchema_empty), a projection-free query over duplicate-free relations has bounded multiplicities (count_le_multBound), a query with neither selection nor difference is empty on every instance or non-empty on every instance whose relations are all non-empty (zero_or_ne_zero_of_noSelDiff), a query with no product and no apply has a size linear in the instance (card_le_sizeBound), a union-free query over relations of at most one row has at most one row (card_le_one_of_thin), and an aggregation-free query is empty on the all-empty instance (evaluatePlain_eq_zero_of_allEmpty). Four operators are deliberately outside the classification – the two recursions, which the predicate reads asFalse, andGammaTokandProvSum, which belong to the rewritten world rather than to the language a source query is written in. The identities that generate the rest are proved asPlainEquivs: duplicate elimination from a grouping (dedup_plainEquiv_gamma), the difference from counts over a tagged union (diff_plainEquiv_notIn), a selection from two differences (sel_plainEquiv_selByDiff), the apply from a product where its right side reads no outer column (apply_plainEquiv_prod), and a window from an apply of a scalar aggregation (plainEquiv_winByApply). Two of them build their own syntax:GenPredIn.polTermreads a predicate whose atoms are comparisons as aCASEexpression over the same comparisons – the term the selection-from-difference needs, with both polarities, since in Kleene's logic a negation holds where its argument is false – andwinByApplywrites the window's frame as a selection against the current row, which the apply supplies as outer columns. The window's frame is asked to contain its current row, which is the hypothesis ofevaluatePlain_winByApplyOfand not of the decorrelationProvenance.Decorrelate– an apply read as a product: the construction of Galindo-Legaria and Joshi, proved rather than cited. Given a parameter relationPwhose rows are pairwise distinct, a query readingP's columns as parameters is turned into a closed query over the parameters and its own columns together, whose rows are the slicesRelation.slices P f = ⊎_{v ∈ P} {v} × f v(AggQueryIn.HasDecorrelation). Each operator carries the parameters along – a selection reads them as columns (GenPredIn.lift), a grouping takes them into its key (groupKey), a window into its partition (winPart), with the clause's order and itsFILTERshifted over the block (GroupOrder.lift,Selection.shift) – and the apply itself recurses, with duplicate elimination of its left side's decorrelation as the new parameter relation, its two blocks swapped into the order the right side reads its context in (Relation.swapBlocks), joined back on those columns so that the multiplicities duplicate elimination dropped are restored (Relation.applyJoin_slices).hasDecorrelation_of_usesOnlyassembles the cases, andexists_applyFree_plainEquivis the closed-query corollary, over the unit as the parameter relation: every query of the fragment is plain-equivalent to one with no apply. The target class set is a parameter throughout (decorrOpsbeing what the construction itself needs, beyond the classes the query already uses), which is what lets the result be composed with the other passes: a query with no window decorrelates to one with no window, and a nine-class target would not record thatProvenance.AllRegular– reading every column as a value: in the plain semantics every column holds a value of the domain, the kind vector being a syntactic index, andAggQueryIn.exists_allRegmakes that into a theorem – every query is plain-equivalent to one all of whose columns are regular, using the same classes and naming the same relations.AggQueryIn.Explodeis the bridge (it reads an aggregate column as a key and is the identity over a plain relation) andAggQueryIn.Retagthe one for a provenance column;explodeBelowapplies them column by column. Three readings of an aggregate column have exact regular counterparts –GenPredIn.toRegtakes an aggregate atom to the same comparison and a range atom to its two,ProjColIn.toRegtakes a column read as a token to the column – and two things have none, whichAggQueryIn.Retypablefences off: a projection column post-composing an aggregate with an arbitrary function (ProjColIn.aggTerm), and a non-determinate window over aggregate columns. A window is the one operator whose plain semantics reads the kind vector: it reads its input throughColKind.readTuple, nulling the aggregate columns, which is one of the listings of a frame that its order clause allows. Reading an aggregate column as a value puts it into the tie-break, so the re-typed window lists a block of peers in another order – immaterial to a determinate window, which is all the semantics admits, and visible to one the semantics refuses. The fence is therefore determinacy itself, quantified over the instance asAggQueryIn.recSettlesis, or an all-regular input (ValueFrame.windowValueOpt_readTuple_of_det, withwindowValue_readTuplethe symmetric unfiltered case), and aFILTERclause is carried through on the condition that it read the occurrence's regular columns, as a clause does in SQL, which forbids an aggregate inside theFILTERof an aggregate. What the theorem leaves behind isAggQueryIn.SwapReady, which is what the two swaps of the basis ask forProvenance.Determinacy– the listing an aggregate reads, and the query that is refused: an aggregate reads its group, or a window's frame, as a sequence that its clause only partly fixes, and a query is determinate where the listing cannot matter – each aggregate symmetric, or its term constant on the rows the clause ties.ValueFrame.windowValue_eq_of_listingandRelation.groupSeqOrd_map_eq_of_listingsay the listing is then invisible (offList.map_eq_of_pairwise_of_symm, two sorted listings of one bag reading alike, andOrderSpec.peer_of_readLe, mutual comparability being peerhood);AggQueryIn.DeterminateOnis the condition, quantified over the instance asrecSettlesis; andAggQueryIn.evaluateCheckedis the evaluator that answers where it holds and refuses where it does not, withwindowValue_eq_of_listing_of_determinateOnandgammaAgg_eq_of_listing_of_determinateOnsaying what its answer means.AggQueryIn.evaluatePlainkeeps its own listing – one the condition admits – which is why no result of the metatheory asks for determinacy: each relates two readings of one listing. The one place two listings meet is the re-typing ofProvenance.AllRegular, whose window fence is this conditionProvenance.BasisAssembly– the basis, assembled: every plain query is equivalent to one over six classes, as three passes over the syntax.AggQueryIn.exists_winFreereplaces every window by an apply of a scalar aggregation,AggQueryIn.exists_applyFree_plainEquiv(the decorrelation) replaces every apply by a product, andAggQueryIn.exists_basisOps_of_dedupDiffreplaces the duplicate elimination and the difference the decorrelation leaves behind;AggQueryIn.exists_basisOps_plainEquivcomposes them, so every query of the plain fragment is equivalent to one over the six classes∅,Π,σ,×,⊎,γ. The order of the passes is forced, and each is stated with its target class set as a parameter – which is why the decorrelation had to be parameterized too: a pass may only be composed with the next if what it produces is known not to contain what the previous one removed.GeneratesOnreads the conclusion as a property of a set of classes,basisOps_generatesOnsays the six have it, and the rows below are the converse, from the invariants ofProvenance.PlainBasisand their witnesses. Each pass also carriesAggQueryIn.overSchema: the query it produces names the relations the query it is given names, which is what the other half needs – two of the six rows (∅andσ/−) are necessary only for a query over the schema, a reference to a name the schema does not declare reading the empty relation. The six rows areproj_mem_of_generatesOn,union_mem_of_generatesOn,gamma_mem_of_generatesOn,prod_or_apply_mem_of_generatesOn,empty_mem_of_generatesOnandsel_or_diff_mem_of_generatesOn, each over the schema its witness lives on. Three of them hold of the whole algebra: forσ/−,AggQueryIn.NonzeroOn, the dichotomy relative to a set of names forced empty, is what carries the invariant through a set recursion; forΠ,AggQueryIn.affine_of_bodysays that a recursive term without a projection reads the recursive relation tuple by tuple, so a bag recursion settles only at its base; for×/apply,AggQueryIn.pointwise_of_bodysays that without them a recursive term maps each row to at most one row, and in a signature without functions on values (AggQueryIn.recNoFun) the orbit of a row stays in a box of a size the query fixes (rowBox,recBound), so the rounds a recursion can run are bounded (optIter_exists_lt,optIter_ne_none). In all three,AggQueryIn.SettlesAt– the recursions settle at this instance – is the one hypothesis a statement about a recursion's value needs, and the typing ofAggQueryIn(a recursive term reads its hole once, underΠ,σ,×, the left of an apply or⊎) is the restriction on a recursive term.GeneratesOnasks the set of classes to hold no recursion, so the query it produces settles everywhere, as the plain query it stands for does. What a window has to be for the first pass to reach it isAggQueryIn.WinsDerivable: its frame contains its current row, its input is all-regular, a predicate of the language holds exactly where its frame condition holds and itsFILTERclause keeps the row, and it is not a multi-frame window – whose column no term expresses.DISTINCTand the clause themselves are covered, the derived form aggregatingf^distinctwhere the window does and reading the clause in the selection that spells the frame out (evaluatePlain_winByApplyOf). The predicate itself is built for three frames – the whole partition, and the twoRANGEframes read against the clause where nothing is null (AggQueryIn.winsDerivable_win_whole,_rangeUpTo,_rangeBefore, offOrderSpec.lePredOn/ltPredOn, the clause's lexicographic comparison as a predicate, andSelection.toPredIn, a classical selection read in a context). What blocks the null branches is that the predicate language has comparisons andIS NOT DISTINCT FROMbut noIS NULLatom, there being no null constant inValueType. The two swaps –−forσ, the apply for×– are the passesAggQueryIn.exists_selFreeandAggQueryIn.exists_prodFree, which askAggQueryIn.SwapReadyof their input: a selection's input and a product's left factor with regular columns, whichProvenance.AllRegularprovides. Composing them gives the three alternative bases:AggQueryIn.exists_basisDiffOps_plainEquivover{∅, Π, ×, ⊎, γ, −},AggQueryIn.exists_basisApplyOps_plainEquivover{∅, Π, σ, apply, ⊎, γ}and – both swaps at once –AggQueryIn.exists_basisApplyDiffOps_plainEquivover{∅, Π, apply, ⊎, γ, −}, each the three passes, then the re-typing, then the swap or swaps, withbasisDiffOps_generatesOn,basisApplyOps_generatesOnandbasisApplyDiffOps_generatesOntheirGeneratesOnforms. What lets the two swaps compose isAggQueryIn.swapReady_selByDiff: the difference a selection becomes introduces neither a product nor a selection. None of the three asks anything of its input beyond what the six-class statement asks – that the columns re-type is part ofAggQueryIn.usesOnly, which reads a column over an aggregate column as a term (ProjColIn.aggTermOf) and refuses the rewritten world's arbitrary function, as it refusesGammaTokandProvSum. The basis that holdswinisAggQueryIn.exists_basisWinOps_plainEquivover{∅, Π, σ, ×, ⊎, γ, win}, two passes and no hypothesis about windows at all: nothing has to rewrite one, the decorrelation carrying a window of every frame and the third pass keeping it. The window class is necessary there (EXCLUDE CURRENT ROW,win_mem_of_generatesOnRec); the six-class statements are the stronger claim, about the windowsevaluatePlain_winByApplyOfderivesProvenance.RecursionBasis– the recursions in a basis:μ^⊎, which in the minimal signature is in every basis because a bag recursion counts the derivations of a tuple. The witness is a chain ofndiamonds –diamondEdges,4ndistinct edges overdChain n, an instance of4n + 1rows with no duplicate – and the queryμ^⊎R.(S, Π_{#3}(σ_{#1=#2}(R × E)))(chainWitness).evaluatePlain_reachStepreads one round as the successors of the previous one,chainStep_iterate_evenandchainStep_iterate_oddcompute the rounds as the layers of the graph (the entry node of diamondicarrying2ⁱcopies, one per path),muSettles_chainsays the rounds end,count_chainWitnessgives the sink2ⁿcopies, andchainWitness_no_polynomial_boundis the row: noc · (n+1)^kbounds that.GeneratesOnRecis generation over the whole algebra in the minimal universe𝒜(∅, {count}), where a query is a partial function of the instance: the query produced settles and agrees wherever the given one settles. The rows against it areempty_,gamma_,sel_or_diff_,proj_,prod_or_apply_andmuBag_mem_of_generatesOnRec;⊎is not a row, being derivable (Provenance.SumByMu). The last rests onAggQueryIn.exists_polyBound_rec, which bounds the rows of a query withoutμ^⊎polynomially, set recursions included, by one induction carrying the card and the values of a result together – a set recursion's fixpoint is duplicate-free over a value set of polynomial size, and every count inside a recursive term is read off the instance the recursion started from. The signature the row is stated in isAggQueryIn.inMinimalSigofProvenance.PlainBasisProvenance.SumByMu–⊎fromμ^⊎: with a bag recursion the union is a derived operator, so⊎, necessary in a basis of the recursion-free fragment, is not necessary in one of the whole algebra.AggQueryIn.sumByMuis the construction (two bag recursions over a one-row driver, each reading one operand once through a phase tag;evaluatePlain_sumByMusays it isq₁ ⊎ q₂,settlesAt_sumByMuthat it settles wherever the operands do), andAggQueryIn.exists_sumFreethe pass: every query over the classes ofSand⊎– restricted recursions, in a signatureΘ, every⊎all-regular (sumsAllReg, what a recursion needs and the re-typing produces) – is matched wherever it is defined by one overSalone, for anySholdingsumMuOps={∅, Π, σ, apply, γ, μ^⊎}, with the restriction, the signature, derivable windows and well-formedness kept. A⊎inside a recursive body is not replaced but split (exists_sumFree_aux's second half): the body is the sum of a body with the non-recursive side of each⊎on the recursive path dropped and a closed query, which is empty at a bag recursion that settles (mu_of_split) and moves into the base of a set recursion (muSet_of_split). The bound names come from an injective supply the query does not use, whichexists_freshSupplygives for a schema declaring finitely many namesProvenance.WinKept– a window kept as a window over an all-regular input: a window reads the regular columns of its rows and nothing of the aggregate ones, its peers' tie-break included, so the window over a re-typed input is a different query.AggQueryIn.winKeptwrites it over the doubled input – each row prefixed by its nulled copy (doubled), the partition, order, term and clause moved to the first block (castCols,TermIn.widen,Selection.widen), the block then dropped – andevaluatePlain_winKeptis the equality: the two listings of a frame, sorted by the clause with ties by the row, differ only in the order of rows with equal first blocks (windowValueOpt_blockL, offreadLe_blockLandOrderSpec.map_eq_of_sorted)Provenance.RecursionBasisPass– the pass over the whole algebra: one structural induction (exists_basisRec_aux) in the manner of the union's pass, generalized over its target classes – any set holding the construction's six (AggQueryIn.sumMuOps) and not⊎, with the windows kept or derived and the set recursion kept or handed to aMuSetHandler. Every node is re-typed to regular columns (AggQueryIn.allRegOf,toReg) and rewritten by the local identities – a window kept over the doubled input (winKept) or, where the target has nowin, written aswinByApply, duplicate elimination as a grouping, the difference as theNOT INform with its product written as an apply (notInDiffA), a product as an apply (prodA, orprodSwapwhen the recursive relation is on its right, the apply admitting it on the left only), a union throughexists_sumFree_aux– with a second half for recursive bodies. The apply replaces×because the restriction on recursive terms admits an apply whose left side reads the recursive relation, which no decorrelation keeps. Its instance over the basis isbasisRecOps_generatesOnRecinProvenance.MuUnionProvenance.Genericity– a query of the minimal signature commutes with a faithful map, and its counts are polynomially many: a map faithful on a set of values (FaithfulOn: nulls and the order preserved) that fixes the query's constants and the counts it computes (AggQueryIn.countValsAll) commutes with its evaluation (AggQueryIn.evaluatePlain_faithful), through every operator and both recursions, settling or not. The order type of a context over a finite set (ordType: each parameter's place among the set's values and whether it is one, and the parameters' pairwise comparison) yields such a map between two contexts of one type (exists_faithful_of_ordType_eq), so at an aggregating node the counts at a context are those at the representative of its order type (AggQueryIn.countValsAll_subset, the count typesAggQueryIn.countTypescollecting them over a base set), and there are polynomially many order types (card_ordType), hence polynomially many count types (AggQueryIn.exists_polyBound_countTypes,PolyBounded).AggQueryIn.exists_card_bound_muSetis whatProvenance.MuUnionneeds: a set recursion's fixpoint, duplicate-free over the base set and the count types, has polynomially many rows in the number of values the recursion reads, which is what bounds the counter the simulation of a set recursion runs; the value lemmaAggQueryIn.valsIn_evaluatePlain(every value of a result is read off the instance, the context or the constants, or is a count) is its first halfProvenance.WinRow– the window class is necessary:win_mem_of_generatesOnRecsays the window class is in every generating set overℕwith the counting aggregate. The witness iscount(*) OVER (… EXCLUDE CURRENT ROW)onncopies of one row (winWitness,dRep), which writesn − 1; the invariant (sym_aux,ClosedSym/BodySym) is that a window-free query of the minimal universe reads that family, fornpast a threshold, as a bag of polynomial shapes (Shape,PolyBag: a multiplicity and a row of polynomials overℕ, instantiated atn), its settling being decided by one bit. Two polynomials are eventually equal or eventually strictly ordered (Poly.Cmp, off their real asymptotics), so every comparison a predicate, a key or a duplicate elimination makes is decided at the threshold (Decided,dedupAt,inst_eq_iff_shift); a count is read symbolically (count_onBag_eq_card); and the recursions run their rounds on bags, the fixpoint index being read off the symbolic rounds. The polynomials a query can write are finitely many because the counts it reads are (CountPolys, offProvenance.Genericity's bound), andn − 1isX − 1, which has no natural constant coefficient (Poly.add_one_ne_X)Provenance.SelRow– the selection is the only operator reading the order:AggQueryIn.evaluatePlain_orderBlindsays a query with no selection, reading no aggregate column as a key (noExplode), in a signature with no function on values, commutes on its regular columns (ColKind.readTuple) with every injective map of the values fixing0and its constants, whatever the map does to the order – the faithfulness commutation ofProvenance.Genericitywith the order dropped. The windows and the ordered aggregations read the order into aggregate columns, which such a query never reads back. The witnessσ_{#1<#2}(S)keeps{(a, b)}and not{(b, a)}(ltWitness_breaks), so no selection-free query expresses it (ltWitness_not_expressible), andσis in every generating set whose produced queries read no aggregate column as a key (sel_mem_of_generatesOnRecNoExplode, againstGeneratesOnRecNoExplode, the scope of the annotated classification)Provenance.RoundBound– a bag recursion that settles does so within a bound read off its values: a recursive term reads its hole once, so it is linear in the recursive relation (AggQueryIn.bind_of_body: a round is the previous round bound through a function of the row, plus what the term reads at the empty round); a row of roundjends a path ofjsteps from the base (exists_path_of_mem_round), a path overV^mlonger than|V|^mrepeats a row, and the segment between the two copies pumps a non-empty round past every bound (mem_round_pump). So a recursion that settles has an empty round at|V|^m(bindStep_round_eq_zero_of_settles) and is the sum of that many rounds (AggQueryIn.mu_eq_muSum_of_valsIn). This is what a bounded simulation of a bag recursion rests on – one that settles everywhere and agrees with the recursion wherever the recursion settles – which is what tabulating an apply's right side over a closed parameter relation needs, the table evaluating the right side at parameters the apply never reachesProvenance.AnnotatedBasis– the basis of the annotated semantics, its statement and its inherited rows:GeneratesAnn T K sch cnt Ssays every query of the whole algebra in the minimal universe reading no aggregate column as a key is matched overS, with the same kinds and no aggregate column read as a key, by a query whose annotated evaluation (evaluateAnnotated) settles and agrees with it on everyK-instance at which the query's does (AggQueryIn.AnnSettlesAt, the per-instance settling of the annotated recursions, inProvenance.AggQueryAdequacy, whose data-part adequacy takes it). The settling of the recursions transfers both ways between the annotated evaluation and the plain evaluation of the stripped query (settlesAt_stripAgg_of_annSettlesAt;annSettlesAt_of_settlesAtfor aliftFaithfulquery – no aggregate selection, no difference, no set recursion – at an instance annotated𝟙,Database.liftOne), so a set generating the annotated algebra over anyKgenerates every faithful query plainly (generatesAtNoExplode_of_generatesAnn), which every witness of the plain rows is:∅,Π,γ,μ^⊎,win,σand one of×/apply are in every such set (required_mem_of_generatesAnn), the selection row holding outright since the alternatives are out of the language. The trivial generating set is every class (generatesAnn_plainRecOps);GeneratesAnn.monocarries generation to supersetsProvenance.AnnotatedDedup–εis dispensable in the annotated algebra, the first non-trivial sufficient half of the annotated classification:ε(q) = μ^∪s.(q, σ_false(s))exactly in every commutative m-semiring (evaluate_dedupMu: the first round is the deduplication, the term keeps nothing of the round, the iteration settles at the second round,annSettlesAt_dedupMu), and the passdedupFreereplaces everyεby that recursion under a fresh name, changing no annotated evaluation (evaluate_dedupFree), settling wherever the query does (annSettlesAt_dedupFree) and keeping the classes, the signature, the hygiene and the well-formedness. So the classes other thanεgenerate the annotated algebra (generatesAnn_dedupFree)Provenance.AnnotatedProd–×is dispensable in the annotated algebra too: a product is the apply of its left factor with its right factor read under the ambient context (evaluate_prodApply, exactly), an apply's left side carrying aggregate columns as freely as a product's factor does. Where a recursive term's hole is in the right factor, which an apply's right side cannot hold, the factors are swapped and the columns put back by a projection (finEq_prodSwap), which cashes some pending group factors and so agrees with the product only up to finalization: the same rows, columns and finalized annotations (AggQueryIn.FinEq), a relation every operator respects (the congruencesAggQueryIn.FinEq.proj…winExpr, the selection on an aggregate value throughGenAnn.finalize_sel) and all that the annotated evaluation reads. The passprodFreekeeps the classes, the signature, the well-formedness and the kinds (AggQueryIn.wellKinded), so the classes other thanεand×generate the annotated algebra (generatesAnn_dedupProdFree)Provenance.AnnotatedSum–⊎is dispensable in the annotated algebra as well:q₁ ⊎ q₂is two bag recursions over one driver row (AggQueryIn.sumByMuK), the first listingq₁'s rows behind the driver, the second addingq₂'s, each round re-tagging an operand's rows; the operands may carry aggregate columns, a round of a bag recursion being bound in the evaluation's environment, and the driver row's aggregate columns hold a padding token that the construction drops (evaluate_sumByMuK_fin, up to finalization). A⊎on the recursive path of a body cannot be replaced where it stands, so the pass splits such a body into a body and a closed query (AggQueryIn.exists_sumFreeAnn_aux): at a bag recursion that settles the closed part is empty (mu_of_splitAnn), at a set recursion it moves into the base (muSet_of_splitAnn). So the classes other thanε,×and⊎generate the annotated algebra (generatesAnn_dedupProdSumFree)Provenance.PathSum– linear recursions over a semiring, read path by path: the iterates of a set recursionX ↦ ε(B ⊎ X ⊳ G)areεof the truncated sums of its bag rounds (iterate_stepK_eq), a round's weights are path sums (y_eq_sum_pathsTo), and a recursion that settles does so within the size of a tuple set closed under its rounds, where the semiring is absorptive or cancellative without zero divisors (iterate_succ_eq_of_settles, andwt_trunc_settleon the tuples the derivations of non-zero weight live on), and its weights within twice that size where⊗is⊕on non-zero values, as in the lineage semiring (PathSum.UnionLike,wt_trunc_settle_lin); a successor counter over the counters annotated𝟙pairs each derivation with exactly one counter (SimSpec.dedupK_rounds), and in an absorptive semiring an all-chains counter whose chains absorb nothing of the derivations they are paired with gives the same value (ChainSpec.dedupK_rounds)Provenance.AnnotatedMuUnion–μ^∪fromμ^⊎andεin the annotated algebra, the construction: duplicate elimination applies noδ, so the simulation ofProvenance.MuUnioncarries over once its counter neither multiplies nor repeats derivations – a successor counter, computed by a difference, whose rows are annotated𝟙or𝟘(AggQueryIn.simResultA,evaluate_simResultA), or an all-chains one; the pass replacing every set recursion isAggQueryIn.muSetFreeA, correct wherever its node is (muSetFreeA_correct), and composed with the passes for×and⊎the classes{∅, Π, σ, apply, γ, win, μ^⊎, ε, −}generate the annotated algebra there (generatesAnnOn_annEpsOps_of)Provenance.AnnotatedChains– the two nodes, over every instance: every row holding a value is within any bound the operators keep (AggQueryIn.rowBd_evaluate); whereδis the support map, a value held only by rows annotated𝟘makes every row holding it𝟘, so the successor counter is exact with no fence on the instance, in the semirings ofPathSum.SettlesLinear(AggQueryIn.muSetSim_correct_succ,generatesAnn_annEpsOps_of_support); whereδis the identity (the Boolean algebras and the min-max semirings), a row is below the weight of each value it holds, so the all-chains counter absorbs nothing of a derivation through distinct tuples (AggQueryIn.muSetSim_correct_chain,generatesAnn_annEpsOps_of_delta_id)Provenance.AnnotatedDiffRow–−is necessary in the annotated algebra: overℕ × ℕ(NatPair), every annotation a query without a difference builds – a row's, its tokens' occurrences', a predicate's provenance – is zero in one coordinate exactly where it is in the other, that being kept by every operator but the difference (annIn_evaluate, for any propertyAnnCloseddescribes), andR − Sgives(0, 1)(diff_mem_of_generatesAnn)Provenance.AnnotatedEpsRow–εorμ^∪is necessary in the annotated algebra: overℕ, without them every annotation a query of the minimal signature builds is at most𝟙when the instance's are (le1_evaluate) – the joint reading of a selection weighs its worlds at most𝟙together (GenPredIn.predsemJ_le_one) – andεof a relation holding one tuple twice gives2(dedup_or_muSet_mem_of_generatesAnn); with the other rows, no proper subset of{∅, Π, σ, apply, γ, win, μ^⊎, ε, −}generates over bothℕandℕ × ℕ(annEpsOps_minimal)Provenance.AnnotatedBasisClass– the annotated basis theorem over a class of semirings:{∅, Π, σ, apply, γ, win, μ^⊎, ε, −}generates the annotated algebra over every m-semiring whereδis the support map and linear set recursions settle within twice the size of their tuple set –ℕ,ℕ[X], the lineage semiring among them – orδis the identity (AnnBasisClass), and no proper subset does over all of them (annEpsOps_isBasis_in_class); the difference's witness inside the class isℕ[x, y], whereR − Sgivesxand no difference-free query builds an annotation with morexthany(diff_mem_of_generatesAnn_xy)Provenance.AnnotatedBasisHom– the basis theorem's matches commute with homomorphisms: the construction reads no annotation, so one query over the nine classes serves every semiring where its counter simulates a set recursion (exists_annEpsOps_matchU), and it commutes with every homomorphism the source commutes with, wherever the source settles on both sides (exists_annEpsOps_match_hom, with the support and theδ = idclasses as_supportand_delta_id); nothing is asked of the match's own labels or read setsProvenance.AnnotatedApproxRows– the necessity rows up to≈, rows annotated𝟘and occurrences annotated𝟘dropped (GeneratesAnnZ): the rows inherited from the plain basis transfer through the Boolean support over𝔹, where≈keeps the realized world and the realized world evaluates plainly (generatesAtNoExplode_of_generatesAnnZ, withAggQueryIn.settlesAt_randomWorld), the others keep their witnesses' rows; with the positive half, the nine classes are a basis up to≈over the class (annEpsOps_isBasis_in_class_approx)Provenance.AnnotatedApplyRow– the apply row up to≈with occurrence identity. Ordinary tokens carry the identities of their occurrences (AggValue.oids, stamped by the grouping and the window), andGenRow.zeqRencompares results up to≈with a one-to-one renaming of them, which keeps which aggregate values share which occurrences; aggregate expressions carry identities too (AggExpr.oids), and so do the expressions a nested value reads at every storey, the nested values themselves being compared through their families, renamed;GeneratesAnnRenis the generation predicate up to it. Over Boolean functions of two variables a set generating up to it holds the apply (apply_mem_of_generatesAnnRen):R ⊳ γ_∅[count](σ_{#1 < u}(S))gives each parameter its own occurrence annotatedy, while without an apply the ordinary tokens holding an occurrence annotatedyare hit by a set of identities bounded by the query (AggQueryIn.exists_hit). With it, the annotated basis theorem holds up to≈with occurrence identity over the class (annEpsOps_isBasis_in_class_ren): the constructions agree with their source row by row, identities included, the rows up to≈by value transfer (GeneratesAnnRen.toGeneratesAnnZ), and no set of classes generates without the apply, a product includedProvenance.AnnotatedWhyRow– the annotated basis theorem: set recursion is required.{∅, Π, σ, apply, γ, win, μ^⊎, −, μ^∪}generates the annotated algebra over every commutative m-semiring, and no proper subset of it does over all of them (annMuOps_isBasis).μ^∪'s row is over the why-provenance semiring (muSet_mem_of_generatesAnn): on a family of instances sharing their data, a query withoutμ^∪keeps its annotations within one grade – witnesses of boundedly many variables (Graded,AggQueryIn.exists_grade) – while a set recursion over an edge carryingmone-variable witnesses builds one ofm. So overWhy[X]the set withεin place ofμ^∪does not generate (not_generatesAnn_annEpsOps_why). The same holds up to≈, nested aggregation included (annMuOps_isBasis_approx,muSet_mem_of_generatesAnnZ)Provenance.MuUnion–μ^∪fromμ^⊎(basisRecOps_generatesOnRec, for every restricted term): a set recursion is simulated by a bag recursion over pairs of a tuple and a counter, the base(q₀ ⊎ C) × E^Kand each round applying the term to the tuple part and moving the counter to every larger one in the lexicographic order ofE^K(AggQueryIn.sim,simResult= its tuple parts without duplicates).evaluatePlain_simResultis the correctness, under|F| ≤ |E|^Kfor the fixpointFand a counter relationEof non-null values, andsettlesAt_simResultthe definedness. The counter relation is computed (counterRel): the columns of the base, of the relations the recursion reads, its constants and the context, with two constants of the domain, the non-null rows kept byx = x; its widthKis fixed by the query, offAggQueryIn.exists_card_bound_muSetofProvenance.Genericity, which bounds the fixpoint by a polynomial in the number of values the counter runs over. The pass ofProvenance.RecursionBasisPassthreads the schema; where the target holds noμ^∪it callsMuSetHandler, whichmuSetHandlerproves for any target holding the union's basis, andbasisRecOps_generatesOnRecis the generation statement:basisRecOps={∅, Π, σ, apply, γ, win, μ^⊎}generates the whole algebra in the minimal universe (GeneratesOnRec), withsumMuOps_generatesOnRec_of_winsDerivabledroppingwinfor derivable windows. Soμ^∪is in no basis of the whole algebra in that universeProvenance.RecursionBasisTheorem– the classification of the whole algebra in the minimal universe, in one place:basisRecOps_isBasissaysbasisRecOpsgenerates over every schema (generatesOnRec_of_basisRecOps_subsetextends that to every superset, offGeneratesOnRec.mono) and that no proper subset does (basisRecOps_minimal), the rows gathered asrequired_mem_of_generatesOnRec:∅,Π,γ,μ^⊎,win, one ofσ/−and one of×/apply are in every generating set overℕwith the counting aggregate.−forσand×for the apply each give a further basis (basisRecDiffOps_isBasis, inProvenance.DiffBasis, andSym.basisProdOps_isBasis, inProvenance.SymPass), and the two together do not (Provenance.RecursionBases)Provenance.SumByProd–⊎and−with products:sumByMuXissumByMuwith each round's apply written as the product it stands for, andnotInDiffXtheNOT INdifference over it, both over the classes{∅, Π, σ, ×, γ, μ^⊎}Provenance.SymCode,Provenance.SymCells,Provenance.SymRel,Provenance.SymTerms,Provenance.SymOps,Provenance.SymGamma,Provenance.SymWin,Provenance.SymMu,Provenance.SymTab,Provenance.SymCorrect,Provenance.SymOrder,Provenance.SymEnvBuild,Provenance.SymCut,Provenance.SymSettle,Provenance.SymMatch,Provenance.SymApply,Provenance.SymStruct,Provenance.SymOver,Provenance.SymPass– evaluating a query at the types of its parameter row: a parameter value is coded relative to a finite cut of values (a value of the cut, or a gap with a rank,Sym.code), equal codes standing for equal values and the order of codes being the order of values (Sym.Code.lt_iff); a code is stored in7 + kcolumns, and a comparison of two cells has the three-valued truth of the comparison of their values (Sym.eval3_cellCmp). A symbolic relation holds, under the descriptor of each parameter row, the encodings of the rows the query computes there (Sym.SliceIs); projection, selection, join, the leaves and the grouping map these slices (Sym.sliceIs_symProj,sliceIs_symSel,sliceIs_joinL/R,sliceIs_leaf,gammaRows_slice), and so do the windows (Sym.sliceIs_symWin) and a bag recursion run against a list of counters (Sym.sliceIs_symMu).Sym.symassembles the symbolic evaluation of a query, andSym.sym_correctsays it is correct wherever the values the evaluation reads are good and the environment provides enough counters. The environment is built from a cut by products, selections, projections and theNOT INdifference (Sym.envOf, sound bySym.envOK_envOf), and the cut of a query is defined by recursion, each aggregation adding the values its symbolic counterpart computes at the cut of its input (Sym.cutQ);Sym.tabQ_correctputs the two together, and the table settles on every instance, its recursions bounded by counters (Sym.settlesAt_tabQ). An apply is then a product of its left side with the descriptors, the table and a pool of values, a row's own descriptor being picked by a predicate that holds of it alone (Sym.eval3_matchSP_true) and the table's cells read back as values (Sym.eval3_decCell_true):Sym.evaluatePlain_applyX. The constructions stay in the fragment (Sym.fine_applyX) and are well formed over the schema (Sym.over_applyX). Run from the leaves up through a query over{∅, Π, σ, apply, γ, win, μ^⊎}(Sym.exists_prodPass_aux), with each apply's pool a closed query holding its left side's values – inside a recursive term, the values of the base and those the term creates – this givesSym.basisProdOps_generatesOnRec: the product in place of the apply,{∅, Π, σ, ×, γ, win, μ^⊎}generates the whole algebra in the minimal universe, and with the rows ofrequired_mem_of_generatesOnRecit is a basis there (Sym.basisProdOps_minimal,Sym.basisProdOps_isBasis)Provenance.DiffBasis– the difference in place of the selection:basisRecDiffOps_generatesOnRecsays{∅, Π, −, apply, γ, win, μ^⊎}generates the whole algebra in the minimal universe, andbasisRecDiffOps_isBasisthat it is a basis there. A selection becomes an apply of its input with a closed test holding the empty tuple once where the predicate is true at the row (DiffBasis.selX,DiffBasis.evaluatePlain_selX); the test is built by induction on the predicate in Kleene's logic, true and false together (DiffBasis.predTF), the connectives and the equalities from the difference alone. The order is read by a window: over{a, b}, a bag recursion of one round (DiffBasis.pairZ), the row ofbcounts the rows strictly before it, and that count is compared with0as a key (DiffBasis.ltT,DiffBasis.evaluatePlain_ltT). Reading the count as a key is whatExplodedoes, whichusesOnlycharges to no class; without itσis in every basis (sel_mem_of_generatesAtNoExplode)Provenance.RecursionBases– all the bases of the whole algebra in the minimal universe: a recursive term reads its recursive relation under a projection, a selection, a product, the left side of an apply, a union,ExplodeandRetag, and only the selection and the apply drop a row. Without them a round hask · |X|rows for akthe round does not change, so a bag recursion that settles is its base (AggQueryIn.evaluatePlain_mu_degenerate,AggQueryIn.exists_dropMu), the answers are polynomial, and the chain of diamonds gives the rowsel_or_apply_mem_of_generatesOnRec. So{∅, Π, −, ×, γ, win, μ^⊎}is not a basis (not_generatesOnRec_prodDiff), andgeneratesOnRec_iffsays a set of classes generates the whole algebra overℕwith the count exactly when it holdsbasisRecOps,Sym.basisProdOpsorbasisRecDiffOpsProvenance.RecFreeBasis– the bases of the recursion-free algebra in the minimal universe:GeneratesOnRFis the generation of every query with no recursion, andgeneratesOnRF_iffsays that among class sets with no recursion the generating ones overℕwith the count are exactly the supersets of∅,Π,⊎,γ,winwithσor−and with×or the apply – all four pairings, each minimal (rfSelApplyOps_minimaland its three siblings). The rows are the whole algebra's at its recursion-free witnesses,⊎added (union_mem_of_generatesOnRF). The positive halves run a recursion-free pass (AggQueryIn.exists_rfPass) that keeps⊎, keeps×or−where the target has them, and keeps a selection, where the target has noσ, by its test fromProvenance.DiffBasisdecorrelated over the distinct rows of its input (AggQueryIn.exists_selByTest). The×bases first remove the applies by the decorrelation ofProvenance.Decorrelate, which stays in the signature for queries whose parameter leaves are regular (AggQueryIn.exists_applyFree_plainEquiv_sig,AggQueryIn.paramsReg) and asksσandεonly of a product or an apply (AggQueryIn.hasDecorrelation_of_usesOnly_gen). Recursion-free,{−, ×}is a basis; with recursion it is not (not_generatesOnRec_prodDiff)Provenance.WindowPartition– a window over a whole partition is a join with its grouping:AggQueryIn.winByJoinwrites it without a window – join the query with its own grouping on the partition key with≐, the syntactic equality a window partitions by, and keep the group's aggregate column – andevaluatePlain_winByJoin,evaluate_winByJoinprove the two agree over plain and over annotated relations. The plain statement is a rearrangement; the annotated one is not, since the join carries the group's existence factorδ(⊕ U)that a window never produces. The two agree only because the group of a row contains that row, so the factor readsα ⊗ δ(α ⊕ β'), which isαby δ-absorption – a frame excluding the current row would have no such identity and no such rewriting. The combinatorial step isfilter_product_key: a table with distinct keys, joined on the key, gives each row exactly the entry of its own keyProvenance.ReadsCongr– an evaluation reads its context only where it says it does: underAggQueryIn.readsRecorded, two valuations of the parameters and two environment contexts agreeing on the positions the query reads give the same annotated evaluation (AggQueryIn.evaluate_congr_reads), terms, predicates and the operators' value builders read the parameters only through their termsProvenance.JointHom– the joint reading of a family under a homomorphism: aLeafSpecsays how an aggregate value reads an occurrence of its family as a function of the occurrence's row, a value built from a listing by one is read off the rows a world selects (classWorlds_presented), and two listings related by a tie-block permutation give corresponding worlds for every value built from them together (classWorlds_hom); a nested family is read off two values whose worlds correspond one by one, the kept product and the absent sum pushed through the hom (NestedValue.WCorr,classWorlds_of_wcorr); a row whose families correspond family by family has corresponding joint worlds (jointWorlds_hom), in particular one whose families are presented on both sides (FamPres,jointWorlds_of_famPres)Provenance.NestedPres– nested values under a homomorphism, at every storey: two nested values built from related rows are related family by family (NestInner.Rel: an expression family presented on each side by listings a tie-block permutation apart, a node's occurrences paired with their annotations pushed through the hom), and where related families share a key on one side exactly when they do on the other (KeysFaithful, which a coherent evaluation gives) their worlds are the images of one bag of decisions, each family and each node decided once (wcorr_of_rel)Provenance.Coherence– one family identifier, one value, across every evaluation a query performs (AggQueryIn.builds_coherent): the aggregate values the operators build – once per row of an apply's left side, once per round of a recursion – and the terms over them carry one value per identifier, for a query whose operators record what they read (readsRecorded), carry distinct labels (labelsDistinct), apply no arbitrary function to an aggregate value (sourceCols) and use frames containing the current row (allFramesContainSelf). The induction is on the identifier's size: an operator's identifier records its parameters', and equal parameters make equal inputs (AggQueryIn.coh_node)Provenance.AggQueryBridges– the fusedHAVINGsite in closed form:AggQueryIn.havingSiteis one aggregate comparison directly above the grouping, andAggQueryIn.havingSite_evaluateAnnotatedcomputes it – one row per group key, annotated byHaving.havingProv– since the pending group factor is superseded by the token's predicate provenance (AggValue.predProv_ofGroup) and the data part collapses to the whole-group aggregates. The fused site is thereby a theorem about the single annotated evaluator, not a semantics of its own. The file also records the opposite regime: a predicate whose compared tokens carry two different groups supersedes nothing, so both group factors stay pending and are cashed into the row (AggQueryIn.evaluate_Sel_of_two_groups, andAggQueryIn.evaluate_Sel_or_of_two_groupsfor the disjunction the∨rule is about), and that a projection dropping no token column a pending factor belongs to leaves both parts of the annotation alone (AggQueryIn.evaluate_Proj_of_pending_le) – so such a projection standing inside a chain of aggregate selections changes neither the families read nor the annotation built. It also carries equality up to impossible rows:AnnotatedRelation.dropZeroremoves the tuples annotated𝟘, which are in no world,ZEqis equality after that, andAggQueryIn.evaluate_Sel_reg_absorbsays a regular selection may be absorbed into the aggregate predicate below it in exactly that sense and not as an equality of relations – a selection with an aggregate atom keeps its failing rows annotated𝟘where a regular one removes themProvenance.Normalize– reading a chain of selections as one predicate. Under the joint readingσ_{ψ₁ ∧ ψ₂}is one sum whereσ_{ψ₁} ∘ σ_{ψ₂}is a product of two, and they agree only where the conjunction decomposes, so the two spellings of what a SQL user calls one query part would differ –4against2overℕ(natRangeToken_mul_ne_and).AggQueryIn.normalizemerges adjacent selections, a query being read asevaluate (normalize q), andnormalize_chainFree,normalize_id_of_chainFreeandnormalize_idemsay the result has no selection above a selection, that normalizing a normal form changes nothing, and that the pass is idempotent. The equality it buys is up to impossible rows and not of relations (AggQueryIn.evaluate_Sel_reg_absorb), since merging a regular selection keeps the rows it would have removed, annotated𝟘. Where both predicates read one family on a row (GenPredIn.ReadsOne), the pending parts of the chain and of the merge agree with nothing asked ofK: each supersede test reduces to “drop that family's factor” (Having.supersede_test_iff), and dropping it twice is dropping it onceProvenance.Alternatives– aggregate columns read as keys, the operator beingAggQueryIn.ExplodeinProvenance.AggQuery: it replaces each occurrence by its alternatives and makes the column regular, so aGROUP BYon a count or aDISTINCTon an aggregate can be written at all – every key-comparing operator takes regular columns. Over a plain relation an aggregate value is a value andExplodeis the identity. It is world-faithful: under a valuation exactly one alternative survives, the one whose value the column has in that world, and it specializes to what the occurrence specializes to, so the random-world commutation covers it. It is not data-part adequate, and cannot be: it gives one row per value the column takes in some world, soAggQueryIn.evaluateAnnotated_toPlaincarries the hypothesisAggQueryIn.noExplode. It commutes with homomorphisms (sim_alternativesAt), since the values a token takes survive both the pushforward (AggValue.vals_mapAnn) and tie-block equivalence (AggValue.vals_congr) – both becauseAggValue.valsreads the occurrences only through their values (AggValue.vals_eq_valsOf).Explodeis outside the (R1)–(R5) fragment. Several aggregate columns compared as one key ask for a single atom on the tuple of values rather than two atoms conjoined. The two coincide where the columns come from different groupings, whose families are disjoint,Kbeing complemented (Having.jointPair_and,Having.altProvPair_eq_mul). They do not where the columns come from one grouping: two aggregates of one group are one family (AggValue.annList_ofGroup), reading them as two independent ones counts a world once per half, and overℕthat is4against2(natRange_jointPair_ne). So the tuple atom is a definition, coinciding with the column-by-column reading only across groupings.Having.jointPair_self_eq_mulmakes the coincidence a theorem: reading one family as two independent halves is the column-by-column product, so a range atom against its two bounds, two selections against one on their conjunction, and two key columns against the atom on their tuple are the same identity, failing together at4against2or not at all. An operator that compares a key reads an occurrence whose column holds an aggregate value through its alternatives, one per value the column takes:(u[i ↦ v], α ⊗ [a ≐ v]), whereAggValue.altProvis[a ≐ v], the predicate provenance of the atoma = vunder SQL's null-safe equality – so the casev = NULLis the atoma IS NULLand needs no clause of its own.AggValue.worldsandAggValue.valsare the worlds and the values they take,predProvOfWith_eq_sum_worldssays the two reading conventions differ only in which subfamilies count, andGenRow.alternativesAtis the reading of an occurrence, whose column an alternative makes regular (alternativesAt_reg). Two facts make it a reading of the worlds rather than an enumeration of values:AggValue.sum_altProv, the alternatives' shares add up to what the worlds carry, so nothing is lost or invented; andAggValue.altProv_mul_eq_zero, distinct alternatives exclude each other whereKis exclusive, since distinct values come from distinct worlds – the remark that in𝔹[X]exactly one alternative of a present occurrence holds under each valuation, and that overℕ[X]an operator combining two alternatives of one occurrence counts worlds that do not existProvenance.AggQueryProbability– the random-world commutation for the general evaluator over𝔹[X]:AggQueryIn.genRandomWorld_evaluate– specializing the realized rows of the general annotated evaluation is the plain evaluation of the realized world (genRandomWorld v (q.evaluate d) = q.evaluatePlain (d.randomWorld v)), for arbitrary queries with aggregate comparisons anywhere. Built from the token-level PQE bridge (AggValue.predProv_eval_iff), the predicate-provenance evaluation under existence guards (GenPredIn.predsem_eval_iff, with¬handled by polarity), the existence-entailment extraction (GenPredIn.entails_guard), the σ-aggregate row lemma (GenPredIn.sel_finalize_eval_iff), and the conformance and guardedness invariants of the evaluator (evaluate_conform,evaluate_guarded). A window commutes for the reason it was built to: restricting the relation to a world restricts every frame to that world, so the token reads as the plain aggregate the world's relation gives its row (tokenOf_specialize). Its token is guarded by the row it is computed for whenever that row is in its own frame, and scalar – so exempt – when it is not. As corollaries, unrestricted probabilistic query evaluation:AggQueryIn.boolean_pqe(the probability that a random world has a non-empty answer is the probability of the query's Boolean provenance, the⊕-sum of the rows' finalized annotations) andAggQueryIn.tuple_pqe(the marginal probability of an answer tuple, for all-regular outputs) – both for arbitrary queries with aggregate comparisons anywhere, removing the top-level restriction of the fusedbooleanHaving_pqeProvenance.AggQueryHom– hom commutation for the general evaluator, token and annotation layer: the finalized factored annotation (GenAnn.finalize_mapHom, throughmap_delta), the predicate provenance of a token comparison (AggValue.predProv_mapAnn) and of a whole generalized predicate (GenPredIn.predsem_mapAnn) commute with everySemiringWithMonusHom– the⊕/⊗/⊖/δ-polynomial content of “compile once, evaluate many”. The evaluator-level commutation (AggQueryIn.evaluateAnnotated_hom) asks nothing of the hom and holds over every m-semiring, asking of the query that every window frame contain its current row (allFramesContainSelf) and that a family identifier determine its value across the evaluation – distinct labels, recorded parameters, no arbitrary function on an aggregate value (labelsDistinct,readsRecorded,sourceCols), under which each family is presented once for the whole evaluation (ClassPres,AggQueryIn.evaluate_hom_univ): the guard-absorption identities licensed bydelta_absorb(AggValue.predProv_delta_absorb,GenPredIn.predsem_delta_absorb) neutralize the supersede decisions a non-injective hom can conflate, the group-sequence transport (havingGroup_tiePerm,ofGroup_predProv_hom,havingGroup_annSum_hom) neutralizes the≼-tie-break ofhavingGroup, and a row-wise simulation (GenRow.Sim,AggQueryIn.evaluate_hom_rel) carries both through the evaluator. A window's frame is carried unchanged, being read off the values; what the pushforward moves is only the order inside a block of equal tuples, whichsortList_hom_tiePermandtokenOf_mapAnn_tiePermrender invisible exactly as for a group. A nested column is related family by family (NestInner.Rel): both sides' world enumerations are images of one index bag, with products and absent sums pushed through the hom (NestedValue.WCorr, fromwcorr_of_relunderKeysFaithful, whichkeysFaithful_of_homUnivsupplies), so its world's weight, one monus over every storey, is carried with nothing asked of the semiringProvenance.QueryToAgg– the embedding of the classical query syntax into the general evaluator:Query.toAggtranslates the non-aggregating fragment one to one over all-regular kinds, faithfully (Query.toAgg_bridgeand, at the raw row level,Query.toAgg_evaluate_eq, via the row invariantGenRow.Inv); the fusedHAVINGsite over an embedded subquery reads its input relation off the classical one (Query.toAggHaving_input). The module sits below the classicalHAVINGcorrectness files, so those state their theorems over the embedded general query with no side hypothesisProvenance.AggQueryEmbedding– the compositional JOIN rewriting, stated natively on the general syntax:GenCountHavingRewritereplacesHAVING COUNT(*)sites – key projections ofσ_ψ ∘ Gamma, all-regular and hence composable under every operator – by the embedded padded join query, andGenCountHavingRewrite.evaluateGen_eqproves the replacement preserves the general evaluator's rows verbatim; the expressible contexts around a site are exactly the ProvSQL-legal ones, the kind discipline forbidding deduplication, difference and re-grouping over aggregate values just as the system doesProvenance.AggQueryRewriting– the provenance-aware rewriting, natively on the general syntax: the rewritten column layoutColKind.rewKinds(nregular data columns plus one provenance column), the fragment predicateAggQueryIn.classical, and the rewritingAggQueryIn.rewritingmirroring the classical rules – with deduplication and difference expressed through the nativeProvSumaggregation of provenance columns and theRetagcastProvenance.AggQueryStrip– the strip of the classical fragment back to the classicalQuerysyntax (AggQueryIn.strip) and its faithfulnessAggQueryIn.strip_bridge, through the row invariantGenRow.InvProvenance.AggQueryRewritingValid– correctness of the native rewriting: the plain-semantics agreementAggQueryIn.rewriting_plainof the two rewritten queries, andAggQueryIn.rewriting_valid, which states that the annotated semantics folded into compositeT ⊕ Ktuples agrees with the plain evaluation of the rewritten queryProvenance.AggQueryHavingRewriting– the rewritten world's evaluator, with tokens as ordinary column values: rewritten queries run over rowsTuple (GenValue (T ⊕ K) K) n(AggQueryIn.evaluateRew), where the token-building groupingGammaTokis ProvSQL'sprovsql_agg(explicit annotation term, group guardδ(⊕ occs)in theprovoutput column) and the two term gates are interpreted by their primitives (TermGIn.evalRew):TermGIn.cmpAggisprovsql_having, read byAggValue.predProv, andTermGIn.chiGateis the regular-atom indicator, read byHaving.chi. Off the token operators and the indicator gate the evaluator is the plain semantics through theinlembedding (AggQueryIn.evaluateRew_plain, underAggQueryIn.noGammaTokandAggQueryIn.chiFree), connecting it to the classical rewriting correctness – the classical rewriting stays inside that fragment (AggQueryIn.rewriting_chiFree).AggQueryIn.rewriting_provRelreads a rewritten evaluation back as an annotated relation – the input the token-building groupings consume – andHaving.havingGroup_toCompositetransports the group sequence along the composite embedding; the rewriting rules built on top live inProvenance.AggQueryGroupRewritingandProvenance.AggQueryClosureProvenance.AggQueryGroupRewriting– the bare-grouping rewriting, the general framework's counterpart of rule (R5): aGROUP BYwhose aggregate columns flow onward as output values, rather than being consumed by a comparison gate. No new value domain is needed – the rewritten world already has tokens as column values – but the correspondence must be stated at token level, since the composite embedding of an annotated relation reads tokens through their deterministic collapse.GenRow.toCompositeRowis the token-aware embedding (AggValue.toCompositeon token columns, the finalized annotation appended as the provenance column), agreeing with the old embedding on token-free rows (GenRow.toCompositeRow_of_reg);AggQueryIn.gammaRewis the rewritten grouping (GammaTokover the classically rewritten subquery) andAggQueryIn.gammaRew_validits correctness; aFILTERclause rides into it unchanged (Selection.castToAnnotatedTuple), its aggregate's column being an expression over the whole group on both sides (AggExpr.ofGroupWhen_toComposite, against the rewritten world'sAggExpr.ofGroupWhenRew, whose reading is the one the transport carries). Both rest on the reusableAggQueryIn.rewriting_provRel– the rewritten world's reading of a classical rewriting back as an annotated relation, andAggValue.predProv_toComposite– a transported token is read by the gate unchangedProvenance.AggQueryClosure– the compositional closure of the three base rewritings (classical blocks,HAVINGsites, bare groupings). Since the base rules do not share an output shape – a bare grouping emits token columns – the relationAggQueryIn.RewritesTois indexed by the rewritten query's own kind vector and correctness (AggQueryIn.rewritesTo_valid) is stated at token level, specializing to the all-regular form asAggQueryIn.rewritesTo_valid_reg. The uniform rewritten kind vectorColKind.rewKindsOf κ(source kinds plus the provenance column) makes casting into the rewritten world kind-preserving, soTermGIn.castRew,GenPredIn.castRewandProjColIn.castRewneed no all-regular hypothesis and selection, projection and union close over token-bearing subqueries – theSELECT … FROM (GROUP BY …)shape. The module also lifts the two scope restrictions of theHAVINGsite:AggQueryIn.havingPredRewis the site with its aggregates exposed (keys and tokens kept as output columns, the gates in the provenance column – the shape ProvSQL actually emits) for an arbitrary predicate with an aggregate atom, not just a single comparison, regular atoms mixed in included.GenPredIn.gateTermtranslates thepredsemalgebra into a rewritten term (∧ ↦ ⊗,∨ ↦ ⊕,¬pushed to the atoms), an aggregate atom becoming aprovsql_havinggate and a regular one aTermGIn.chiGateindicator gate. It is faithful (GenPredIn.gateTerm_evalRew) for a row whose aggregate columns hold no nested token: the gate reads the transported column, and the transport preserves the reading of an ordinary token (AggValue.predProvOf_toComposite) and of an expression – a window's, or a filtered aggregate's – alike (AggExpr.predProv_toComposite, off the world transportAggExpr.isWorld_toCompositeandAggExpr.valOn_toComposite). What it does exclude is a range atom (GenPredIn.rangeFree), and that is the gate vocabulary's own limit: ProvSQL's gate carries one comparison, so the emitted term is the product of two of them, which denotes the two-world reading. The system recovers the one-world reading in its evaluation pass instead – a product of conditions over one contributor family is resolved jointly, with the closed formS_C ⊖ S_{D+1}(Having.G_eq_S_monus_S) for a two-sided bound on a count – so lifting the fence means modeling that pass, not adding a gate. Whether the group-existence guard is superseded or kept as a factor is decided byGenPredIn.entailsExistence, inGenPredIn.siteProvTerm: an aggregate-only predicate always supersedes it (GenPredIn.aggOnly_entailsExistence), one with a regular atom reachable in an empty group does not. Deduplication closes too, throughAggQueryIn.dedupRew/AggQueryIn.dedupRew_valid: ProvSQL'sεrule (group by the data columns,⊕-sum the provenance column) proven against an arbitrary rewritten subquery. So does product (AggQueryIn.prodRew/AggQueryIn.prodRew_valid), whose join reassembly uses the kind-dispatched column copyProjColIn.copy, faithful because the operands' rows conform (GenRow.toCompositeRow_conformoverAggQueryIn.evaluate_conform). The grouping itself closes over an arbitrary rewritten subquery (AggQueryIn.RewritesTo.gammaOf, offAggQueryIn.gammaRewOf_valid): the rule asks only that some query of the rewritten world compute its input's rows – the pairs of a plain tuple and the annotation its provenance column carries, whichAggQueryIn.provRel_of_toCompositeRowreads off any such rewriting – so aGROUP BYover aGROUP BYis covered, the inner aggregate column read out first as the kinds ask (AggQueryIn.rewritesTo_gamma_gamma). The selection with an aggregate atom closes over an arbitrary rewritten subquery as well (AggQueryIn.RewritesTo.selAgg, offAggQueryIn.selAggRew_valid), so aHAVINGneed not sit on the grouping it reads – one over a grouping of a grouping is covered (AggQueryIn.rewritesTo_having_over_gamma). Its provenance column is the gate term times the row's own provenance column, with no entailment test: where the predicate entails the group's existence the evaluator drops the pending factor and the gate term absorbs the guard left in the column instead (GenPredIn.predsem_absorb_prod, for exactly the factors the evaluator's supersede filter selects). ProvSQL'shaving_entails_group_existencetest is therefore an optimization and not what makes the rewriting correct; the fused site rule stays because it is the shape ProvSQL emits. Difference above a grouping the kinds already forbid; what is left outside is the operators this layer gives no rule for – the apply, the two recursions and the alternatives, each for a reason in the shape of the rewritten plan, and the windows, which ProvSQL does rewrite: what is missing there is a specification of that rewriting, not a possibility, and specifying it is outside the semantics this library formalizes
The classical rewriting layer
Provenance.QueryRewriting– alternative query evaluation by rewriting plain queries onT ⊕ K; implements rules (R1)–(R4) of Sen, Maniu & Senellart on the classical syntax, with correctnessQuery.rewriting_valid. The difference rule joins the two branches on their data columns with≐, the syntactic equality difference itself uses, so the rule holds over a domain with a null as it stands. Rule (R5) – aggregation – lives on the general syntax instead (Provenance.AggQueryGroupRewriting), where an aggregate output is a symbolic token rather than a quotiented K-tensor HAVING: algebra, possible worlds, probability, and correctnessProvenance.Having– algebraic identities behindHAVING (count)aggregate provenance: include/exclude recurrences for the JOIN and possible-world expressions, the upward-expansion bound, the upward-closed collapse (upward_closed_collapse,collapse_to_minimal), the sandwichT_U(W) ≤ ann_U(W) ≤ A_Wof the factored world annotation and the resulting distributivity-free collapse of the monotone case (monus_factor_le,witness_identity,witness_minimal,Fann_eq_S), the range closed formrange_eq_S_monus_S–HAVING C+1 ≤ count ≤ DisS_{C+1} ⊖ S_{D+1}, of whichatMost_eq_S_monus_SandG_eq_S_monus_Sare the casesC = 0andD = C + 1, and whose hypotheses are not confined to the stepF = Sit passes through (Having.natRange_neseparates the two sides overℕon two occurrences annotated𝟙), and the index-set size factsProvenance.HavingSemantics– the possible-world semantics of the fusedQuery.Havingoperator (grouping + aggregate comparison) over annotated databases: group-occurrence sequences, the bridge between subsequences andFinset-of-positions worlds (seqOf_sublist,sublist_eq_seqOf,seqOf_injective), the factored world annotation (worldAnn), the predicate provenance (havingProv) with its attachment to the query-free algebra (havingProv_eq_prov), and Boolean combinations of aggregate comparisons (HavingPred). Existential comparisons collapse to the qualifying occurrences (havingProv_existential3): in an absorptive m-semiring the provenance off(t) op cis the⊕-sum of the annotations of the occurrences whose value makes the comparison true. It holds over a domain with a null as it stands, and SQL's ownMINandMAXare existential in that reading (Existential.sqlOf3,existential3_sqlOf_min_leand its three companions) – the values the aggregate skips being exactly the values a strict comparison is unknown on, an occurrence with a null value is in no world's reason for the predicate holdingProvenance.HavingMinMax– theHAVINGaggregate comparisons whose validity is decided occurrence by occurrence: forMIN,MAXandPICKFIRST, and for all six comparison operators, the possible-world provenance of a group collapses, in an absorptive m-semiring, to a closed form computable by a single scan over the occurrences (minScan_correct,maxScan_correct,firstScan_correct), hence in polynomial time in data complexity. The collapse rests on the identitymeet_family_eqfor the worlds that stay inside a setGand meet a setHProvenance.Probability– intensional probabilistic query evaluation: probability distribution over Boolean valuations, probability of aBoolFunc X, and the statement of Theorem 12 of Sen, Maniu & Senellart reducingPr(t ∈ q(Î))toPr(⋁_{(t,α) ∈ ⟪q⟫^Î} α); the proof is reduced to a single structural commutation lemmarandomWorld_evaluateAnnotatedProvenance.SupportAdequacy– support adequacy over𝔹, for the full non-aggregation fragment (difference and duplicate elimination included): the support of the𝔹-annotated evaluation is the plain evaluation of the support of the database, and this transfers along any m-semiring homomorphismK → 𝔹. This is the equality that replacesℕ-adequacy (Benzaken, Cohen-Boulakia, Contejean, Keller & Zucchini) beyond the positive fragment.Provenance.Circuit– Boolean circuits with structural predicates and two recursive bottom-up probability evaluators: the read-once evaluator with the inclusion-exclusion correction at OR gates (Circuit.prob), and the d-D evaluator with direct summation at OR gates under decomposability + determinism (Circuit.probDD). Both evaluators are proved correct against the sum-over-valuations semantics (Sen, Maniu & Senellart, Section V-D step 1).Provenance.CategoricalBlock– the categorical-block counterpart ofProvenance.Circuit's d-D weighted-model-counting correctness: an independent re-proof over categorical block variables (the free Boolean case is theκ ≡ fun _ => Boolinstance). ACatAssignmentgives each block its own categorical distribution,CatCircuithas block-outcome literals, andCatCircuit.dD_eventProb_eq_probDDproves the direct-summation evaluator correct on decomposable + deterministic categorical circuits. The three block lemmas (CatAssignment.mulin_disjoint,mulin_or_prob,mulin_none) andsingleBlock_detOR_soundback ProvSQL's trust in the deterministic-OR (plus(mulinputs)) mark and the1 - Σ pᵢnone-branch of the bounded-treewidthrepair_key/ BID route (evaluateCertifiedIsland).Provenance.HavingProbability– probability identities for evaluatingHAVING-style aggregate comparisons under contributor independence: given pairwise-disjoint contributor variable supports (so contributors are independent Bernoullis with marginalsp i = P.funcProb (α i)), the MAX / MIN factorization formulas for all six comparison operators (funcProb_maxLeOnNonempty/funcProb_minGeOnNonemptyand the genericfuncProb_guardedSomecovering the remaining operators), the COUNT / SUM Poisson-binomial-style recurrences (countMass_insert_zero/countMass_insert_succ/sumMass_insert_of_le/sumMass_insert_of_lt), and the CDF assembly around them (funcProb_count_filter, empty-world masscountMass_zero, and the shorter-tail identityfuncProb_count_ge_eq_absent_le).Provenance.DistributionExample–percent_rank,cume_distandntileevaluated on a three-row partition, including a partition of one row and one with peers: the values SQL gives, and the pair of counts the two nested frames supply. Alsorankagainstdense_rank, which part exactly where the order has peers.Provenance.NestedExample– second-level aggregation,sum(count(*))over aGROUP BY, written through the alternatives: the inner count read as a key becomes a regular column, so the outer aggregate is an ordinary one and nothing nested is involved. The alternatives and their annotations are printed, one of them impossible, and with them the gap between a world's answer and the token's deterministic reading that keepsExplodeout ofAggQueryIn.evaluateAnnotated_toPlain.Provenance.HavingExample– worked examples on a three-occurrence group: theSUM ≥ 5possible-world provenance in𝔹[X]and its collapse to minimal worlds (both computed by kernel evaluation), and the Poisson-binomialPr[COUNT(*) ≥ 2] = 7/24computation via the recurrence and CDF assembly.Provenance.HavingQueryCorrectness– query-level correctness of the fusedHavingoperator against the JOIN-based rewriting, in absorptive m-semirings (⊗-over-⊖distributivity is needed for<,≤,=,≠only; the monotone≥and>cases hold without it,Query.joinCount_monotone_correct): theC = 1case (AggQueryIn.havingSite_count_ge_one, the fusedCOUNT(*) ≥ 1site equals the duplicate-eliminated key projection) and the general case (Query.joinChain_count_correct, theC-fold self-join chain with a lexicographic occurrence-identifier tie-break gives every key the⊕-sum of its(C+1)-element world monomials, the fusedCOUNT(*) ≥ C + 1provenance), via the extensional characterizationgroupByKey_eq_dedup_mapof duplicate elimination and the chain algebrachainAgg/esymmProvenance.HavingJoinCompositional– the JOIN rewriting upgraded from extensional (per-key annotation sums) to intensional, multiset-level equality: the padded rewritingjoinCountQueryPadded(the join query unioned with the𝟘-annotated self-difference of the key query, then duplicate-eliminated) evaluates to exactly one row per group key with the fused predicate provenance (joinCountQueryPadded_correct; for≥and>,joinCountQueryPadded_monotone_correctwithout distributivity), which is precisely the key projection of the fused output (fused_key_proj); the combinedcountHaving_site_rewrite(countHaving_site_rewrite_monotone) makes the substitution transparent to every surrounding operator – padding matters, since a bare “equal up to𝟘-rows” relation is not a congruence for enclosing aggregates. The compositional query-to-query form of the rewriting lives on the general syntax (GenCountHavingRewrite, inProvenance.AggQueryEmbedding)Provenance.HavingMonotone– monotoneHAVINGconditions, for which absorptivity suffices: the existential comparisonsMIN(t) ≤ c,< c,MAX(t) ≥ c,> crewrite asε(Π_{#0}(σ_{t op c}(q)))(existential_site_rewrite,minLe_site_rewrite…), and the syntaxMonoCondof positive Boolean combinations ofCOUNT(*) ≥ C,> Cand existential atoms comes with the compositional rewritingMonoCond.rewrite(conjunction as join on the group key, disjunction as set union), the closed formMonoCond.site_evaluateAnnotatedof the fused site of a compound condition in the general evaluator, and the site substitutionMonoCond.site_rewrite, all without distributivity of⊗over⊖Provenance.HavingQueryCounterexamples–decide-checked counterexamples, at the level of queries evaluated on concrete annotated databases, showing that the HAVING / JOIN correspondence forCOUNT(*)needs both absorptivity (tropical overℤ ∪ {∞}, for≥) and⊗-over-⊖distributivity (ChainFive, for=), and that the≥correspondence does close inChainFive(HavingQueryCounterexamples.ChainFive.query_ge_agree). It also witnesses that the collapse of a count needs absorptivity: overℕ, two occurrences annotated1and2give a possible-world sum of2, the product, because every world omitting one of them is killed by the monus – neither the⊕-sum3that the absorptive collapse gives nor the indicator reading𝟙(natCountToken_ne_sum,natCountToken_ne_delta). The∨rule is witnessed not to be a decomposition of the one sum over the union of the disjuncts' families, in𝔹and inℕ(bool_or_ne_joint,nat_or_ne_joint), the𝔹instance closing at row level where theℕone does not. Beside them,joint2andjoint3are the one-sum readings over two and three families, and: the two alternatives of a Boolean aggregate column overcount – overℕthey carry2where the worlds of the two families together carry𝟙, which is what every non-Boolean column's alternatives carry (nat_or_alternatives_ne_support); a searchedCASEsplits into its branches without double counting, since the guards exclude each other, in every m-semiring and with no hypothesis on it (Having.joint2_branch_split), the second branch's guard being the test that the first is not true and not its negation, which would be𝟘where the guard is unknown; but the split parts from the one sum over the union as soon as two branches read different families, with no disjunction anywhere in the query (natCase_ne,1against2overℕ). And inclusion–exclusion is not the joint reading of a disjunction:S₁ ⊕ S₂ ⊖ S₁ ⊗ S₂holds overℕ(nat_incl_excl_eq) and fails in𝔹(bool_incl_excl_ne), where⊤ ⊕ ⊤ ⊖ ⊤ ⊗ ⊤is⊥while both sides hold – the overlap is not a quantity to remove, and where⊕is idempotent it was never counted twice. Min-max is the row where the two roads to killing an invented world of a nested aggregate – an exclusive⊕, or aδsaturating to𝟙– are both closed, and the instances say so: overℕthe world that keeps an inner occurrence of a dropped outer one is annotated𝟘(nat_incoherentWorld_eq_zero), over min-max it is not (mm_incoherentWorld_ne_zero), since𝟙 ⊖ g = 𝟙there. Min-max does nonetheless keep the row-level absorption of the∨rule, in every configuration of the two tests (mm_row_agree_one,mm_row_agree_both,mm_row_agree_neither) – soδ = idsuffices for that whereChainFiveshowed an idempotent⊕does not. Both instances are also stated against the definition itself rather than against a sum written family by family –natOrExprandnatCaseExprare the two Boolean functions asAggExprs over one shared family, andnatOrExpr_ne_structuralandnatCaseExpr_ne_splitare the same two numbers read offAggExpr.predProv. At the row level the picture differs and the file says so: what an implementation reports isδ(β₁) ⊗ δ(β₂) ⊗ predsem(ψ), and over𝔹those factors close the gap the∨rule opens (bool_row_agree), so the𝔹instance is about the predicate provenance and not about the row. An idempotent⊕is not what closes it:ChainFiveis absorptive, hence⊕-idempotent, and itsδis not the identity, and there the reported row ishiwhere the joint reading islo(chain_row_ne).Provenance.Tseitin– the Tseitin CNF transformation encoding a circuit as an equisatisfiable CNF overX ⊕ Circuit X. Provides syntacticLiteral/Clause/CNFtypes, the Tseitin encoder, and the bidirectional equisatisfiability theoremCircuit.tseitin_equisat(Sen, Maniu & Senellart, Section V-D step 3, before the knowledge compiler is invoked).
Algorithms
Provenance.Algorithms.CompOp– shared comparison-operator type used by the HAVING enumeration algorithms and by the predicate languages: the six comparisons, whichCompOp.strictmarks as unknown on a null operand, and the two syntactic ones (syneq,synne) which are notProvenance.Algorithms.CountEnum– enumeration of valid possible worlds forHAVING count op Cpredicates: definitions ofcombinations,addExact, andcountEnum, together with the correctness theoremcountEnum_correctProvenance.Algorithms.SumDP– subset-sum enumeration of valid possible worlds forHAVING sum(t) op Cpredicates: definition ofsumExactandsumDP, together with the correctness theoremsumDP_correct
Complexity
Provenance.HavingComplexity– deciding whetherHAVING SUMprovenance over anℕ[X]-instance is non-𝟘is NP-complete, already in data complexity (havingSumNonzero_NP_complete). Built on the descriptive-complexity library: membership isKnapsackcut down by one first-order sentence, and hardness is a padding FO reduction fromKnapsack, hence stronger than a Karp reduction. The bridge to the semiring semantics ishavingSumProv_ne_zero_iff, andhavingSumNonzeroHow_faithfulcloses the loop on the other side: a concrete group – a list of aggregate values and a constant – is encoded with its size bounds discharged, so the statement is about values written in binary;exists_concreteNonemptySubsetSum_iffcloses it in the decoding direction, which is what carries the hardness back to concrete groups. In unary the problem is tractable, by the very dynamic program ofProvenance.Algorithms.SumDP
Extensionality: which m-semirings annotate a query and not its spelling
Provenance.BooleanSemiring– the m-semirings in which⊕and⊗are a bounded distributive lattice (IsLatticeSemiring: absorptive,⊗idempotent) and those in which𝟙 ⊖ ·is moreover a complement (IsBooleanSemiring), with their points, the semiring homomorphisms onto𝔹: they separate the elements of a lattice m-semiring (IsLatticeSemiring.eq_of_forall_point, off Mathlib's prime separation theorem), preserve the monus of a Boolean one (IsBooleanSemiring.map_monus), and are m-semiring homomorphisms whenδis the identity (IsBooleanSemiring.pointHom)Provenance.FragQuery– the first levels of the chain of SQL fragments as a syntax of their own,FragQueryIn:F₀(projection, selection, product, apply, union, constants),F₁(with duplicate elimination and the semijoin,EXISTSandIN) andF₂(with the difference and the antijoin), read in the general syntax byFragQueryIn.toAgg, with the closed forms of both semantics (FragQueryIn.sem,FragQueryIn.semPlain) and the bridgesFragQueryIn.toAgg_evaluateAnnotatedandFragQueryIn.toAgg_evaluatePlainProvenance.FragQueryMeta– that semantics under a semiring homomorphism that need not preserveδ(FragQueryIn.sem_mapAnn), over𝔹, where a tuple is in the support of the result exactly when it is in the plain result of the support (FragQueryIn.mem_support_sem), and overℕ, where an annotation read as a multiplicity gives the plain semantics of the unfolded instance onF₀(FragQueryIn.semPlain_unfold)Provenance.SemanticExtensionality– extensionality for every semantics that extends semiring provenance. Over any semiring, a semantics following the clauses of semiring provenance on the positive operators, for all arguments and with nothing asked on negation, is extensional forF₂only if the semiring is a Boolean algebra (FragQueryIn.ExtendsSemiringProvenance.isBooleanRig_of_level2); over a commutative m-semiring such a semantics exists iff it is a Boolean m-semiring (exists_semantics_extensional_iff). The copies themselves need not agree fromF₂on (FragQueryIn.splitR_semPlain,FragQueryIn.splitR_sem,FragQueryIn.splitR_copies_ne).Provenance.Extensionality– graded extensionality.Kis extensional for a class of queries (Extensional) when two queries of the class with the same plain semantics on every instance collapse, on everyK-instance, to the same K-relation (AnnotatedRelation.annSum). Every commutative m-semiring is extensional forF₀(extensional_level0, by a polynomial identity overℕ[K]), and on the classical layer the swapped product forces the commutativity of⊗(mul_comm_of_extensional_swap);Kis extensional forF₁iff it is a lattice m-semiring (extensional_level1_iff), forF₂iff it is a Boolean m-semiring (extensional_level2_iff), and for the whole recursion-free algebra under the hygiene of the metatheory (AggQueryIn.Tame) iff it is a Boolean m-semiring whoseδis the identity (extensional_tame_iff). Each axiom is forced by one pair of equivalent queries on a one-tuple instance; the converses go through the points
Concrete m-semirings (Provenance.Semirings.*)
Provenance.Semirings.Bool– the Boolean m-semiring𝔹Provenance.Semirings.BoolFunc– the Boolean-function m-semiring𝔹[X]Provenance.Semirings.Why– the Why[X] m-semiring (sets of witness sets)Provenance.Semirings.Which– the Which[X] m-semiring (lineage / Lin[X])Provenance.Semirings.How– the ℕ[X] m-semiring of multivariate polynomials; the universal provenance semiringProvenance.Semirings.Nat– the counting m-semiringℕProvenance.Semirings.Tropical– the tropical m-semiring (min-plus) overℕ ∪ {∞},ℚ ∪ {∞}, orℝ ∪ {∞}; theℝinstance is also used as a counterexample showing that the absorptive hypothesis ofHaving.F_eq_Sand of theMIN/MAX/PICKFIRSTscan collapses (MinTropicalR.minScan_ne_prov) is genuinely required (idempotent +⊗-over-⊖distributive is not enough)Provenance.Semirings.Viterbi– the Viterbi m-semiring (max-times) over[0,1]Provenance.Semirings.MinMax– the min-max semiring over any bounded linear order (security / access control semiring and dual fuzzy semiring)Provenance.Semirings.Lukasiewicz– the Łukasiewicz (fuzzy logic) m-semiring overℚ ∩ [0,1]Provenance.Semirings.ChainFive– a five-element chain m-semiring, absorptive but without⊗-over-⊖distributivity; witnesses that the distributivity hypothesis ofHaving.world_bound(hence of theHAVING count =/≤identities) is genuinely requiredProvenance.Semirings.Interval,Provenance.Semirings.IntervalUnion– intervals and finite unions of intervals over a dense linear order, used for temporal databasesProvenance.Semirings.Security– the alternative security semiringS′ = 𝔹^Lof Amsterdamer, Deutch and Tannen: the subsets of a set of clearance levels, a tuple annotated with the levels at which it may be seen. It is the instance atSet LofBooleanAlgebra.toSemiringWithMonus, which reads any Boolean algebra as an m-semiring (⊕ = ⊔,⊗ = ⊓,a ⊖ b = a ∖ b,δ = id) and proves there, once, every property the library states of an m-semiring: both idempotences, absorptivity, exclusivity, complementedness and⊗-over-⊖distributivity. That construction is adefand not an instance on purpose –Bool,Prop,Set αandα → Boolare all Boolean algebras, so a global instance would collide with the catalog's own𝔹and𝔹[X]instances – andSecurityis its own type for the same reasonProvenance.Semirings.Regex– the regular-expression semiring (ProvSQL'ssr_regex, 1.13.0): languages over the labels of the input tuples,⊕the union,⊗the concatenation, a product gate concatenating its factors in the order of the query. The first entry of the catalog whose⊗does not commute (not_commutative), on Mathlib'sLanguage. An m-semiring all the same: the monus is the difference of languages, which ProvSQL declines to compute but which exists, andδthe indicator of non-emptiness. Idempotent, complemented, neither absorptive nor exclusive, and every value has a Kleene star with the identities ProvSQL's simplifier applies (kstar_one_add,kstar_kstar,kstar_zero,kstar_one)Provenance.Semirings.TropicalPaths– the min-cost-paths semiring (sr_tropical_paths): a cost with every derivation of that cost as a language,⊕keeping the lower cost and merging the languages on a tie,⊗adding the costs and concatenating.⊕is the join of the lexicographic order of the costs reversed and the languages by inclusion, with𝟘at the bottom, and the monus that order determines (the difference of the languages on a tie) makes it an m-semiring, again one ProvSQL declines to compute. The star it implements is verified against the fixpoint equation it solves:𝟙for a positive cost,(0, L∗)for a cost0, and no solution for a negative one (no_fixpoint_of_neg), which is the refusalrecursion-cycle-no-valueProvenance.Semirings.BestPath– the one-best-derivation semiring (sr_best_path): a cost with one word of labels, the better value being the cheaper one and, at equal costs, the shortlex-smaller word;⊕the better of two, so the values are a chain with𝟘at the bottom,⊗the concatenation with the costs added. Selective, idempotent, non-commutative, complemented, with⊗distributing over the monus on both sides, and absorptive on both sides for nonnegative costs (absorptive_of), which is what lets ProvSQL solve a recursion in it by Dijkstra's algorithm
Published papers
Provenance.Papers.Icde2026– a frozen restatement of the claims of Sen, Maniu & Senellart, each proved by applying the declaration the paper links to. Its statements are fixed at publication and never edited to follow the library, so a generalization keeps compiling while a weakening breaks the build; together withscripts/check-anchors.sh, which reads itsAnchor:lines, it is what keeps the paper's hyperlinks honest
See Provenance.Example for an example annotated database computation.
Related formalizations #
Benzaken, Cohen-Boulakia, Contejean, Keller & Zucchini
formalize K-relations in Coq/Rocq, for the positive relational algebra extended
with a single top-level aggregate, and prove an adequacy theorem: at K = ℕ,
the annotated semantics computes exactly the standard bag semantics of the
relational algebra. Their positivity restriction is essential to that theorem:
ℕ-adequacy fails as soon as monus-based difference interacts with duplicate
elimination (Nat.counterexample_diff_adequacy in
Provenance.QueryAdequacy). This library covers the non-monotone m-semiring
extension instead – monus difference, duplicate elimination, compositional
aggregation – and therefore anchors correctness differently: through
homomorphism commutation (Provenance.QueryAnnotatedDatabaseHom), the
rewriting correctness theorems (Query.rewriting_valid,
AggQueryIn.rewritesTo_valid), the possible-worlds adequacy of the
Boolean-function annotated semantics (randomWorld_evaluateAnnotated in
Provenance.Probability), the 𝔹-support adequacy and its transfer along
monus homomorphisms (Provenance.SupportAdequacy), and the data-part
adequacy results of Provenance.QueryAdequacy. Conversely, this library
does not treat NULL
values, correlated subqueries, or a SQL surface syntax, which the Coq/Rocq
development inherits from Datacert.
References #
- Green, Karvounarakis & Tannen, Provenance Semirings
- Geerts & Poggi, On database query languages for K-relations
- Green & Tannen, The Semiring Framework for Database Provenance
- Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data
- Benzaken, Cohen-Boulakia, Contejean, Keller & Zucchini, A Coq formalization of data provenance