Relational algebra #
This file defines the abstract syntax and semantics of relational algebra queries over plain (unannotated) databases. The language is the extended relational algebra described in Section III of Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data, with multiset semantics, explicit duplicate elimination, multiset difference, and aggregation.
Main definitions #
Term T n– an expression that evaluates to a value of typeTin the context of a tuple of arityn(constants, tuple projections, and arithmetic operations)Query T– a relational algebra query: selection, projection, union, join, difference, and renamingQuery.evaluate– the standard set semantics of queries overDatabase T
References #
- Sen, Maniu & Senellart, ProvSQL (Section III)
- const {T : Sort u_1} {c n : ℕ} : T → TermIn T c n
- outer
{T : Sort u_1}
{c n : ℕ}
: Fin c → TermIn T c n
An outer column: a column of the query this one is applied to. There are none in a closed query,
cbeing0there. - index {T : Sort u_1} {c n : ℕ} : Fin n → TermIn T c n
- add {T : Sort u_1} {c n : ℕ} : TermIn T c n → TermIn T c n → TermIn T c n
- sub {T : Sort u_1} {c n : ℕ} : TermIn T c n → TermIn T c n → TermIn T c n
- mul {T : Sort u_1} {c n : ℕ} : TermIn T c n → TermIn T c n → TermIn T c n
- caseWhen
{T : Sort u_1}
{c n : ℕ}
: CompOp → TermIn T c n → TermIn T c n → TermIn T c n → TermIn T c n → TermIn T c n
SQL's searched
CASE: the third term where the comparison of the first two holds, the fourth – theELSE– where it does not. A guard that is unknown takes theELSE, as SQL has it. TheELSEis a term and not the null, so the constructor asks nothing of the value domain;CASE WHEN φ THEN t ENDis the case where it is the constant null.A guard that is a Boolean combination of comparisons needs no more than this: a conjunction is a nested
CASE, a disjunction iscoalesceof the two cases, and a negation isCompOp.negate. - coalesce
{T : Sort u_1}
{c n : ℕ}
: TermIn T c n → TermIn T c n → TermIn T c n
SQL's
COALESCEof two terms: the first where it is not null, the second where it is. It is not null-strict, which is why it is a constructor and not an arithmetic term.
Instances For
Dependency graph
A term of a closed query: no outer column to read.
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
- (TermIn.const a).repr x✝ = reprArg a
- (#k).repr x✝ = Std.Format.text "#" ++ reprArg k
- (t₁.add t₂).repr x✝ = Repr.addAppParen (t₁.repr x✝ ++ Std.Format.text "+" ++ t₂.repr x✝) x✝
- (t₁.sub t₂).repr x✝ = Repr.addAppParen (t₁.repr x✝ ++ Std.Format.text "-" ++ t₂.repr x✝) x✝
- (t₁.mul t₂).repr x✝ = Repr.addAppParen (t₁.repr x✝ ++ Std.Format.text "*" ++ t₂.repr x✝) x✝
- (t₁.coalesce t₂).repr x✝ = Repr.addAppParen (Std.Format.text "COALESCE(" ++ t₁.repr x✝ ++ Std.Format.text ", " ++ t₂.repr x✝ ++ Std.Format.text ")") x✝
Instances For
Dependency graph
Equations
- instReprTerm = { reprPrec := TermIn.repr }
Dependency graph
Equations
- (TermIn.const c).castToAnnotatedTuple = TermIn.const (Sum.inl c)
- (#k).castToAnnotatedTuple = #(k.castLT ⋯)
- (t₁.add t₂).castToAnnotatedTuple = TermIn.add t₁.castToAnnotatedTuple t₂.castToAnnotatedTuple
- (t₁.sub t₂).castToAnnotatedTuple = TermIn.sub t₁.castToAnnotatedTuple t₂.castToAnnotatedTuple
- (t₁.mul t₂).castToAnnotatedTuple = TermIn.mul t₁.castToAnnotatedTuple t₂.castToAnnotatedTuple
- (TermIn.caseWhen op t₁ t₂ t₃ t₄).castToAnnotatedTuple = TermIn.caseWhen op t₁.castToAnnotatedTuple t₂.castToAnnotatedTuple t₃.castToAnnotatedTuple t₄.castToAnnotatedTuple
- (t₁.coalesce t₂).castToAnnotatedTuple = TermIn.coalesce t₁.castToAnnotatedTuple t₂.castToAnnotatedTuple
Instances For
Dependency graph
Value of a term on a row. An open term also reads an outer
valuation γ, one value per outer column. A closed term reads none, so
the argument defaults to a valuation no one looks at (Fin 0 is empty)
and closed uses write t.eval u.
Equations
- (TermIn.const a).eval tuple γ = a
- (TermIn.outer k).eval tuple γ = γ k
- (#k).eval tuple γ = tuple k
- (t₁.add t₂).eval tuple γ = t₁.eval tuple γ + t₂.eval tuple γ
- (t₁.sub t₂).eval tuple γ = t₁.eval tuple γ - t₂.eval tuple γ
- (t₁.mul t₂).eval tuple γ = t₁.eval tuple γ * t₂.eval tuple γ
- (TermIn.caseWhen op t₁ t₂ t₃ t₄).eval tuple γ = if op.eval3 (t₁.eval tuple γ) (t₂.eval tuple γ) = Kleene.true then t₃.eval tuple γ else t₄.eval tuple γ
- (t₁.coalesce t₂).eval tuple γ = if ValueType.isNull (t₁.eval tuple γ) = true then t₂.eval tuple γ else t₁.eval tuple γ
Instances For
Dependency graph
Equations
- instCoeTerm = { coe := fun (a : T) => TermIn.const a }
Dependency graph
Equations
- instOfNatTermNat = { ofNat := TermIn.const a }
Dependency graph
Equations
- «term#_» = Lean.ParserDescr.node `«term#_» 1024 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol "#") (Lean.ParserDescr.cat `term 1024))
Instances For
Dependency graph
- EQ {T : Type} {n : ℕ} : Term T n → Term T n → BoolTerm T n
- NE {T : Type} {n : ℕ} : Term T n → Term T n → BoolTerm T n
- LE {T : Type} {n : ℕ} : Term T n → Term T n → BoolTerm T n
- LT {T : Type} {n : ℕ} : Term T n → Term T n → BoolTerm T n
- GE {T : Type} {n : ℕ} : Term T n → Term T n → BoolTerm T n
- GT {T : Type} {n : ℕ} : Term T n → Term T n → BoolTerm T n
- SYNEQ
{T : Type}
{n : ℕ}
: Term T n → Term T n → BoolTerm T n
IS NOT DISTINCT FROM: the two values are the same value, two nulls being the same value. This is what grouping, partitioning, duplicate elimination and difference key on, and it is never unknown. - SYNNE
{T : Type}
{n : ℕ}
: Term T n → Term T n → BoolTerm T n
IS DISTINCT FROM.
Instances For
Dependency graph
Equations
- (BoolTerm.EQ t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text "==" ++ TermIn.repr t₂ x✝) x✝
- (BoolTerm.NE t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text "!=" ++ TermIn.repr t₂ x✝) x✝
- (BoolTerm.LE t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text "<=" ++ TermIn.repr t₂ x✝) x✝
- (BoolTerm.LT t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text "<" ++ TermIn.repr t₂ x✝) x✝
- (BoolTerm.GE t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text ">=" ++ TermIn.repr t₂ x✝) x✝
- (BoolTerm.GT t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text ">" ++ TermIn.repr t₂ x✝) x✝
- (BoolTerm.SYNEQ t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text "≐" ++ TermIn.repr t₂ x✝) x✝
- (BoolTerm.SYNNE t₁ t₂).repr x✝ = Repr.addAppParen (TermIn.repr t₁ x✝ ++ Std.Format.text "≠̇" ++ TermIn.repr t₂ x✝) x✝
Instances For
Dependency graph
Equations
- instReprBoolTerm = { reprPrec := BoolTerm.repr }
Dependency graph
Equations
- (BoolTerm.EQ a b).castToAnnotatedTuple = BoolTerm.EQ (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
- (BoolTerm.NE a b).castToAnnotatedTuple = BoolTerm.NE (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
- (BoolTerm.LE a b).castToAnnotatedTuple = BoolTerm.LE (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
- (BoolTerm.LT a b).castToAnnotatedTuple = BoolTerm.LT (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
- (BoolTerm.GE a b).castToAnnotatedTuple = BoolTerm.GE (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
- (BoolTerm.GT a b).castToAnnotatedTuple = BoolTerm.GT (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
- (BoolTerm.SYNEQ a b).castToAnnotatedTuple = BoolTerm.SYNEQ (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
- (BoolTerm.SYNNE a b).castToAnnotatedTuple = BoolTerm.SYNNE (TermIn.castToAnnotatedTuple a) (TermIn.castToAnnotatedTuple b)
Instances For
Dependency graph
Equations
- «term_==__1» = Lean.ParserDescr.trailingNode `«term_==__1» 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " == ") (Lean.ParserDescr.cat `term 21))
Instances For
Dependency graph
Equations
- «term_!=__1» = Lean.ParserDescr.trailingNode `«term_!=__1» 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " != ") (Lean.ParserDescr.cat `term 21))
Instances For
Dependency graph
Equations
- «term_<=__1» = Lean.ParserDescr.trailingNode `«term_<=__1» 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " <= ") (Lean.ParserDescr.cat `term 21))
Instances For
Equations
- «term_<__1» = Lean.ParserDescr.trailingNode `«term_<__1» 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " < ") (Lean.ParserDescr.cat `term 21))
Instances For
Equations
- «term_>=__1» = Lean.ParserDescr.trailingNode `«term_>=__1» 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " >= ") (Lean.ParserDescr.cat `term 21))
Instances For
Equations
- «term_>__1» = Lean.ParserDescr.trailingNode `«term_>__1» 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " > ") (Lean.ParserDescr.cat `term 21))
Instances For
IS NOT DISTINCT FROM.
Equations
- «term_≐_» = Lean.ParserDescr.trailingNode `«term_≐_» 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ≐ ") (Lean.ParserDescr.cat `term 21))
Instances For
Dependency graph
The comparison a Boolean term makes.
Equations
- (BoolTerm.EQ a b).toCompOp = CompOp.eq
- (BoolTerm.NE a b).toCompOp = CompOp.ne
- (BoolTerm.LE a b).toCompOp = CompOp.le
- (BoolTerm.LT a b).toCompOp = CompOp.lt
- (BoolTerm.GE a b).toCompOp = CompOp.ge
- (BoolTerm.GT a b).toCompOp = CompOp.gt
- (BoolTerm.SYNEQ a b).toCompOp = CompOp.syneq
- (BoolTerm.SYNNE a b).toCompOp = CompOp.synne
Instances For
Dependency graph
The two terms a Boolean term compares.
Equations
Instances For
Dependency graph
Three-valued evaluation of a comparison: a comparison with a NULL
operand is neither true nor false.
Equations
- φ.eval3 tuple = φ.toCompOp.eval3 (TermIn.eval φ.args.1 tuple) (TermIn.eval φ.args.2 tuple)
Instances For
Dependency graph
The rows a comparison keeps: those on which it is true.
Equations
- φ.eval tuple = (φ.eval3 tuple = Kleene.true)
Instances For
Dependency graph
Equations
- φ.evalDecidable x✝ = BoolTerm.evalDecidable._aux_1 φ x✝
Instances For
Dependency graph
- BT {T : Type} {n : ℕ} : BoolTerm T n → Selection T n
- Not {T : Type} {n : ℕ} : Selection T n → Selection T n
- And {T : Type} {n : ℕ} : Selection T n → Selection T n → Selection T n
- Or {T : Type} {n : ℕ} : Selection T n → Selection T n → Selection T n
- True {T : Type} {n : ℕ} : Selection T n
Instances For
Dependency graph
Equations
- (Selection.BT t).repr x✝ = t.repr x✝
- f.Not.repr x✝ = Std.Format.text "¬" ++ Repr.addAppParen (f.repr x✝) x✝
- (t₁.And t₂).repr x✝ = Repr.addAppParen (t₁.repr x✝ ++ Std.Format.text "∧" ++ t₂.repr x✝) x✝
- (t₁.Or t₂).repr x✝ = Repr.addAppParen (t₁.repr x✝ ++ Std.Format.text "∨" ++ t₂.repr x✝) x✝
- Selection.True.repr x✝ = Std.Format.text "True"
Instances For
Dependency graph
Equations
- instReprSelection = { reprPrec := Selection.repr }
Dependency graph
Equations
- (Selection.BT t).castToAnnotatedTuple = Selection.BT t.castToAnnotatedTuple
- φ.Not.castToAnnotatedTuple = φ.castToAnnotatedTuple.Not
- (φ₁.And φ₂).castToAnnotatedTuple = φ₁.castToAnnotatedTuple.And φ₂.castToAnnotatedTuple
- (φ₁.Or φ₂).castToAnnotatedTuple = φ₁.castToAnnotatedTuple.Or φ₂.castToAnnotatedTuple
- Selection.True.castToAnnotatedTuple = Selection.True
Instances For
Dependency graph
Three-valued evaluation of a selection, in Kleene's logic: a row on which the predicate is unknown is selected by neither it nor its negation.
Equations
Instances For
Dependency graph
The rows a selection keeps: those on which it is true.
Equations
- φ.eval tuple = (φ.eval3 tuple = Kleene.true)
Instances For
Dependency graph
The rows a selection keeps, as a test. SQL keeps a row when the
condition is true, an unknown counting as a rejection, so the
three-valued reading becomes two-valued here. This is the form a
FILTER clause is read in, where a sequence has to be cut.
Instances For
Dependency graph
Equations
- φ.evalDecidable x✝ = Selection.evalDecidable._aux_1 φ x✝
Instances For
Dependency graph
A row is kept by NOT φ when φ is false, which is not the same as
φ failing to be true: a row on which φ is unknown is kept by neither.
Dependency graph
Where nothing is null no selection is ever unknown.
Dependency graph
Negation is classical where nothing is null.
Dependency graph
Equations
- instCoeBoolTermSelection = { coe := fun (bt : BoolTerm T n) => Selection.BT bt }
Dependency graph
Addition as a binary function, the fold of the ⊕-sum performed by
the rewriting-target operator Query.ProvSum (and by its general-syntax
counterpart AggQueryIn.ProvSum).
Instances For
Dependency graph
Dependency graph
Dependency graph
An aggregate function on sequences of values: an arbitrary function
from finite sequences over T to T. Beyond the monoid-shaped ⊕-sum
of Query.ProvSum, this interface covers non-commutative aggregates –
such as PICKFIRST, whose result depends on the order of its input – and
non-associative ones. It is the aggregate interface of the fused Having
operator, whose possible-world semantics does not need any algebraic
structure on the aggregate.
Equations
- SeqAggFunc T = (List T → T)
Instances For
Dependency graph
An aggregate is a total function on sequences, so each one has to say
what it does with the empty sequence. Where a row exists only because its
group does, that value is never read and the choice is immaterial. Where the
row exists on its own – an aggregation over no grouping, a frame that may
exclude the row it is computed for – it is read, by the scalar convention of
AggValue.predProvScalar.
Each aggregate of SQL also comes with an input policy, which says what it
reads of a sequence in which some values are null. There are three.
Null-skipping (SUM, MIN, MAX, AVG …) drops the nulls and answers
NULL over what is left of nothing: that is sqlOf. Counting (COUNT)
reads every occurrence, which counts when its value is not null, and
answers 0 over nothing: that is counting. Null-keeping (ARRAY_AGG,
…) reads every value, nulls included: that is the aggregate itself.
The aggregates below are those of a domain with no null, and they give the
zero of the value type over no row. COUNT is right that way: SQL counts no
row as 0. SUM, MIN and MAX are not, since SQL gives NULL there, and
sqlOf is what makes them so on a domain that has a null – it skips the
nulls, as SQL does, and gives NULL when nothing is left. COUNT(*) stays
unwrapped, being the one aggregate SQL does not read that way.
SUM as a sequence aggregate; 0 on the empty sequence, where SQL has
null.
Equations
- SeqAggFunc.sum L = List.foldr (fun (x1 x2 : T) => x1 + x2) 0 L
Instances For
Dependency graph
COUNT(*) as a sequence aggregate (over an ℕ-valued domain); 0 on
the empty sequence, as SQL has.
Equations
Instances For
Dependency graph
MIN, with the zero of the value type as its default on the empty
sequence, where SQL has null.
Equations
- SeqAggFunc.min [] = 0
- SeqAggFunc.min (x :: xs) = List.foldr min x xs
Instances For
Dependency graph
MAX, with the zero of the value type as its default on the empty
sequence, where SQL has null.
Equations
- SeqAggFunc.max [] = 0
- SeqAggFunc.max (x :: xs) = List.foldr max x xs
Instances For
Dependency graph
PICKFIRST: the first value of the sequence, with the zero of the value
type as its default on the empty one, where SQL has null.
Equations
- SeqAggFunc.pickFirst L = L.headD 0
Instances For
Dependency graph
The value at offset i of the sequence, counting from 0, with the
zero of the value type where the sequence is shorter, and PICKFIRST at
offset 0. It is the aggregate SQL's nth_value, lag(t, k) and
lead(t, k) read a frame through, which PICKFIRST alone cannot give:
it reads one end of the frame and no other position.
Equations
- SeqAggFunc.pickNth i L = L.getD i 0
Instances For
Dependency graph
SQL's reading of an aggregate on a domain with a null: skip the
nulls, and give NULL when nothing is left. SUM, MIN and MAX are read
this way. COUNT is not: it gives 0 over no row, which is what the
unwrapped aggregate already does.
Equations
- f.sqlOf L = if (List.filter (fun (a : V) => decide (a ≠ ValueTypeNull.null)) L).isEmpty = true then ValueTypeNull.null else f (List.filter (fun (a : V) => decide (a ≠ ValueTypeNull.null)) L)
Instances For
Dependency graph
SQL's counting input policy: every occurrence is read, and counts
when its value is not null. This is COUNT(t).
It is not sqlOf. The two agree on dropping the nulls and part company on
what is left of nothing, where a null-skipping aggregate answers NULL and
a count answers 0. COUNT(*) needs neither, being COUNT over a term
that is never null, so that every occurrence counts and the plain count of
the sequence is already right.
Equations
- f.counting L = f (List.filter (fun (a : V) => !ValueType.isNull a) L)
Instances For
Dependency graph
What it takes for an aggregate to count matches: it is never null, and
it is zero exactly when it has no non-null value to count. SQL's count(e)
is such an aggregate.
A count is a value, never a null.
A count is zero exactly over nothing but nulls.
Instances For
Dependency graph
Which aggregates read their input as a multiset #
The interface is a function on sequences, so an aggregate may depend on
the order of its input, and PICKFIRST does. The ones that do not are the
ones a grouping or a window can compute without settling how its rows are
sequenced: for them the canonical order the library sorts by is as good as
the order an ORDER BY asks for, and for the others it is not.
An aggregate is symmetric when it reads its input as a multiset: permuting the sequence does not change the answer.
Instances For
Dependency graph
A symmetric aggregate as a function of a bag. It does not read the
order of its sequence, so it is a function of the bag of values. This is
what a nested aggregate value needs: the order ≼ is an order on plain
tuples, and an occurrence of a nested value carries a tuple with an
aggregate column, so there is no sequence for an order-dependent
aggregate to read and the bag is the input.
Equations
- f.onBag hf s = Quot.liftOn s f ⋯
Instances For
Dependency graph
Dependency graph
f^distinct: the aggregate read over the distinct values of its
sequence. Over plain relations this is SQL's DISTINCT aggregate, an
aggregate value being an ordinary value there. Over annotated relations a
grouped DISTINCT aggregate is not this transformer but the abbreviation
AggQueryIn.gammaDistinct, which deduplicates the rows first, so that each
distinct value is one occurrence annotated by the ⊕ of the occurrences it
stands for.
Instances For
Dependency graph
MIN and MAX return one of their inputs #
- Rel {T : Type} (n : ℕ) : String → Query T n
- Proj {T : Type} {n m : ℕ} : Tuple (Term T n) m → Query T n → Query T m
- Sel {T : Type} {n : ℕ} : Selection T n → Query T n → Query T n
- Prod {T : Type} {n₁ n₂ n : ℕ} {hn : n₁ + n₂ = n} : Query T n₁ → Query T n₂ → Query T n
- Sum {T : Type} {n : ℕ} : Query T n → Query T n → Query T n
- Dedup {T : Type} {n : ℕ} : Query T n → Query T n
- Diff {T : Type} {n : ℕ} : Query T n → Query T n → Query T n
- ProvSum
{T : Type}
{m n₁ : ℕ}
: Tuple (Fin m) n₁ → Term T m → Query T m → Query T (n₁ + 1)
Provenance aggregation: group by the key columns of the first argument and
⊕-sum the term of the second over each group into a single trailing output column. It is not a source operator – aggregation as such lives on the general syntax (AggQueryIn.Gamma) – but the target of the (R1)–(R4) rewriting: the ⊕-gate creation of theεand∖rules ofQuery.rewriting. Its general-syntax counterpart isAggQueryIn.ProvSum. - Having
{T : Type}
{m n₁ n₂ : ℕ}
: Tuple (Fin m) n₁ →
Tuple (Term T m) n₂ → Tuple (SeqAggFunc T) n₂ → CompOp → Fin n₂ → Term T n₁ → Query T m → Query T (n₁ + n₂)
The fused
HAVINGoperator: grouping by the indices of the first argument, computing the sequence aggregates of the third argument applied to the terms of the second (each group read in the canonical tuple order, which plays the role of the ordering≼of non-commutative aggregates), and keeping only the groups whose aggregate value in columnl(theFin n₂argument) compares, via the comparison operator, with the value of the regular term (theTerm T n₁argument, evaluated on the group key – this covers both query constants and group-key attributes). The output has the group key followed by the aggregate values.
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
- (Query.Rel n s).repr x✝ = Std.Format.text s
- (Π ts q).repr x✝ = Std.Format.text "Π_" ++ Repr.addAppParen (ts.repr x✝) x✝ ++ Repr.addAppParen (q.repr x✝) x✝
- (σ φ q).repr x✝ = Std.Format.text "σ_" ++ Repr.addAppParen (φ.repr x✝) x✝ ++ Repr.addAppParen (q.repr x✝) x✝
- (q₁.Prod q₂).repr x✝ = Repr.addAppParen (q₁.repr x✝ ++ Std.Format.text "×" ++ q₂.repr x✝) x✝
- (q₁ ⊎ q₂).repr x✝ = Repr.addAppParen (q₁.repr x✝ ++ Std.Format.text "⊎" ++ q₂.repr x✝) x✝
- (ε q).repr x✝ = Std.Format.text "ε" ++ Repr.addAppParen (q.repr x✝) x✝
- (q₁ - q₂).repr x✝ = Repr.addAppParen (q₁.repr x✝ ++ Std.Format.text "-" ++ q₂.repr x✝) x✝
- (Query.ProvSum is t q).repr x✝ = Std.Format.text "γ⊕_" ++ Repr.addAppParen (is.repr x✝) x✝ ++ Repr.addAppParen (TermIn.repr t x✝) x✝ ++ Repr.addAppParen (q.repr x✝) x✝
Instances For
Dependency graph
Equations
- instReprQuery = { reprPrec := Query.repr }
Dependency graph
The source fragment of the classical syntax: the operators a
query is written with, RA⁺(∖). It excludes the two operators that are
not source operators – ProvSum, which the (R1)–(R4) rewriting emits,
and the fused Having, whose semantics lives on the general syntax – and
is exactly the fragment carrying an annotated semantics
(Query.evaluateAnnotated) and accepted by Query.rewriting. Its
general-syntax counterpart is AggQueryIn.classical.
Equations
- (Query.Rel n s).source = True
- (Π a q_2).source = q_2.source
- (σ a q_2).source = q_2.source
- (q₁.Prod q₂).source = (q₁.source ∧ q₂.source)
- (q₁ ⊎ q₂).source = (q₁.source ∧ q₂.source)
- (ε q_2).source = q_2.source
- (q₁ - q₂).source = (q₁.source ∧ q₂.source)
- (Query.ProvSum a a_1 q_2).source = False
- (Query.Having a a_1 a_2 a_3 a_4 a_5 a_6).source = False
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
- (Query.Rel n s).sourceDecidable = isTrue ⋯
- (Π a q_2).sourceDecidable = match q_2.sourceDecidable with | { decide := true, reflects_decide := h } => isTrue ⋯ | { decide := false, reflects_decide := h } => isFalse ⋯
- (σ a q_2).sourceDecidable = match q_2.sourceDecidable with | { decide := true, reflects_decide := h } => isTrue ⋯ | { decide := false, reflects_decide := h } => isFalse ⋯
- (ε q_2).sourceDecidable = match q_2.sourceDecidable with | { decide := true, reflects_decide := h } => isTrue ⋯ | { decide := false, reflects_decide := h } => isFalse ⋯
- (Query.ProvSum a a_1 q_2).sourceDecidable = isFalse ⋯
- (Query.Having a a_1 a_2 a_3 a_4 a_5 a_6).sourceDecidable = isFalse ⋯
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Equations
- «termΠ_» = Lean.ParserDescr.node `«termΠ_» 1024 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol "Π ") (Lean.ParserDescr.cat `term 1024))
Instances For
Dependency graph
Equations
- termσ_ = Lean.ParserDescr.node `termσ_ 1024 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol "σ ") (Lean.ParserDescr.cat `term 1024))
Instances For
Dependency graph
Equations
- «term_×__2» = Lean.ParserDescr.trailingNode `«term_×__2» 80 81 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " × ") (Lean.ParserDescr.cat `term 81))
Instances For
Dependency graph
Equations
- «term_⊎_» = Lean.ParserDescr.trailingNode `«term_⊎_» 50 51 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⊎ ") (Lean.ParserDescr.cat `term 51))
Instances For
Dependency graph
Equations
- termε_ = Lean.ParserDescr.node `termε_ 1024 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol "ε ") (Lean.ParserDescr.cat `term 1024))
Instances For
Dependency graph
Equations
- «term_-__1» = Lean.ParserDescr.trailingNode `«term_-__1» 50 51 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " - ") (Lean.ParserDescr.cat `term 51))
Instances For
Dependency graph
Equations
- «term_⋈_» = Lean.ParserDescr.trailingNode `«term_⋈_» 1020 1021 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⋈ ") (Lean.ParserDescr.cat `term 1021))
Instances For
Dependency graph
Equations
- «term_∪__1» = Lean.ParserDescr.trailingNode `«term_∪__1» 50 51 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ∪ ") (Lean.ParserDescr.cat `term 51))
Instances For
Dependency graph
Dependency graph
Equations
- (Query.Rel n s).aggdepth2_plus_depth = 0
- (Π a q_2).aggdepth2_plus_depth = q_2.aggdepth2_plus_depth + 1
- (σ a q_2).aggdepth2_plus_depth = q_2.aggdepth2_plus_depth + 1
- (q₁.Prod q₂).aggdepth2_plus_depth = max q₁.aggdepth2_plus_depth q₂.aggdepth2_plus_depth + 1
- (q₁ ⊎ q₂).aggdepth2_plus_depth = max q₁.aggdepth2_plus_depth q₂.aggdepth2_plus_depth + 1
- (ε q_2).aggdepth2_plus_depth = q_2.aggdepth2_plus_depth + 1
- (q₁ - q₂).aggdepth2_plus_depth = max q₁.aggdepth2_plus_depth q₂.aggdepth2_plus_depth + 1
- (Query.ProvSum a a_1 q_2).aggdepth2_plus_depth = q_2.aggdepth2_plus_depth + 3
- (Query.Having a a_1 a_2 a_3 a_4 a_5 a_6).aggdepth2_plus_depth = a_6.aggdepth2_plus_depth + 3
Instances For
Dependency graph
The occurrences of the group of key g in relation r: the multiset of
matching tuples, as a list sorted by the canonical linear order on tuples.
The sort order plays the role of the ordering ≼ along which
non-commutative sequence aggregates read the occurrences of a group; for
commutative aggregates it is irrelevant.
Equations
- Relation.groupSeq is r g = sortList (Multiset.filter (fun (u : Tuple T m) => ∀ (k' : Fin n₁), u (is k') = g k') r)
Instances For
Dependency graph
The occurrence sequence an aggregate of a grouping reads: the
group's rows, cut by a FILTER clause where the aggregate carries one.
Both the plain evaluator and the rewritten world's evaluator read a group
through this, so the two agree clause for clause.
Equations
- Relation.groupSeqOpt is r g none = Relation.groupSeq is r g
- Relation.groupSeqOpt is r g (some φ) = List.filter φ.keeps (Relation.groupSeq is r g)
Instances For
Dependency graph
Standard multiset semantics of a query over a plain database.
The Diff case is all-or-nothing difference: every copy of a tuple that
occurs at all in r₂ is removed from r₁ (deliberately not Multiset.sub,
which would subtract multiplicities as in SQL's EXCEPT ALL). This matches
the monus-based annotated semantics of difference
(Query.evaluateAnnotated) exactly on 0/1-annotated inputs; on general
annotations the two disagree over ℕ (see Nat.counterexample_diff_adequacy
and Provenance.QueryAdequacy).
Equations
- One or more equations did not get rendered due to their size.
- (Query.Rel n s).evaluate d = match Database.find n s d with | none => ∅ | some rn => rn
- (Π a q_2).evaluate d = Multiset.map (fun (t : Tuple T n_3) (k : Fin n) => TermIn.eval (a k) t) (q_2.evaluate d)
- (σ a q_2).evaluate d = Multiset.filter a.eval (q_2.evaluate d)
- (q₁.Prod q₂).evaluate d = Relation.cast hn (q₁.evaluate d * q₂.evaluate d)
- (q₁ ⊎ q₂).evaluate d = q₁.evaluate d + q₂.evaluate d
- (ε q_2).evaluate d = Multiset.dedup (q_2.evaluate d)
- (q₁ - q₂).evaluate d = Multiset.filter (fun (t : Tuple T n) => t ∉ q₂.evaluate d) (q₁.evaluate d)