Documentation

Provenance.Semirings.BestPath

The one-best-derivation m-semiring (ProvSQL's sr_best_path) #

A value is ๐Ÿ˜, or a cost c with a word w of labels โ€“ one derivation of a tuple, with its cost โ€“ and a value is better than another when its cost is lower or, at equal costs, when its word comes first in shortlex order (shorter first, then lexicographic). sr_best_path (src/semiring/BestPath.h, since 1.13.0) computes in it:

The chain is the natural order of the semiring, better being greater: the LinearOrder of BestPathVal is the dual of the shortlex-with-cost key, with ๐Ÿ˜ adjoined at the bottom. What makes the semiring laws hold is that this key is compatible with concatenation on both sides (key_mul_le_mul_right, key_mul_le_mul_left), strictly, which is also what gives the distributivity of โŠ— over the monus on both sides (mul_sub_left_distributive_of, mul_sub_right_distributive_of) that BestPath.h claims. ProvSQL's two further claims: with nonnegative costs ๐Ÿ™ is the best value, so the semiring is absorptive on both sides (absorptive_of, which asks 0 โ‰ค c of every cost โ€“ ProvSQL refuses a negative cost at the leaves, semiring-negative-cost), and every star is then ๐Ÿ™. Without the cost hypothesis the semiring laws still hold; only absorptivity does not.

The costs are any linearly ordered cancellative additive monoid (โ„, โ„โ‰ฅ0, โ„•), the labels any linearly ordered type (ProvSQL compares them bytewise).

structure BestPathVal (C ฮ› : Type) :

A cost and a word of labels: a value of sr_best_path other than ๐Ÿ˜.

  • cost : C
  • word : List ฮ›
Instances For
    Dependency graph
    def BestPathVal.key {C ฮ› : Type} (p : BestPathVal C ฮ›) :

    The key a value is compared by: its cost, then the length of its word, then the word itself in lexicographic order. Smaller is better.

    Equations
    Instances For
      Dependency graph
      Dependency graph
      @[instance_reducible]

      The chain: better is greater.

      Equations
      Dependency graph
      def BestPathVal.mul {C ฮ› : Type} [AddCommMonoid C] (p q : BestPathVal C ฮ›) :
      BestPathVal C ฮ›

      Concatenation, with the costs added.

      Equations
      Instances For
        Dependency graph
        def BestPathVal.one {C ฮ› : Type} [AddCommMonoid C] :
        BestPathVal C ฮ›

        The empty derivation at cost 0.

        Equations
        Instances For
          Dependency graph
          structure BestPath (C ฮ› : Type) :

          The one-best-derivation semiring: a value of sr_best_path, with ๐Ÿ˜ at the bottom of the chain. A structure of its own, so that the chain's order and the operations below are found on it and not on Option.

          Instances For
            Dependency graph
            def BestPath.keyW {C ฮ› : Type} (a : BestPath C ฮ›) :

            The chain's key: โŠฅ for ๐Ÿ˜, the dual of the value's key otherwise.

            Equations
            Instances For
              Dependency graph
              Dependency graph
              @[instance_reducible]
              instance BestPath.instLinearOrder {C ฮ› : Type} [LinearOrder C] [LinearOrder ฮ›] :
              Equations
              Dependency graph
              @[instance_reducible]
              instance BestPath.instAdd {C ฮ› : Type} [LinearOrder C] [LinearOrder ฮ›] :
              Add (BestPath C ฮ›)

              โŠ• is the better of two values: the maximum of the chain.

              Equations
              Dependency graph
              @[instance_reducible]
              instance BestPath.instZero {C ฮ› : Type} :
              Zero (BestPath C ฮ›)
              Equations
              Dependency graph
              theorem BestPath.zero_le' {C ฮ› : Type} [LinearOrder C] [LinearOrder ฮ›] (a : BestPath C ฮ›) :
              Dependency graph
              @[instance_reducible]
              instance BestPath.instMul {C ฮ› : Type} [AddCommMonoid C] :
              Mul (BestPath C ฮ›)

              โŠ— concatenates, adding the costs; ๐Ÿ˜ absorbs.

              Equations
              Dependency graph
              @[instance_reducible]
              instance BestPath.instOne {C ฮ› : Type} [AddCommMonoid C] :
              One (BestPath C ฮ›)
              Equations
              Dependency graph
              theorem BestPath.one_def {C ฮ› : Type} [AddCommMonoid C] :
              Dependency graph
              theorem BestPath.some_mul_some {C ฮ› : Type} [AddCommMonoid C] (p q : BestPathVal C ฮ›) :
              { val := some p } * { val := some q } = { val := some (p.mul q) }
              Dependency graph
              theorem BestPath.none_mul {C ฮ› : Type} [AddCommMonoid C] (a : BestPath C ฮ›) :
              { val := none } * a = { val := none }
              Dependency graph
              theorem BestPath.mul_none {C ฮ› : Type} [AddCommMonoid C] (a : BestPath C ฮ›) :
              a * { val := none } = { val := none }
              Dependency graph
              theorem BestPath.mul_right_mono {C ฮ› : Type} [LinearOrder C] [LinearOrder ฮ›] [AddCommMonoid C] [IsOrderedCancelAddMonoid C] (r : BestPath C ฮ›) :
              Monotone fun (a : BestPath C ฮ›) => a * r

              โŠ— r is monotone in the chain.

              Dependency graph
              theorem BestPath.mul_left_mono {C ฮ› : Type} [LinearOrder C] [LinearOrder ฮ›] [AddCommMonoid C] [IsOrderedCancelAddMonoid C] (r : BestPath C ฮ›) :
              Monotone fun (a : BestPath C ฮ›) => r * a
              Dependency graph
              @[instance_reducible]
              Equations
              • One or more equations did not get rendered due to their size.
              Dependency graph
              Dependency graph
              Dependency graph
              noncomputable def BestPath.deltaInd {C ฮ› : Type} [LinearOrder C] [LinearOrder ฮ›] [AddCommMonoid C] (a : BestPath C ฮ›) :
              BestPath C ฮ›

              ProvSQL's BestPath::delta: the indicator of being non-๐Ÿ˜.

              Equations
              Instances For
                Dependency graph
                Dependency graph
                Dependency graph
                theorem BestPath.natCast_pos {C ฮ› : Type} [LinearOrder C] [LinearOrder ฮ›] [AddCommMonoid C] [IsOrderedCancelAddMonoid C] {n : โ„•} (hn : 0 < n) :
                โ†‘n = 1
                Dependency graph
                @[instance_reducible]

                The one-best-derivation semiring is an m-semiring: a โŠ– b is a where a is strictly better than b and ๐Ÿ˜ otherwise, the least c with a โ‰ค b โŠ• c in a chain.

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