Documentation

Provenance.ProvsqlExample

A worked query against ProvSQL's own answer #

A left outer join of three departments with three employees, a rank and an average over each department, and the three rows a total order and LIMIT 3 keep. ProvSQL computes the provenance of each candidate row on this instance; everything below is that answer, checked in the kernel. What it checks is the system's output and not the semantics alone, so a disagreement is a finding about one of the two and not something to fit.

What is checked. q1_data gives the six candidate rows; q1_ann and q2_ann give their annotations as Boolean functions of the six tokens, compared against ProvSQL's sr_boolexpr at all 64 valuations; and world_all, world_noA1, world_noB1 give the rows the query returns in three worlds – both window columns and the LIMIT – by evaluating it plainly on that world's instance.

The shape is the query's own. The two window columns are two windows stacked over the join, the second carrying the first one's column through, and the ORDER BY … LIMIT 3 sits above both, which is where SQL evaluates it: a window reads its whole partition and not the truncated relation.

What had to be encoded differently, and why.

Agreement. Every row's annotation is ProvSQL's, as a Boolean function. The one place the two readings are worded differently is the average of a padded row: ProvSQL prints NaN, which it takes for a display artefact, and the semantics says null – world_noB1.

The six tokens: dA, dB, dC, a1, a2, b1.

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

                  Boolean functions of six variables, computably #

                  The library's DecidableEq (BoolFunc X) is Classical.decEq, which the kernel cannot reduce, and there is no linear order on BoolFunc X at all – so an annotated evaluation over 𝔹[X] cannot be computed. Both come from the truth table here: a function of six variables is its 64 values, and a list of booleans is ordered and has decidable equality.

                  The valuation whose bits are those of k.

                  Equations
                  Instances For
                    Dependency graph

                    The truth table of a Boolean function of the six tokens.

                    Equations
                    Instances For
                      Dependency graph
                      Dependency graph
                      @[instance_reducible]

                      The order the group and frame sorts read annotations in.

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

                          A ↦ 1, B ↦ 2, C ↦ 3; names 10, 20, 30; ids 101, 102, 201.

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            Dependency graph
                            @[reducible, inline]
                            Equations
                            • One or more equations did not get rendered due to their size.
                            Instances For
                              Dependency graph
                              Dependency graph

                              The query #

                              dept LEFT JOIN emp ON e.dept = d.dept, spelled in the core syntax rather than through AggQueryIn.leftOuter: the derived form carries AggQueryIn.castKind, and a cast along a proof is what the kernel cannot reduce, so a decide through it is impossible. Writing each projection's column family as a function of the column index keeps the kinds constant by reduction, which is what lets the two arms meet and the whole query evaluate in the kernel.

                              The five columns are d.dept, d.name, e.id, e.dept, e.salary.

                              Dependency graph
                              @[reducible, inline]

                              The identity projection on the five columns, which brings the kinds to the constant form the other arm has.

                              Equations
                              Instances For
                                Dependency graph
                                @[reducible, inline]

                                The matching pairs.

                                Equations
                                • One or more equations did not get rendered due to their size.
                                Instances For
                                  Dependency graph
                                  @[reducible, inline]

                                  The two department columns of a join row.

                                  Equations
                                  Instances For
                                    Dependency graph
                                    @[reducible, inline]

                                    The departments with no employee.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      @[reducible, inline]

                                      Padding such a department with three nulls.

                                      Equations
                                      Instances For
                                        Dependency graph
                                        Dependency graph

                                        The two window columns, and the ORDER BY … LIMIT 3 over them #

                                        rank() OVER (PARTITION BY d.dept ORDER BY e.salary DESC) and avg(e.salary) OVER (PARTITION BY d.dept) are two columns of one SELECT, so they are two windows stacked over the join: the second sits over a relation that already holds the first one's aggregate column and carries it through (AggQueryIn.Win reads the regular columns of its input, ColKind.readTuple). The ORDER BY … LIMIT 3 then sits above both, which is where SQL evaluates it – a window reads the whole partition and not the truncated relation.

                                        The truncation is spelled by hand rather than through AggQueryIn.truncate: that one goes through rank, whose column is 1 + count and whose kinds need AggQueryIn.castKind, and a cast along a proof is what the kernel cannot reduce. Counting the rows that sort ahead and keeping ≤ 2 is the same condition as rank ≤ 3, and needs no cast.

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

                                          The counting aggregate: how many rows the frame holds.

                                          Equations
                                          Instances For
                                            Dependency graph
                                            @[reducible, inline]

                                            SQL's avg: the mean of the non-null values, null over none.

                                            Equations
                                            Instances For
                                              Dependency graph
                                              @[reducible, inline]

                                              rank() OVER (PARTITION BY d.dept ORDER BY e.salary DESC), as the count of the rows ahead – the rank is one more. Column 5.

                                              Equations
                                              • One or more equations did not get rendered due to their size.
                                              Instances For
                                                Dependency graph
                                                @[reducible, inline]

                                                The kinds of the relation the second window sits over: five regular columns and the rank count.

                                                Equations
                                                Instances For
                                                  Dependency graph
                                                  @[reducible, inline]

                                                  avg(e.salary) OVER (PARTITION BY d.dept) beside it, carrying the rank column through. Column 6.

                                                  Equations
                                                  • One or more equations did not get rendered due to their size.
                                                  Instances For
                                                    Dependency graph
                                                    @[reducible, inline]

                                                    salary DESC NULLS LAST, id ASC, dept ASC.

                                                    Equations
                                                    Instances For
                                                      Dependency graph
                                                      @[reducible, inline]

                                                      The three order columns: e.salary, e.id, d.dept.

                                                      Equations
                                                      Instances For
                                                        Dependency graph
                                                        @[reducible, inline]

                                                        The kinds of the windowed relation: five regular columns and the two window columns.

                                                        Equations
                                                        Instances For
                                                          Dependency graph
                                                          @[reducible, inline]

                                                          How many rows sort strictly ahead of a row's peers, over the windowed relation: rank - 1 in the total order the ORDER BY names.

                                                          Equations
                                                          • One or more equations did not get rendered due to their size.
                                                          Instances For
                                                            Dependency graph
                                                            Dependency graph
                                                            @[reducible, inline]

                                                            The whole query: the join, the two window columns, the LIMIT, and the counting column dropped again – the two window columns carried through by AggQueryIn.dropRank.

                                                            Equations
                                                            Instances For
                                                              Dependency graph

                                                              The query's rows, world by world #

                                                              Each world is read by evaluating the query plainly on that world's instance (AnnotatedDatabase.randomWorld), which is SQL on that sub-instance: the join, both window columns at once, and the three rows the LIMIT keeps. The rank is 1 + the counting column, as rank has it.

                                                              @[reducible, inline]

                                                              Every token true.

                                                              Equations
                                                              Instances For
                                                                Dependency graph
                                                                @[reducible, inline]

                                                                a1 absent.

                                                                Equations
                                                                Instances For
                                                                  Dependency graph
                                                                  @[reducible, inline]

                                                                  b1 absent.

                                                                  Equations
                                                                  Instances For
                                                                    Dependency graph