The fragment semantics under homomorphisms, over đš and over â #
Three readings of the closed-form annotated semantics
FragQueryIn.sem, each an induction over the syntax, and together what
the extensionality theorem of Provenance.Extensionality needs.
- Homomorphisms. A semiring homomorphism
h : K â+* K'commutes with the semantics (FragQueryIn.sem_mapAnn), provided it preserves the monus where the query uses one â a difference or an antijoin (FragQueryIn.hasMonus). Nothing is asked aboutδ, which the fragment never reads: this is what lets a point of a lattice m-semiring, which is a semiring homomorphism ontođšand nothing more, be pushed through a query ofFâ. - Over
đš. A tuple is in the support of the annotated result exactly when it is in the plain result of the support of the instance (FragQueryIn.mem_support_sem), for every query of the fragment. - Over
â. Reading anâ-annotation as a multiplicity (AnnotatedRelation.unfold), the plain semantics of the unfolded instance is the unfolded annotated semantics, onFâ(FragQueryIn.semPlain_unfold): the adequacy inâof the positive fragment, with multiplicities in place ofđ.
Pushing a function through the annotations #
The annotations of a relation, read through a function.
Equations
- AnnotatedRelation.mapAnn f r = Multiset.map (fun (p : AnnotatedTuple T K n) => (p.1, f p.2)) r
Instances For
Dependency graph
The annotations of a database, read through a function.
Equations
- AnnotatedDatabase.mapAnn f d = List.map (fun (e : String Ă (n : â) Ă AnnotatedRelation T K n) => (e.1, â¨e.2.fst, AnnotatedRelation.mapAnn f e.2.sndâŠ)) d
Instances For
Dependency graph
find commutes with reading the annotations through a function.
Dependency graph
The tuples of a relation are untouched.
Dependency graph
The â-sum of the annotations of a tuple, through a semiring
homomorphism.
Dependency graph
The â-sum of all the annotations, through a semiring
homomorphism.
Dependency graph
A filter on the tuples passes under the pushforward.
Dependency graph
Whether a query uses the monus: a difference or an antijoin somewhere.
Equations
- (FragQueryIn.Rel xâ a).hasMonus = False
- FragQueryIn.Empty.hasMonus = False
- FragQueryIn.Unit.hasMonus = False
- (FragQueryIn.Proj ts q).hasMonus = q.hasMonus
- (FragQueryIn.Sel Ď q).hasMonus = q.hasMonus
- (qâ.Prod qâ).hasMonus = (qâ.hasMonus ⨠qâ.hasMonus)
- (qâ.Apply qâ).hasMonus = (qâ.hasMonus ⨠qâ.hasMonus)
- (qâ.Sum qâ).hasMonus = (qâ.hasMonus ⨠qâ.hasMonus)
- q.Dedup.hasMonus = q.hasMonus
- (a.Diff a_1).hasMonus = True
- (FragQueryIn.Semijoin cnt a Ď qâ qâ).hasMonus = (qâ.hasMonus ⨠qâ.hasMonus)
- (FragQueryIn.Antijoin cnt a Ď a_1 a_2).hasMonus = True
Instances For
Dependency graph
A query of Fâ uses no monus.
Dependency graph
Homomorphisms #
The semantics commutes with a semiring homomorphism that preserves the monus where the query uses one.
Dependency graph
Over đš: the support #
find commutes with taking the support.
Dependency graph
Membership in the support: some copy of the tuple is annotated true.
Dependency graph
Over đš, the â-sum of the annotations of a tuple is true exactly
when the tuple is in the support.
Dependency graph
Over đš, the â-sum of all the annotations is true exactly when the
support is non-empty.
Dependency graph
Support adequacy over đš, for the whole fragment: a tuple is in
the support of the annotated result exactly when it is in the plain
result of the support of the instance.
Dependency graph
Over â: annotations as multiplicities #
An â-annotated relation, unfolded: each copy of a tuple is
repeated as many times as its annotation says.
Equations
- r.unfold = Multiset.bind r fun (p : AnnotatedTuple T â n) => Multiset.replicate p.2 p.1
Instances For
Dependency graph
An â-annotated database, unfolded relation by relation.
Equations
Instances For
Dependency graph
find commutes with unfolding.
Dependency graph
The multiplicity of a tuple in the unfolding is the â-sum of its
annotations.
Dependency graph
Adequacy in â with multiplicities, on Fâ: the plain semantics
of the unfolded instance is the unfolded annotated semantics. A product
multiplies multiplicities, a union adds them, and the other operators of
Fâ carry them along.