Documentation

Provenance.NestedExample

Second-level aggregation, both ways #

sum(count(*)) over a GROUP BY aggregates an aggregate column, and the syntax reads it in two ways. This file writes the query both ways, on a relation whose two groups have different counts.

Through the alternatives (AggQueryIn.Explode): read the aggregate column as a key, replacing each occurrence by its alternatives, one per value the column takes and each carrying [a ≐ v]. The column becomes regular, and every operator applies to a regular column – a grouping included – so the outer aggregate is an ordinary one over an ordinary relation and nothing nested is involved.

Directly (AggQueryIn.GammaNest): aggregate a term that reads the aggregate column. The column this builds is a nested aggregate value (Provenance.Nested), whose occurrences are the inner grouping's rows and whose outer aggregate is a function of the bag of them – it has to be, the order ≼ being an order on plain tuples while an occurrence here carries a tuple with an aggregate column.

The two readings are not the same object. The alternatives explode a row into one per value its column takes, each annotated so that it is present exactly in the worlds where the column has that value; the nested reading keeps one row and reads it world by world. The checks below show where they part: the alternatives' token collapses to 4, which is no world's answer, where the nested token collapses to 3, which is SQL's.

Each check is a theorem closed by decide: the evaluator reads a relation as a sequence through an insertion sort, which the kernel reduces, so the computed value is compared against the expected one by the kernel. The queries built with AggQueryIn.castKind need evaluate_castKind or evaluatePlain_castKind first – the kernel does not reduce a cast along a proof.

Three rows in two groups: 1 twice and 2 once.

@[reducible, inline]
Equations
Instances For
    Dependency graph
    @[reducible, inline]

    The plain database.

    Equations
    Instances For
      Dependency graph
      @[reducible, inline]

      The annotated database, every row annotated 1.

      Equations
      Instances For
        Dependency graph

        The inner grouping: one row per group, carrying its count #

        @[reducible, inline]
        abbrev NestedExample.inner :
        AggQuery ℕ (1 + 1) (Fin.append (fun (x : Fin 1) => ColKind.reg) fun (x : Fin 1) => ColKind.agg)

        SELECT a, count(*) FROM R GROUP BY a.

        Equations
        Instances For
          Dependency graph
          theorem NestedExample.inner_kind :
          Fin.append (fun (x : Fin 1) => ColKind.reg) (fun (x : Fin 1) => ColKind.agg) 1 = ColKind.agg

          The count column is the second one, and it is an aggregate column.

          Dependency graph

          Reading it as a key makes every column regular.

          Dependency graph

          The outer aggregation over the alternatives #

          @[reducible, inline]

          SELECT sum(c) FROM (SELECT a, count(*) AS c FROM R GROUP BY a) t, with the inner count read as a key so that the outer sum aggregates a regular column.

          Equations
          Instances For
            Dependency graph

            What the two sides compute #

            The inner grouping, plainly: one row per group with its count, (1,2) and (2,1).

            The outer aggregation, plainly: 2 + 1 = 3, which is SQL's sum(count(*)). Over a plain relation an aggregate value is a value and Explode is the identity, so the alternatives cost nothing here.

            The alternatives, annotated: one row per (group, value) pair the count can take, each carrying the group's annotation times [c ≐ v]. With every input row annotated 1 over ℕ, the group of 1's has a count of 2 and the group of 2 a count of 1.

            And the outer aggregation's token: its occurrences are the three alternatives, each carrying the alternative's annotation. Printed as (value, annotation):

            the two possible ones contribute 2 and 1, and the impossible one is annotated 0. The sum in a world is 2 + 1 = 3, SQL's answer, and the deterministic reading of the token is 1 + 2 + 1 = 4, which is no world's. That is why equality up to 𝟘 removes the occurrences annotated 𝟘 inside aggregate values as well as the rows annotated 𝟘 (GenRow.zeroNorm), and it is why AggQueryIn.evaluateAnnotated_toPlain excludes Explode: an aggregate column read as a key gives one row per value the column takes in some world, so the data part of the annotated evaluation is not the data part of any one world.

            The direct nested reading #

            AggQueryIn.GammaNest aggregates a term that reads the aggregate column, so it keeps one row per group of its own and the column it builds is a nested token: its occurrences are the inner grouping's rows, each carrying the aggregate value read there. Here there is one group – no key columns – so the token's occurrences are the two rows of inner, and its outer aggregate is sum read off the bag of them (SeqAggFunc.onBag, the aggregate being symmetric).

            @[reducible, inline]
            abbrev NestedExample.outerNest :
            AggQuery ℕ (0 + 1) (Fin.append (fun (k : Fin 0) => k.elim0) fun (x : Fin 1) => ColKind.agg)
            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              Dependency graph

              Plainly it is SQL's answer: 2 + 1 = 3, the same as through the alternatives, an aggregate value being a value over a plain relation.

              The occurrences of its token, annotated: the inner grouping's two rows, each as (the collapse of the inner value, the row's annotation) – the counts 2 and 1, each annotated 1.

              Its deterministic reading is 3 – and not the 4 the alternatives' token collapses to. Nothing is read twice here: the nested token keeps one row and reads it world by world, where Explode explodes the row into one per value its column takes.

              And the values it takes over its worlds: {1, 2, 3}. A world keeps some of the two outer occurrences – at least one, the reading being grouped – and, of each it keeps, some of that group's rows, at least one (World.IsWorld): so the sums available are 1 (either group alone, one row of it), 2 (both groups with one row each, or the first group's two rows) and 3 (everything). 0 is not among them: that would be the empty world, which a grouped reading does not have.