Documentation

Provenance.Notation

Surface syntax for kind-indexed queries #

Writing an AggQuery by hand is dominated by bookkeeping rather than by the query: a column reference carries a proof that its column is regular, a projection's kind vector is computed from its columns, and duplicate elimination and difference demand a kind vector that is syntactically all-regular. None of that is the query, and all of it has to be written out.

This module gives a bracketed surface syntax in which it is not. Inside RA[ … ] the parser knows whether it is reading a term, a predicate or a query, so the elaboration inserts the wrappers and discharges the kind obligations:

RA[ ε (π[#3] (σ[#0 < #4 ∧ #3 = #7] (rel 4 "Personnel" × rel 4 "Personnel"))) ]

Three things follow from the syntax living in categories of its own rather than in notation over terms.

Column references are positional: #i is column i, counting from zero, of the query the surrounding operator reads.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    Dependency graph

    Terms over the columns of a query.

    Equations
    Instances For
      Dependency graph
      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        Dependency graph

        Predicates over the columns of a query.

        Equations
        Instances For
          Dependency graph
          Dependency graph
          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            Dependency graph

            Terms #

            Dependency graph
            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              Dependency graph

              A Lean term, as a constant of the query language.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                Dependency graph
                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  Dependency graph
                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    Dependency graph
                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      Dependency graph

                      Predicates #

                      Equations
                      • One or more equations did not get rendered due to their size.
                      Instances For
                        Dependency graph
                        Equations
                        • One or more equations did not get rendered due to their size.
                        Instances For
                          Dependency graph
                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            Equations
                            • One or more equations did not get rendered due to their size.
                            Instances For
                              Dependency graph
                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For
                                Equations
                                • One or more equations did not get rendered due to their size.
                                Instances For
                                  Dependency graph
                                  Equations
                                  • One or more equations did not get rendered due to their size.
                                  Instances For
                                    Dependency graph
                                    Dependency graph
                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      Dependency graph
                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      Instances For
                                        Dependency graph

                                        Columns and aggregated columns #

                                        Grouping reads two lists that are not terms: the key columns, which are indices, and the aggregated columns, each a term paired with the aggregate applied to it.

                                        Equations
                                        • One or more equations did not get rendered due to their size.
                                        Instances For
                                          Dependency graph

                                          A column of the query being read.

                                          Equations
                                          Instances For
                                            Dependency graph
                                            Dependency graph
                                            Equations
                                            • One or more equations did not get rendered due to their size.
                                            Instances For
                                              Dependency graph

                                              One output column of a projection: a term, or a bare column reference carried through whatever its kind.

                                              Equations
                                              Instances For
                                                Dependency graph
                                                Dependency graph
                                                Equations
                                                • One or more equations did not get rendered due to their size.
                                                Instances For
                                                  Dependency graph

                                                  One aggregated column: a term and the aggregate applied to it. The aggregate is an ordinary Lean term of type SeqAggFunc, so the catalog is open – SeqAggFunc.sum, SeqAggFunc.sum, and anything else of that type.

                                                  Equations
                                                  Instances For
                                                    Dependency graph
                                                    Equations
                                                    • One or more equations did not get rendered due to their size.
                                                    Instances For
                                                      Dependency graph

                                                      Queries #

                                                      Equations
                                                      • One or more equations did not get rendered due to their size.
                                                      Instances For
                                                        Dependency graph
                                                        Equations
                                                        • One or more equations did not get rendered due to their size.
                                                        Instances For
                                                          Dependency graph

                                                          A query already written in Lean.

                                                          Equations
                                                          • One or more equations did not get rendered due to their size.
                                                          Instances For
                                                            Dependency graph
                                                            Equations
                                                            • One or more equations did not get rendered due to their size.
                                                            Instances For
                                                              Dependency graph
                                                              Equations
                                                              • One or more equations did not get rendered due to their size.
                                                              Instances For
                                                                Dependency graph
                                                                Dependency graph

                                                                Grouping. With no keys before the ; this is aggregation without grouping, whose single row exists even over an empty input – the absence of a GROUP BY is what makes an aggregation scalar, here as in SQL.

                                                                Equations
                                                                • One or more equations did not get rendered due to their size.
                                                                Instances For
                                                                  Dependency graph

                                                                  A window. Before the aggregated column come the partition columns, the order columns, the ORDER BY clause and the frame: ⊞[#0 ; #1 ; o ; w ; #2 : f] q gives every row of q a further column holding f of #2 over that row's frame, which is w read on the order column #1 within the partition given by #0, and read in the order o gives that column. The clause is a term of type OrderSpec (OrderSpec.asc, OrderSpec.desc, or a column-by-column OrderCol), and the frame a term of type ValueFrame, so both catalogs are open – ValueFrame.whole, upTo, before, rangeUpTo o, peerGroup o and the EXCLUDE modifiers of any of them.

                                                                  Equations
                                                                  • One or more equations did not get rendered due to their size.
                                                                  Instances For
                                                                    Dependency graph
                                                                    Equations
                                                                    • One or more equations did not get rendered due to their size.
                                                                    Instances For
                                                                      Dependency graph
                                                                      Equations
                                                                      • One or more equations did not get rendered due to their size.
                                                                      Instances For
                                                                        Dependency graph
                                                                        Equations
                                                                        • One or more equations did not get rendered due to their size.
                                                                        Instances For
                                                                          Dependency graph

                                                                          Bracket around a query of the surface syntax.

                                                                          Equations
                                                                          • One or more equations did not get rendered due to their size.
                                                                          Instances For
                                                                            Dependency graph

                                                                            The same, naming the value type. Only a base relation leaves the value type undetermined – every other operator takes it from its argument – so this is what a query written from the ground up needs, in place of an ascription.

                                                                            Equations
                                                                            • One or more equations did not get rendered due to their size.
                                                                            Instances For
                                                                              Dependency graph

                                                                              Elaboration #

                                                                              Each category expands through an internal marker in the term category, which is what lets a rule recurse into its own sub-syntax. Column references become TermGIn.index with the regularity proof discharged by rfl, which is what a concrete kind vector makes available.

                                                                              @[reducible, inline]

                                                                              A query all of whose columns are regular. This is the shape of a source query before any grouping, and the one an ascription on a base relation needs: the arity determines the kind vector, so naming it again is noise.

                                                                              Equations
                                                                              Instances For
                                                                                Dependency graph
                                                                                def Provenance.Notation.allReg {T : Type} {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery T n κ) (h : κ = ColKind.allReg n := by first | rfl | (funext j; fin_cases j <;> rfl)) :

                                                                                Retag a query whose kind vector is all-regular by computation into the ColKind.allReg form that Dedup and Diff ask for. The obligation is discharged by the tactic on a concrete kind vector, which is what the surface syntax always produces.

                                                                                Equations
                                                                                Instances For
                                                                                  Dependency graph
                                                                                  Equations
                                                                                  • One or more equations did not get rendered due to their size.
                                                                                  Instances For
                                                                                    Dependency graph
                                                                                    Equations
                                                                                    • One or more equations did not get rendered due to their size.
                                                                                    Instances For
                                                                                      Dependency graph
                                                                                      Equations
                                                                                      • One or more equations did not get rendered due to their size.
                                                                                      Instances For
                                                                                        Dependency graph
                                                                                        Equations
                                                                                        • One or more equations did not get rendered due to their size.
                                                                                        Instances For
                                                                                          Dependency graph
                                                                                          Equations
                                                                                          • One or more equations did not get rendered due to their size.
                                                                                          Instances For
                                                                                            Dependency graph

                                                                                            Reading a column #

                                                                                            A column reference says which column, not what is in it. Which atom, or which projection column, that becomes is settled by the kind vector, and the kind vector is concrete on any query one can write – so the two functions below decide it by computation. The surface syntax therefore does not change with the kinds: a comparison against a grouped aggregate is written like any other comparison, as it is in SQL.

                                                                                            def Provenance.Notation.atomAt {T : Type} {n : ℕ} {κ : Fin n → ColKind} (k : Fin n) (op : CompOp) (t : TermG T κ) :
                                                                                            GenPred T κ

                                                                                            The atom comparing column k against a term, whichever kind the column has: a regular comparison on a value column, an aggregate atom on a token column.

                                                                                            Equations
                                                                                            • One or more equations did not get rendered due to their size.
                                                                                            Instances For
                                                                                              Dependency graph
                                                                                              def Provenance.Notation.projAt {T : Type} {n : ℕ} {κ : Fin n → ColKind} (k : Fin n) :
                                                                                              ProjCol T κ

                                                                                              The projection column carrying column k through, whichever kind it has.

                                                                                              Equations
                                                                                              • One or more equations did not get rendered due to their size.
                                                                                              Instances For
                                                                                                Dependency graph

                                                                                                Worked productions #

                                                                                                Every production is exercised below. A surface syntax that elaborates is the only evidence that it parses and that the obligations it hides – the regularity proofs, the kind vectors, the retaggings – really do discharge.