Documentation

Provenance.Database

Tuples, relations, and databases #

This file defines the basic relational model used throughout the library.

Main definitions #

def Tuple (T : Type) (n : ℕ) :
Equations
Instances For
    Dependency graph
    def Tuple.repr {T : Type} {n : ℕ} [Repr T] (t : Tuple T n) :
    Equations
    Instances For
      Dependency graph
      def Tuple.cast {T : Type} {n m : ℕ} (heq : n = m) (t : Tuple T n) :
      Tuple T m
      Equations
      Instances For
        Dependency graph
        Dependency graph
        @[instance_reducible]
        instance instReprTuple {α : Type} {n : ℕ} [Repr α] :
        Repr (Tuple α n)
        Equations
        Dependency graph
        @[instance_reducible]
        instance instZeroTuple {T : Type} [ValueType T] {n : ℕ} :
        Zero (Tuple T n)
        Equations
        Dependency graph
        @[instance_reducible]
        instance instLTTuple {T : Type} [ValueType T] {n : ℕ} :
        LT (Tuple T n)
        Equations
        Dependency graph
        @[instance_reducible]
        instance instLETuple {T : Type} [ValueType T] {n : ℕ} :
        LE (Tuple T n)
        Equations
        Dependency graph
        @[instance_reducible]
        instance instToStringTuple {T : Type} {n : ℕ} [ToString T] :
        Equations
        Dependency graph
        @[instance_reducible]
        instance instDecidableRelTupleLt {T : Type} [ValueType T] {n : ℕ} :
        DecidableRel fun (t₁ t₂ : Tuple T n) => t₁ < t₂
        Equations
        Dependency graph
        @[instance_reducible]
        instance instLinearOrderTuple {T : Type} [ValueType T] {n : ℕ} :
        Equations
        • One or more equations did not get rendered due to their size.
        Dependency graph
        def Relation (T : Type) (arity : ℕ) :
        Equations
        Instances For
          Dependency graph
          def Relation.cast {T : Type} {n m : ℕ} (heq : n = m) (r : Relation T n) :
          Equations
          Instances For
            Dependency graph
            @[instance_reducible]
            instance instAddRelation {T : Type} {arity : ℕ} :
            Add (Relation T arity)
            Equations
            Dependency graph
            @[instance_reducible]
            instance instSubRelation {T : Type} [ValueType T] {arity : ℕ} :
            Sub (Relation T arity)
            Equations
            Dependency graph
            @[instance_reducible]
            instance instHMulRelationHAddNat {T : Type} {a₁ a₂ : ℕ} :
            HMul (Relation T a₁) (Relation T a₂) (Relation T (a₁ + a₂))
            Equations
            • One or more equations did not get rendered due to their size.
            Dependency graph
            @[instance_reducible]
            instance instZeroRelation {T : Type} {n : ℕ} :
            Equations
            Dependency graph
            @[instance_reducible]
            instance instZeroSigmaNatRelation {T : Type} :
            Zero ((n : ℕ) × Relation T n)
            Equations
            Dependency graph
            def Database (T : Type) :
            Equations
            Instances For
              Dependency graph
              def Database.find {T : Type} (n : ℕ) (s : String) (d : Database T) :
              Equations
              Instances For
                Dependency graph
                def Database.find.f {T : Type} (n : ℕ) (s : String) :
                Equations
                Instances For
                  Dependency graph
                  def Database.assign {T : Type} (s : String) {k : ℕ} (X : Relation T k) (d : Database T) :

                  Binding a relation name, the I[R ↦ M] of a recursion's rounds. A database is searched front to back, so a binding is a cons: it shadows whatever the name had, and nothing else moves.

                  Equations
                  Instances For
                    Dependency graph
                    def sortedInsert {α : Type u_1} [LinearOrder α] (x : α) (l : { l : List α // List.Pairwise (fun (x1 x2 : α) => x1 ≤ x2) l }) :
                    { l : List α // List.Pairwise (fun (x1 x2 : α) => x1 ≤ x2) l }
                    Equations
                    Instances For
                      Dependency graph
                      Dependency graph
                      def sortList {α : Type} [LinearOrder α] (M : Multiset α) :
                      List α

                      A multiset as a sorted list: the canonical reading of a relation as a sequence. It is computable, where a choice through Multiset.toList is not, and it is determined by the multiset, which is what lets two sequences built from the same rows be recognized as the same sequence.

                      It is an insertion sort rather than Multiset.sort, which is defined by well-founded recursion and does not reduce in the kernel: the evaluators read a relation as a sequence through this, and a decide-checked equation about a computed relation needs every step of it to reduce.

                      Equations
                      Instances For
                        Dependency graph
                        @[instance_reducible]
                        instance instToStringRelation {T : Type} [ValueType T] {n : ℕ} [ToString T] :
                        Equations
                        Dependency graph