D Wiki - New pages [en-gb]

PhilipTutorial

2017-09-24T14:29:59Z

Dandl: Initial creation from TTM post

This is a verbatim copy of text posted by Philip to the TTM mailing list, lightly edited for continuity and formatting.

Hopefully Philip will improve it, but (of course) he may just delete it. Over to Philip.

== PREAMBLE ==

Below is an edited message that quoted others with some RM semantics, my 'tutorial' & my 'quiz'.

I have sent many messages about RM query meanings. The recent intro/tutorial/quiz that this is from is not intended
to be an ideal presentation.
If one bumped up against not understanding something in reading an example or not knowing something in answering the quiz,
presumably one would ask a question or point out a contradiction.

== INTRODUCTION ==

Each relvar name has a dba-given predicate and each operator has a Codd-given transformation on predicates.
Each query subexpression (relation or wff) has a predicate built from its mentioned relvar names and operators.
This is in fact how we actually know what queries mean.

Every relvar has a predicate (parameterized statement about the
world), with attributes the free variables. Every relation operator
has a corresponding predicate transform, eg JOIN/AND. So every
relation expression has a corresponding predicate, and vice versa. The
design of the relation operators is such that IF the relvars' values are their predicates'
extensions THEN an expression's value is its predicate's extension.
The value of a relvar after an assignment is the value of the query
evaluated before the assignment. Which means the extension of the
relvar predicate in the new state is the extension of the expression predicate in the old state.
When I say that is all you need to know, THAT IS ALL YOU NEED TO KNOW.

The predicate of a relation expression that is a name of a relation
variable or constant is its predicate. The predicate of a relation
expression that is a JOIN is the AND of the predicates its operands;
of a UNION is the OR; of a MINUS is the AND NOT; of a RESTRICT X=Y or
of an ADD X AS Y is the AND X=Y; and of a PROJECTALLBUT X is the
EXISTS X.

RE: delete-through-restrict - logical basis

query wff predicate:
n n(x,y) 'x likes y'
m m(z) 'i like z'
n where y=3 n(x,y) and y=3 'x likes y and y=3'
(n where y=3){allbut y} exists y [n(x,y) and y=3] 'x likes 3'
(n where y=3){allbut y} n(x, 3) 'x likes 3'
m rename z to x m(x) 'i like x'
(n where y=3) join (m rename z to x) n(x, y) and y=3 and m(x)
'x likes y and y=3 and i like x' ie 'x likes 3 and y=3 and i like x'
(n where y=3){allbut y} join (m rename z to x) n(x, 3) and m(x)
'x likes 3 and i like x'

----------------------------------------------------------------------------

The value of every subexpression is the extension of its predicate.
I append (a) an excerpt tracing and justifying an illustrating example and (b) a self-quiz excerpt.

== TUTORIAL ==

Here is how a relational database works.

type T={a, b}
relvar r RELATION{X T} "i like X"
Relvar predicate for relvar r is "i like X".
r:=RELATION{TUPLE{X a}} // i like a and i don't like b.
Relvar r value, relvar r (and database) proposition is "i like a and i don't like b".
r:=RELATION{TUPLE{X a},TUPLE{X b}} // now i like a and i like b.
Relvar r value, relvar r (and database) proposition is "i like a and i like b".

hmm... if i assume that a relvar holds those tuples that make its predicate true
(in which case, for each present tuple, that tuple put into the
predicate is true, and in which case, for each absent tuple, that
tuple put into the predicate is false) then a certain conjunction mapped from its tuples is true.

Namely:
(AND for t in r of the predicate of r applied to t)
AND (AND for t not in r of NOT(the predicate of r applied to t))
or if you prefer:
(FORALL t in r : the predicate of r applied to t)
AND (FORALL t not in r : NOT (the predicate of r applied to t))

So if i assume that a relvar value is the extension of its predicate then it seems to state what i expect!

Namely that if a tuple is in a relvar then it asserts the relvar
predicate applied to it and that if a tuple is not in a relvar then it
asserts the negation of the relvar predicate applied to it.
(Informally, present tuples are true and absent tuples are false.)

print r // RELATION{TUPLE{X a},TUPLE{X b}}

hmm... this is the extension of the predicate of r.

hmm... a query expression that is a relvar name seems to be the
extension of a predicate that is the relvar's predicate.

print RELATION{TUPLE{X b}} // RELATION{TUPLE{X b}}

hmm... this is the extension of X=b.

hmm... a relation expression RELATION{TUPLE{A1 v1, ...}, ...} seems
to be the extension of a predicate (A1=v1 AND ...) OR ....

Or if it's clearer: (A1=v11 AND A2=v12 AND...) OR (A1=v21 AND A2=v22
AND...) OR .... Ie the disjunction of the conjunction of the equalites
of attributes names and values.

print r PROJECT ALL BUT X // RELATION{TUPLE{}}

hmm... relation expression e PROJECT ALL BUT A seems to be the
extension of (EXISTS A: the predicate of e).

print r UNION RELATION{TUPLE{X b}} // RELATION{TUPLE{X a},TUPLE{X b}}

hmm... relation expression e UNION f seems to be the extension of
(the predicate of e OR the predicate of f).

print (r UNION RELATION{TUPLE{X b}}) MINUS RELATION{TUPLE{X a}} // RELATION{TUPLE{X b}}

hmm... relation expression (e UNION f) MINUS g
seems to be the extension of ((the predicate of e OR the predicate of
f) AND NOT the predicate of g)

hmm... relation expression e MINUS f
seems to be the extension of (the predicate of e AND NOT the
predicate of f).

hmm... every relation seems to be the extension of a certain
transformation of its arguments' predicates.

hmm... seems that a query expression that is a relvar name has as
value the extension of the relvar predicate and that a query
expression that is a literal has as value the extension of the
disjunction-conjunction-equality from its tuples and that a query
expression that is an operator call has as value the extension of a
certain transformation of its arguments' predicates, and that
(consequently) an arbitrary query expression has as value the
extension of a thus-built predicate.

So if i assume that a query expression predicate is thus-built then
the query is the extension of its predicate!
And so the query tuples are the ones that make a certain predicate true!

Namely the thus-built query expression predicate.
And so a certain conjunction mapped from its tuples is true!

Namely the same proposition as expressed twice above, but for the
query instead of the relvar:
(AND for t in value of query of the predicate of query applied to t)
AND (AND for t not in value of query of NOT(the predicate of query applied to t))
or if you prefer:
(FORALL t in value of query : the predicate of query applied to t)
AND (FORALL t not in value of query : NOT (the predicate of query applied to t))

So if i assume that a query value is the extension of its predicate
then it seems to state what i expect

Namely that if a tuple is in a query then it asserts the query
predicate applied to it and that if a tuple is not in a query then it
asserts the negation of the query predicate applied to it.
(Informally, present tuples are true and absent tuples are false.)
(Note that if missing tuples are not false, then you can't use
MINUS/NOTMATCHING.)

b. QUIZ

* What are the names of your relation variables and constants?
* What is the characteristic predicate (parameterized statement about the world) for each?
* What is the formal wff for each? Why?
* What are the attributes for each? Why?
* What is your (example) query relation expression?
* What is the characteristic predicate of its result? Why?
* What are the (example) values of your relation variables?
* What statement does each make about the world? Why?
* What statement does the database make about the world? Why?
* What is the value of your query relation expression? Why?
* What statement does this value make about the world in the context of this query relation expression? Why?
* What statement does a query result make about the world regardless of its query relation expression? Why?

The most important things to understand are that:

# each relation expression corresponds to a certain wff and
# equivalent relation expressions correspond to equivalent wffs

The relational algebra is just another syntax for FOPL.

Update through views: a not-quite-so seminal paper - asking too much, and orthogonal base relations

2017-02-12T08:51:27Z

AntC: /* References */

Another much-cited paper on updating through views, of the same vintage as Dayal & Bernstein or Codd's 12 rules, is Bancilhon & Spyratos 1981, which introduced the "constant complement" approach (and which anticipates Date's Principle of Interchangeability).

B&S aim to give a more precise specification for D&B's ''unique'', avoiding ''extraneous updates''. They don't offer an opinion on how few views are updatable-through, compared to D&B's "very few situations" conclusion. But it isn't difficult to see their restrictions are more stringent.

I think their approach rests on an unstated assumption that is unrealistic. I'm going to draw out my reasons, to discuss the implications for independent update of relations (base or views). First I'll outline their approach.

== What is a "View complement"? ==

Given base relations and a view defined over them, the ''view complement'' is "The information [in the bases] not visible within the view", as B&S put it.

* Take view ''V'' defined over base relations ''B1, B2, ..., Bn''.
: (If ''V'' is defined over relvars that are themselves views, substitute in the view definitions (recursively) until there are all bases.)
* Interchange the schema for an information equivalent one in which:
** There is a base ''BV'' with same heading as ''V''.
** There are views ''VB1, VB2, ..., VBn'' with the same headings as the based-ons respectively, and to be defined over ''BV'' and ....
** There are bases ''BBm, BBm+1, ..., BBm+o'' (not necessarily corresponding to ''B1, B2, ...'').
** View ''V' '' is defined over ''VB1, VB2, ...VBn'' exactly as was ''V'' over the original bases.
* The content for these alternative relvars (i.e. their internal predicate) is to be:
** Base ''BV'' is to have the same content as would view ''V''.
** View ''VB1, VB2, ..., VBn'' are to have the same content as would ''B1, B2, ..., Bn'' respectively.
** Bases ''BBm, BBm+1, ..., BBm+o'' are to have 'just enough' content to combine with the content of ''BV'' and supply the content for views ''VB1, VB2, ..., VBn''.
** So ''V' '' always yields the same content as ''BV''.

The idea is that ''BBm, BBm+1, ..., BBm+o'' represent the original base relations ''B1, B2, ..., Bn'' minus the view ''V'' -- i.e. the ''complement'' of the view. For example:
* If ''V'' is a restriction over a single base, its complement could be a base with the same heading, containing the tuples excluded from the view (i.e. disjoint internal predicate).
* If ''V'' is a projection over a single base, its complement could be a base with the projected-out attributes, plus a key to join back.
: To be information equivalent/a lossless decomposition would need declaring an EQD between the two projections.
* If ''V'' is a join, its complement could be two bases with the headings of the original bases, containing respectively the tuples not MATCHING.

In general there will be many ways to choose the schema and internal predicates for ''BBm, BBm+1, ..., BBm+o''. The schema designer has a free hand to decompose or combine the original bases.

=== Constant complement ===

The ideal choice of complement is one in which the view-as-base ''BV'' can be freely updated without requiring update to any other bases; and from which update bases-as-views ''VB1, VB2, ..., VBn'' are correctly generated, such that ''V' '' yields the same as ''BV''.

* With the restriction view, since its complement has a disjunctive internal predicate, tuples can be freely updated into the view-as-base. (An attempt to modify an existing tuple to values that would exclude it from the restriction is disallowed, because that would violate the view-as-base's internal predicate.)

* With the projection view-as-base, it is possible to modify the non-key attributes; but not insert (because tuples would need to be inserted to the complement, to be able to join); and (arguably) not delete, because the 'information equivalence' requirement imposes an EQD on the keys.

* With the join view-as-base, opportunities for update are even more limited. (Only modify the non-common attributes; not INSERT because that might need 'moving' a tuple from the complement to the join-as-base; not DELETE because that might need 'moving' a tuple to the complement.)

It is notable that the example initial base schema B&S work with (two base relations each of two attributes) has an unusually large number of integrity constraints, including bi-directional Functional Dependencies, and an EQD such that the two relations are a lossless decomposition.

B&S tighten the screw further [Secion 3]:
<blockquote> User requirements impose two constraints on this set [of ''translatable'' updates], namely,
(i) If the user is allowed two updates ''u'' and ''v'', then he must be allowed the composite update ''uv''. 
(ii) The user must have the means to cancel, if he wishes, the effect of every update that he is allowed to the view.
</blockquote>

Re (i) they don't appear to consider that applying ''u'' might make ''v'' invalid (or ''v.v.'').
Re (ii), it is not clear which User(s) stated this requirement, or why.

== The invalid assumption: that base relvars are independently updatable ==

Behind the hold-the-complement-constant approach is an assumption that if a view can be updated independently, as if it was a base, it is first-class. On the grounds updates to each base are independent (and are therefore first-class), because they hold all other bases constant.

"The problem of finding independent views is extremely important in database theory." pronounce B&S [section 6], with no citation (beyond their own technical work).

To put it plainly: updates to base are not necessarily independent. And B&S need look no further than their own initial schema. Updates are not independent because of inter-relational constraints. B&S's should look at how 'tight' are the constraints in their schema (two base relations), and consider that neither base relation could form a constant complement of the other.

Independence of update of base relations is indeed an important criterion for schema design: Normalisation is to remove redundancy/avoid update anomalies. Note, though, that if a normalised schema is to be information-equivalent to its un-normalised predecessor, each decomposition must add inter-relational constraints to ensure lossless re-composition.

Inter-relational constraints are the norm with mature schema designs. Therefore an ideal of independent update is unachievable for base relations. It is an entirely pointless criterion for update through views.

== Orthogonal Design and updating base relations ==

'Orthogonal Design' (Principle Of, introduced as part of Date & McGoveran's 1994 treatment of updating through views) of a schema is claimed to be essential to translating updates through a view to updates to base. Definitions vary for what POOD means precisely,

<blockquote>"Loosely, the principle that no two relvars in a given database should have overlapping meanings." says Date in his Relational DB Dictionary (2008 Extended Edition). And Date goes on to give a precise extensional definition.

" The semantic orthogonality property holds in a database design (a particular schema) if and only if, ignoring multi-relation constraints, there is no "overlap" or redundancy between the intended membership of any two relations in the schema. If this is true, then we can add (or remove) tuples to (from) one without that operation in and of itself implying tuples need to be added (or removed) to the other for database consistency, except as required by some multi-relation constraint (e.g., a foreign key). This notion is analogous to having orthogonal axes in a coordinate system: The variables such axes represent are independent – we can alter the value on one such variable without altering any of the others. " says McGoveran in his draft Chapter on Updating Relations (2015).
</blockquote>

As we have seen, normalising a design (so that "we can add (or remove) tuples to (from) [a relation] without that operation in and of itself implying [other] tuples need to be added (or removed) to " that same relation "for database consistency") entails defining multi-relation constraints to preserve information equivalence. So allowing an exception for inter-relational (multi-relation) constraints makes POOD a dead letter.

Behind B&S's advocacy for constant complement is the presumption that base relations are first-class because "we can alter the value on one such [relation] without altering any of the others". This in fact does not apply for base relations (because of muti-relation constraints). Neither is it reasonable to expect it to apply for update through views, ''a fortiori'' because their content is redundant necessarily.

To compare updates to a base relvar subject to a multi-relation constraint with update through a view:

* Consider an INSERT to a base relation that is the dependent in an INclusion Dependency.
: That INSERT might fail because there is no matching tuple in the defining base relation.
: Violation of the IND can only be detected at run time.
: Does this mean the base relation is not updatable-to?

* Then consider an INSERT through a view defined using MATCHING.
: If that's translated to an INSERT to the MATCHING's left operand, it might fail because there is no matching tuple in the right operand.
:: (That is, fail because the inserted tuple would therefore not appear in the resulting value for the view -- violating ''no side effects''/The Assignment Principle.)
: So (arguably) violation of The Assignment Principle can only be detected at run time.
: Does this mean the MATCHING view is not updatable-through?

[in progress]

== References ==

* Bancilhon and Spyratos 1981 "Update Semantics of Relational Views"
: http://pages.cs.wisc.edu/~jhuang/qual/update-semantics-of-views.pdf

* David McGoveran Chapter draft March 2015 "Can All Relations Be Updated? "/"Updating Relations"
: http://www.alternativetech.com/publications/Logic%20for%20DB%20Folks%20Series%20XX%20-%20Updating%20Relations.pdf

* Chris Date 2008 "The Relational Database Dictionary, Extended Edition"
: http://www.apress.com/book/view/1430210419

See also [[Update through views: a possible approach#References]]

Update through views: a seminal paper - appreciation, commentary, critique

2017-02-09T05:25:22Z

AntC: /* no side effects */

My gold standard for expressing principles to do with updating-through-views is Dayal & Bernstein 1978 "On the Updatability of Relational Views", section "Correctness Criteria for View Updates". That's not to say I entirely agree with them, but I'm impressed that they have expressed their approach in one sentence of ~50 words, plus 4 paragraphs to explain each key term. The surprise is how soon this was published after Codd's papers elaborating the RM.

Contrast that [http://computing.derby.ac.uk/c/codds-twelve-rules/ Codd's 12 Rules], including the prescription for update-through-view, and definition for "theoretically updatable" was published in 1985. Codd says "Although I have defined each rule in earlier papers, I believe this to be the first occurrence of all twelve of them together.", and cites a paper "conceived in 1981".

Another influential paper of the same vintage, Bancilhon & Spyratos 1981, introduced the "constant complement" approach (which anticipates Date's Principle of Interchangeability).

== Correctness Criteria for View Updates ==

The model sentence:
<blockquote>
Given a semantically consistent schema extension '''$*''', we say that an update operation '''u''' on view extension '''V*''' is ''translatable'' if there is a ''unique'' set of updates '''U''' on '''$*''' producing the desired update on '''V*''', such that there are ''no extraneous updates'' in '''U''', ''no side effects'' on '''V*''', and '''U''' ''preserves semantic consistency''.
</blockquote>
Explanations:
<blockquote>
An update is ''extraneous'' in '''U''' if '''U''' produces the same effect on the view extension with or without the extraneous update.
</blockquote>
<blockquote>
The set of updates '''U''' has ''no side effects'' if ''only'' the desired update is performed on the view.
</blockquote>
<blockquote>
A set of update operations on a semantically consistent schema extension ''preserves semantic consistency'' if the resulting schema extension is also semantically consistent.
</blockquote>
<blockquote>
The ''uniqueness'' criterion is controversial and requires some justification. This criterion says that the inverse mapping (of the view definition) from view extensions to schema extensions must be a function.
</blockquote>

They add:
<blockquote>
There is another uncomfortable dimension to the issue of translatability. In our examples, we translated a view insertion only into ''insertions'' on the base relations. Should we permit an insertion to map to deletions and replacements as well?
</blockquote>

Their conclusion I find elusive (and it appears only at the end of the abstract, rather than in the Conclusion section):
<blockquote>
In summary, our theorems show that there are very few situations in which view updates are possible--even fewer, in fact, than intuition might suggest.
</blockquote>
How few are "very few"? Compared to what? How few "might intuition suggest"? Was the prevailing opinion at the time that all or nearly all updates through views were possible?

== Commentary, Critique ==

Taking the requirements in sequence presented.

=== ''no extraneous updates'' ===

In other words (and to put it positively), each "update" in '''U''' must be necessary to achieving the required effect on the extension. (But this doesn't say what an "update" is. Presumably any tuple inserted, deleted or replaced. The only example given is a tuple insert into base where a value is to be concocted for an attribute projected out of the view. D&B regard such a value as arbitrary, because any other valid value would do as well. Curiously, they instead propose inserting NULL -- as if that's not arbitrary!) So both tuples and attribute values can be ''extraneous''.

=== ''no side effects'' ===

That is, the effect on the view must be exactly what was requested in the update. This is "no side effects" in the sense "A secondary, typically undesirable effect" [Oxford online dictionary]. This would be an uncontroversial criterion were it not that:
* Date & McGoveran's 1994 treatment did not require it.
: (And Date had to correct that by giving a grand title "Assignment Principle".)
* SQL makes it optional (WITH CHECK OPTION defined on the view) -- that is, with the CHECK opted off, it is possible (for example) to 'successfully' insert tuples that do not subsequently appear in the view. ('Successfully' in the sense there is no error message, and the tuples are inserted into base.)
: This is a strange sort of non-optional OPTION: for some views opting off prevents any attempts at certain updates through the view -- even for tuples that could validly appear.

=== ''preserves semantic consistency'' ===

I.e. all constraints must hold; Date's "Golden Rule". Again uncontroversial. D&B consider only key/Functional Dependencies, not Foreign Key constraints/INclusion Dependencies, nor more exotic constraints. "Since keys are syntactic constructs, they will give us a compile-time check on update translatabililty." [Section 5.] And their detailed workings do not take any opportunity to consider at run-time the content of the base relations.

=== ''uniqueness'' ===

D&B admit up front this is controversial. The three sentences immediately following the explanation above:
<blockquote>
The alternative, of course, is that there are several distinct sets of schema updates that will alter the view extension as desired. The problem in the latter case is how to choose which set to apply. An arbitrary choice seems unacceptable.
</blockquote>
I agree "an arbitrary choice seems unacceptable" -- this is the same thinking as rejecting ''extraneous'' updates.

As to "how to choose", I think D&B have simply made an error in logic (their "of course" does not follow). For there to be a unique such "set of schema updates", yes it would be sufficient for there to be an inverse mapping from view to schema (base) -- that's an ideal; but it is not necessary. To be ''unique'', all that's needed is there be one set of non-''extraneous'' schema updates that wil alter the view extension as desired. That is, one set that alters the view extension as desired for this particular update request (delete, insert, etc). The inverse mapping criterion amounts to not only achieving this particular request, but also being able to reverse that request, returning both the view and base to ''status quo ante''.

=== map ''insertions only into insertions'' ===

From later in the explanation:
<blockquote>
Some additional semantics are required. We have chosen to map view updates of one type (insertions, deletions, replacements) to schema updates ''of the same type''. Theoretically, this choice is arbitrary. Intuitively, though, it makes good sense ...
</blockquote>

I cannot see it makes sense in all cases: the only way to ensure insert-through-MINUS is to insert into the minuend, but delete from the subtrahend -- otherwise the insertion will not appear in the result, i.e. a ''side effect''.

The examples D&B consider here (such as replacing a tuple for a requested insert, in order to preserve semantic consistency) all fail on other of their criteria -- especially causing ''side effects'', or risking causing ''side effects'' depending on other content of the base schema.

Furthermore since they're concluding "there are very few situations in which view updates are possible", there is no requirement for "some additional semantics". 'Back off' the semantic requirements, and more views will be updatable-through.

== The paper's contribution to [[Update through views: a possible approach]] ==

The ''preserves semantic consistency'' ("Golden Rule") and ''no side effects'' ("Assignment Principle") are my prescription 1 and 2.

D&B's aim for "compile time check on update translatability" is another implicit criterion/restraint on algorithms. It appears as my prescription 3.

''no extraneous updates'' and ''unique'' set of updates are my prescription 4 (necessary and sufficient/''essential'' tuples and attribute values) -- which is more explicit about what constitutes a "set of updates" and what it is for something in that set to be ''extraneous''.

Can I express the prescriptions as succinctly as D&B's criteria?

Given a semantically consistent schema extension '''$*''', we say that an update operation '''u''' on view extension '''V*''' is ''translatable'' if there is a set of tuple inserts, deletes and replacements '''U''' on '''$*''', together ''sufficient'' to produce the desired update on '''V*''', such that each tuple operation is ''necessary'' in '''U''', the ''precise effect'' on '''V*''' is as requested, '''U''' ''preserves semantic consistency'', and the ''translation is statically determinable'' purely from the form of the update request, the schema and view definition and the semantic integrity constraints.

== References ==

Dayal and Bernstein 1978 "On the Updatability of Relational Views”
https://pdfs.semanticscholar.org/39f4/853a35a913c714c5f3956dbefd02916447c4.pdf

See also [[Update through views: a possible approach#References]]

Update through views: rewrites

2017-02-07T10:31:45Z

AntC: /* Semantics: effect of update operations */

[todo: currently includes all examples from discussions; add more rewrites for full coverage; precisely specify the rewrite rules and qualifying conditions]

== Preliminaries/general approach ==

Assume a variant of '''Tutorial D''' in which targets for update can be relational expressions, not merely relvar names. Then a view name (virtual relvar) is to be a shorthand for its defining expression. We're already doing that in read contexts. Do so also in update target contexts.

I.e. if there's a virtual defined in the form
* VAR ''V'' VIRTUAL (''R'' WHERE ''p'')
: as a target for update
* UPDATE ''V'' WHERE ''q'' : ''assigns'';
expand to the syntax for update 'targets' as relational expressions:
* UPDATE (''R'' WHERE ''p'') WHERE ''q'' : ''assigns'';
: Is only a smidgeon away from:
* UPDATE ''R'' WHERE (''p'' AND ''q'') : ''assigns'';

So that is now targetting a base variable.

A virtual's defining expression might itself refer to virtuals. Recursively substitute their defining expressions, until the target expression consists only of base relvar names, literals/constants and relational operators.

Where a given base relvar appears more than once in the target expression, refactor the expression (if possible) so that it appears only once. For example:
{|
|-
| style="width: 40%; " | (''R'' WHERE ''p'') UNION (''R'' WHERE ''q'') || ==> ''R'' WHERE (''p'' OR ''q'')
|-
| ''R'' MINUS (''R'' WHERE ''q'') || ==> ''R'' WHERE NOT ''q''
|}
: That is, refactor using the equational equivalences used typically for optimising query plans. These must be information-preserving.
: If a multiply-occuring base relvar cannot be refactored to a single occurence, that is of itself survivable, but it might have the effect that some ''relexpr'' is not updatable-through, whereas a suitably refactored expression would be.

If there's an IND between two relations ''R1, R2'', it doesn't seem a big stretch to put them together as target in a single update statement, rather than two. (That is, put them together as a shorthand for the Multiple Assignment. Figuring out the separate updates is something a dbms could do mechanically; why impose that load on the programmer?)
{|
|-
| style="width: 40%; " | INSERT (''R1'' JOIN ''R2'') ''v''; || ==> INSERT ''R1'' (''v'' {attribs of ''R1''}''',''' INSERT ''R2'' (''v'' {attribs of ''R2''});
|}

In various examples I've identified the sort of criteria that can be considered:
* keys and cardinality of joins
* constraints (particularly INDs)
* projections that make attributes 'inaccessible' from the view
* the form of the update request, Prescription 2.
(for example DELETE ... WHERE ... could succeed whereas DELETE ... v might not.)
* in general anything that can be examined at compile time, Prescription 3.

== Semantics: effect of update operations ==

For definiteness, this is the specified effect for the update operations (Prescription 2), in style of RM Prescription 21
<blockquote>After assignment of v to V (the “target variable”), the equality comparison V = v shall evaluate to TRUE.</blockquote>

:: These are entirely standard; stated here to show equivalences of update operations.

{|
! style="width: 35%; " | Operation (see [[#Notation]]) !! After update this equation shall hold true (where ''re' '' is the 'after' value)
|- style="vertical-align:top;"
| INSERT ''re'' ''v''; || ''re' '' == ''re'' UNION ''v''
|-
| DELETE "re" ''v''; || ''re' '' == ''re'' MINUS'' ''v''
|-
| DELETE "re" WHERE ''p''; || ''re' '' == ''re'' MINUS (''re'' WHERE ''p'')
|- style="vertical-align:top;"
| UPDATE ''re'' WHERE ''p'' : ''assigns''; || ''re' '' == (''re'' MINUS (''re'' WHERE ''p'')) UNION ''Upd''((''re'' WHERE ''p''), ''assigns'')
|- style="vertical-align:top;"
| ''re'' ''':=''' ''v''; // assignment || ''re' '' == ''v'', == (''re'' MINUS (''re'' MINUS ''v'')) UNION (''v'' MINUS ''re'')
|}

The rewrites may take advantage of the following equivalences, especially so that some operation be supported which would not otherwise be updatable-through.

{|
! style="width: 40%; " | Operation !! ==> equivalent operation
|-
| INSERT ''re'' ''v''; || ==> ''re'' := ''re'' UNION ''v'';
|-
| DELETE ''re'' ''v''; || ==> ''re'' := ''re'' MINUS ''v'';
|-
| DELETE ''re'' ''v''; || ==> DELETE ''re'' WHERE (rel{tup{*}} MATCHING ''v'');
|- style="vertical-align:top;"
| ''re'' ''':=''' ''v''; || ==> DELETE ''re'' (''re'' MINUS ''v'') ''',''' INSERT ''re'' (''v'' MINUS ''re'');
|}

: In particular, ''':=''' assignment is only supported on condition that both DELETE and INSERT are supported, so usually is rewritten as such.

== Sub-terms that are not updatable-through ==

Where a sub-term is a literal/constant, it is not updatable-through. (In effect it is subject to a constraint that it always be that value, so falls under Prescription 2 "Golden Rule".) Rewrites can take advantage of that constraint to disambiguate rewrites. For example

[to do]

== Notation ==
{|
|- style="vertical-align:top;"
| style="width: 25%; " | ''relexpr, re, re', re1, re2, ...'' || relational expressions
|- style="vertical-align:top;"
| ''R, R', R1, R2, ...'' || relvar names (i.e. bases)
|- style="vertical-align:top;"
| ''p, q, p1, q1, ...'' || predicate expressions (booleans) for WHERE clauses
|- style="vertical-align:top;"
| ''assigns'' || attribute assignment lists in UPDATE or EXTEND
|- style="vertical-align:top;"
| ''Upd''(''relexpr'', ''assigns'') || a function that applies ''assigns'' to the relation value of ''relexpr'', yielding a relation value
|- style="vertical-align:top;"
| ==> || rewrite rule: transform the left operation to the right
|- style="vertical-align:top;"
| <==> || two-way rewrite: transform in either direction
|- style="vertical-align:top;"
| rel{tup{*}} || a singleton relation formed from the 'current' tuple of some enclosing relation expression
|- style="vertical-align:top;"
| ''relop'' || an arbitrary relational operator (infix), including projection considered as an operator
|- style="vertical-align:top;"
| ''relexpr'' {attribs of ''re2''} || a projection of ''relexpr'' on the attributes of ''re2''
|- style="vertical-align:top;"
| ''upd1'' ''',''' ''upd2''; || Note the ''',''' comma, not semicolon separating two update statements. This is standard '''Tutorial D''' Multiple Update (aka Multiple Assignment). Typically the rewrites for a target with more than one base relvar will be set of Multiple Updates (separated by commas), one for each relvar. The rewrites will 'walk' down the target's expression tree, generating an update for each sub-term until it gets to the base relvars.
|}

== JOINs ==
A) INSERT through 1:many JOIN with IND
Supported for update.
* INSERT (R1 JOIN R2) v ;
: ==> INSERT R1 (v{attribs of R1}), INSERT R2 (v{attribs of R2});

B) INSERT through 1:many JOIN without IND
Not supported: an INSERT on the 1 side could MATCH tuples already in the many side,
that would thereby 'appear' in the result; so breaking Assignment Principle.

C) DELETE through 1:many JOIN (with or without IND)
Supported: delete from the many side only.
* DELETE (R1 JOIN R2) v; // R2 is the many side
: ==> DELETE R2 ( (R2 MATCHING R1) MATCHING v);
Deleting from the 1 side might 'unMATCH' non-targetted tuples on the many side,
that would thereby 'disappear' from the result.
If no such tuples, we might DELETE the 1 side, but that's not essential.

D) DELETE through 1:1 JOIN with two-way IND (i.e. EQD)
Supported: delete from both sides.
* DELETE (R1 JOIN R2) v;
: ==> DELETE R1 ( (R1 MATCHING R2) MATCHING v), // Multiple Update
:: DELETE R2 ( (R2 MATCHING R1) MATCHING v);

E) DELETE through 1:1 JOIN with a single IND
Supported: delete from the dependent (subset) side only.
* DELETE (R1 JOIN R2) v; // R2 is the subset side
: ==> DELETE R2 ( (R2 MATCHING R1) MATCHING v);

F) DELETE through 1:1 join without IND
Not supported: could be achieved by deleting from either side only or both.
Then neither tuple DELETE is essential.

: Assign through 1:many JOIN with IND
* (R1 JOIN R2) := v;
==> DELETE (R1 JOIN R2) ((R1 JOIN R2) MINUS v), INSERT (R1 JOIN R2) (v MINUS (R1 JOIN R2));

== Restrictions ==

The '''Appendix A''' approach is that Restrictions are Joins. And yet joins that arise from restrictions are typically not joins of bases. Examples:

* (R WHERE X = 1) <==> R JOIN REL{TUP{X 1}}
: REL{TUP{X 1}} is not a base. In fact it's a constant, so not updatable at all.

* (R WHERE X > Y) <==> R JOIN REL{{{x, y} | x IN dom(X), y IN dom(Y), x > y}}
: That REL{ } is not a base. I've defined it using set builder notation. In fact it's a constant, so not updatable at all.

* In case of (R WHERE <subselect on R2>) we need to consider more carefully. Typically R2 has attributes that don't appear in R, so any update would amount to update-through-projection. Which is a different kettle of fish to update-through-join.

So we need update-through-restriction, which is usually regarded as non-controversial:
* INSERT (R WHERE p) v; ==> INSERT R (v WHERE p);
* DELETE (R WHERE p) v; ==> DELETE R (v WHERE p);
* DELETE (R WHERE p) WHERE q; ==> DELETE R WHERE (p AND q)
* Therefore assign(:=) is supported, being a combo of DELETE, INSERT.
* UPDATE also supported, being a combo of DELETE, INSERT.
: A tad tricky because the updated tuples might fail the restriction.
: And that attempt should be rejected as failing prescription 2 "Assignment P". aka SQL's WITH CHECK OPTION, approximately.
: Assume I have a function Upd(rel, assigns) that applies assigns to rel:
: UPDATE (R WHERE p) WHERE q : assigns; ==>
: IF IS_EMPTY(Upd(R WHERE (p AND q), assigns) WHERE NOT p)
: THEN UPDATE R WHERE (p AND q) : assigns ;
: ELSE Fail ;

== Projections ==

Projections are awkward for updating through. Push projections towards the leaves as far as possible, for example:
* For [NOT] MATCHING, which needs a projection and JOIN
: '''Appendix A''' gives: ''re1'' MATCHING ''re2'' ==> (''re1'' JOIN ''re2'') { attribs of ''re1'' }
: Instead: ''re1'' MATCHING ''re2'' ==> ''re1'' JOIN (''re2'' { attribs in common } )

* For projections that are really implementing RENAME, change to RENAME
: (EXTEND ''re'' : { B := A }) {ALL BUT A} ==> (''re'' RENAME A AS B)

* For no-op projections (i.e. is projecting all attributes), all updates are supported.
: Rewrite ''updop'' (''re''{ ... }) ...; ==> ''updop'' ''re'' ...;

G) DELETE through projection
Supported (whether or not the projection is key-preserving.)
DELETE (R{ ... }) WHERE p; ==> DELETE R WHERE p;
DELETE (R{ ... }) v; ==> DELETE R (R MATCHING v);
We must DELETE exactly those base tuples to achieve the DELETE of the proj.
We can't DELETE too many, by those rewrites.

H) INSERT through projection
Not valid. (No surprise.) Therefore

I) assign (:=) through projection
Not valid.

J) UPDATE through projection
Valid providing the projection is key-preserving (i.e. at least one key).
UPDATE (R{ ... }) WHERE p : assigns; ==> UPDATE R WHERE p : assigns;
Note: the assigns could be changing the key.

Valid even if the projection is not key-preserving,
providing the assigns are not changing attribs in the based-on's key
(for at least one key).

[For ref: Dave's suggested 'template' for spcifying rewrites]

2. Update through JOIN

Given r1 JOIN r2 where r1 and r2 are arbitrary relations.

a. Rewrite
UPDATE r1 JOIN r2: {p := q}
as
UPDATE ….

b. Rewrite
INSERT (r1 JOIN r2) v
as
INSERT ….

c. Rewrite
DELETE r1 JOIN r2 WHERE p
as
DELETE ...

d. Rewrite
(r1 JOIN r2) := v
as
...

Or: Not supported.

Update through views possible approach

2017-02-06T09:02:05Z

AntC: /* Musings: a possible comparison */

(In draft as at early February 2017.)

It is assumed the reader is familiar with the topic of update through views. 'View' is the term usual in database discussions, as for example in SQL. The ttm term is 'Virtual relvar'. Updating through views is discussed, for example, in both DTATRM and DBE. Most textbooks on the Relational Model or SQL discuss views and at least mention updating through views.

== Background ==

Update through views is a regular discussion topic on the ttm forum. And a regular topic for Chris Date, co-author of The Third Manifesto. He has published many treatments, since particularly a series of articles (with David McGoveran) 1994 [see [[#References]] below for publication details]. Arising from that 1994 treatment also was the Principle Of Orthogonal Design, aimed at making update through views more tractable. McGoveran continues to publish on the topic (nowadays separately to Date), emphasises Orthogonal Design as key to updating databases -- albeit a different interpretation from Date. The topic has also been much discussed on older forums, such as comp.database.theory.

There is a wide range of opinions on the desirability, possibility and practicability of update through views:

* Those who assert update is possible through all views, and the mechanisms merely need refining.
* Those who prescribe update should be possible through all views "that are theoretically updatable".
** (The quote is from Codd's 12 rules (1985), rule 6. The narrative for that rule includes a definition of 'theoretically updatable'.)
* Those who think some but not all views are updatable through, (which is not inconsistent with Codd 1985) and there is merit in a relational dbms being able to support that ability.
** Note that the SQL standard stipulates some capabilities, which have been somewhat implemented by vendors.
* Those who think that although some views might support being updated through, that is certainly not all of the views encountered in practice, so the uncertainty and continuing debate do not justify implementing a feature that can at best be only partial.
* Those who are adamant that (even if some views are updatable-through unproblematically), it is an unnecessary feature, and adds complexity both to the dbms and to developers/schema designers wanting to update the database.
** (It is true that update to base relvars is always sufficient, and necessarily so: the objective for update through views is to translate updates requested against views into updates against base.)

The "possible approach" propounded in this article is squarely aimed at getting some progress in the middle of this range. Specifically:
* The debate has tended to be polarised, with the most prominent advocates (Date particularly) at the "all views can be updated through" position.
* Date's continuing inability to 'solve' the problem (even to his own satisfaction) have lead to many being sceptical.
* The only major attempt at a partial implementation is SQL. It is beset with limitations and hard-to-explain behaviour. (And subtle differences between different vendors' implementations.) Such that most developers avoid the 'feature', and advise others to do the same. (See, for example, regular questions on StackOverflow.)
* Consequently there appears to be little thinking that acknowledges some views can be updated through, some not, and seeks to arrive at a precise characterisation of which and why. (And how, for those updates that can be supported.)

== Considerations for an approach ==

[email from the forum]

<blockquote> On Jan 21, 2017, at 2:53 AM, Anthony Clayden <anthony.d.clayden@gmail.com> wrote:

The whole topic has suffered from too much ad-hockery.
I have a small and perfectly-formed set of rules in mind.
</blockquote>

<blockquote>So my general position:
* Some views are updatable-through; some aren't.
* Some views are INSERTable-through but not DELETEable-through, and ''v.v.''.
* rather than putting effort into developing byzantine rules to make more views updatable;
* the effort should go into agreeing a small set of rules [**] that 
: a) are clear what's updatable, what isn't;
: b) have clear effects for views that are updatable;
: c) can give clear explanations (compilation error messages) for those that are not.
</blockquote>
Note [**] the "rules" were in later discussions re-titled as "prescriptions". The following has been editted accordingly.

<blockquote>I have four-and-a-bit prescriptions. Of which the bit is merely to say that if the four prescriptions don't give a clear answer how to update, then the view is not updatable-through (for that action) -- i.e. c) above.</blockquote>

== The prescriptions ==

The first two prescriptions are standard on this topic [Dayal & Bernstein 1978]'s ''preserves semantic consistency'' and ''no side effects''.

The third prescription is really to make view updating tractable and predictable/manageable for the dbms and application developers. The same motivation as for ttm's OO Prescription 1 (compile time type checking).

It is the fourth I've long had trouble with -- hence this prologue. When I say "fourth", this has been up to 4 or 5 separate rules in my previous versions. I think I've now found a formulation to condense [D&B 1978]'s ''unique'', ''no extraneous updates'', my own ''unambiguous''; and to find grounds to reject [D&B 1978]'s "uncomfortable dimension" with which I've never been, er, comfortable. The notion -- that both tuples for the update and their attributes be ''essential'' -- is cribbed from D,D&F's ETNF paper. [Darwen, Date, Fagin 2012, ETNF = Essential Tuple Normal Form]

There are footnotes for each prescription, but let's state them succinctly first:

# At all times all constraints must hold. (rubric: The "Golden Rule".)
# Any update through a view must have precisely the effect on the content of the view as if it were a base relation. (rubric: "Assignment Principle")
# That a view is updatable-through (for some action INSERT, DELETE, UPDATE, assignment :=) must be determined by reference only to the schema, view's definition, constraints and the specified update effect for that action, per prescription 2. (rubric: "Not dependent on the happenstance of content")
# Noting that the update is to be effected by some combination of tuples deleted and inserted into the database (base relations): each such tuple must be necessary to achieving 1. and 2., the set of tuples (deletes and inserts) must be sufficient, and each attribute value must be similarly necessary. (rubric: ''essential'' tuples, ''essential'' attribute values.)
# If there is no set of necessary, sufficient tuples/attributes per 4., that view is not updatable-through for that action.

=== Footnotes to the prescriptions ===

# Knowing all constraints must hold, the compiler can:
#: a) rely on them all holding before it plans the update steps;
#: b) examine them (in the catalogue or otherwise) to guide the update.
# I'm not expecting the update actions to be necessarily limited to the traditional INSERT/DELETE/UPDATE/assignment(:=).
#: Opportunity for new forms of update. (I've toyed with a few on the forum.) 
# The consequence is that the algorithm for update be derivable at compile time.
#: (So could be implemented as a stored procedure.)
#: Suggested alternative formulation: “Whether a given view can be updated-through or not must be determined solely from the declared database constraints, the given view's definition, and the requested update to be performed to the view (and thus update through it).”
# ''Essential'' tuple means that it is ''necessary'' for those tuples to be deleted/inserted to comply with 1., 2 for all valid states of the database.
#: ''Essential'' attribute value means that value is the only possible to comply with 1., 2 for all valid states of the database.
#: ''Sufficient'' requires that if there are two (or more) different sets of tuple actions/values that comply:
#* and one is a superset of another (deletes and inserts taken separately), then the tuples in the difference are not ''necessary'' (not ''essential'').
#* or the sets only partially overlap (and their intersection is not sufficient), then the tuples unique to each set are not ''necessary'' (not ''essential'').

The ETNF paper's use of ''essential'' tuple is (loosley speaking) that without that tuple some constraint would be violated, and we couldn't 'recreate' that tuple from other content to satisfy the constraint. I'm extending that idea: without that tuple (inserted or deleted) in the base some constraint would be violated and/or the update would not have precisely the effect requested for the view.

== References ==

* Codd's 12 rules -- Rule 6 and definition, see also discussion under Rule 9.
: (The bare rules just prescribe.)
: http://computing.derby.ac.uk/c/codds-twelve-rules/
* Dayal and Bernstein 1978 "On the Updatability of Relational Views”
: https://pdfs.semanticscholar.org/39f4/853a35a913c714c5f3956dbefd02916447c4.pdf
: references a 1975 paper Chamberlin, Gray, Traiger
: https://www.computer.org/csdl/proceedings/afips/1975/5083/00/50830425.pdf
* Bancilhon and Spyratos 1981 "Update Semantics of Relational VIews"
: http://pages.cs.wisc.edu/~jhuang/qual/update-semantics-of-views.pdf
* Darwen, Date, Fagin 2012 "A Normal Form for Preventing Redundant Tuples in Relational Databases"
: http://researcher.watson.ibm.com/researcher/files/us-fagin/icdt12.pdf
* An example SQL implementation (SQL-Server) reference manual
: https://msdn.microsoft.com/en-us/library/ms187956.aspx#Anchor_3
* For another round of the continuing debate
: http://www.dbdebunk.com/2016/12/on-view-updating-c-j-date-and-d.html
: note this is Fabian Pascal reporting a Date/McGoveran posting from 2004, it's unlikely either author would hold the same views today.
* Links to the Date & McGovern 1994 series of articles (need to dig them out via the wayback machine)
: http://www.dbdebunk.citymax.com/page/page/622302.htm -- Part 1 links through to the other parts, in a haphazard fashion
<blockquote>I am not alone in thinking that the treatment of view updating within the overall theory of relational databases has always been rather unsatisfactory for one reason or another. As Nat Goodman puts it: "... there is no theory behind any of this. Each [rule] seems intuitively correct, but there is no overall framework. It would be better to have a general rule that states what a correct view update algorithm has to do, and then derive the special rules for each case from that general rule. Without this, the [rules] feel like a crazy patchwork of exceptions and special notes. In some cases, two or more [rules] are equally sensible ..." (and so on).</blockquote>
: http://www.dbdebunk.com/page/page/622150.htm -- Part 6 is the concluding summary
<blockquote>'''Comments On Republication:''' [on dbdebunk] Originally published in Database Programming & Design 7, No. 6 (June 1994) and published as a two-part article in RELATIONAL DATABASE WRITINGS1991-94. It is republished here by permission of David McGoveran, Miller Freeman Inc. and Pearson Education, Inc. © All rights reserved by C.J. Date. Research has shown that certain detail level corrections might be needed, which we may undertake in the future. However, we still believe strongly that the overall approach is sound.
</blockquote>

== Musings: a possible comparison ==
<blockquote>
On 3/02/2017, at 9:06 PM, Dave Voorhis <dave@armchair.mb.ca> wrote:

The essence of the debate is perhaps something like this:

The update-through-views proponent sees this...

: VAR v VIEW ...

…and feels it is perfectly reasonable to allow

: UPDATE v WHERE Name = ‘Dave Vorhis’: {Name := ‘Dave Voorhis’}.

The update-through-views opponent sees the above, and feels it is akin to...

: #define e (int)((p / n + sqrt(r) * 0.156) * pow(q, 3))

…and expecting an assignment like e := 2 to meaningfully update p, n, r and q.

The update-through-views proponent sees the above and says no, it’s really akin to…

: a[e] := 2;

…which is fine, isn’t it?

The update-through-views opponent disagrees that it’s akin to updating an array.
</blockquote>

(Speaking as an update-through-views-sometimes proponent:)

I've never been happy likening update-through-view to update-to-array. Because there's only one way to update an array, and if two different expressions are targetting the same cell, that's referentially transparent. It's a little more like being able to target a slice/slab/sub-cube of an array (which some languages support), in that you're updating multiple cells with one statement. (For comparison, there's a quote alleged from Dijkstra that all array updates should be seen as assigning to the whole structure, even if they're targetting a single cell. Similarly for targetting components of data structures in general.) But I'm still not happy with the analogy.

An array you can't change the size/shape merely by assigning a new value; you can't at run time insert/delete cells (indexes) in the middle; you can't add an extra dimension. (Changing shape would be something like renumbering the indexes in an array with rationals between the integers, and leaving 'gaps'.)

Contrast that with updating relations -- even just base ones -- there are expressions that target the same tuple, but in non-obvious ways:

* S WHERE S# = 'S1';
* S WHERE SNAME = 'Smith';

You can update that base, and those same expressions no longer target the same tuple:

* UPDATE S WHERE SNAME = 'Smith' : {SNAME := 'Smythe'};
* INSERT S REL{TUP{S# 'S17', SNAME 'Smith', ...}};

(Indeed the idea of "the same tuple" is a nonsense, unlike an array cell. I mean: no longer return the same result as each other.)

You can update a relation to change it's size/shape, such that expressions that used to target a single tuple now target multiple tuples, or no tuples at all.

Note all this applies just with update to base relations.

If we're looking for a conventional data structure "akin to" relations, could I suggest a doubly-linked list:

* There are expressions that target the same cell, but in non-obvious ways
:: left(left(left(L))) === right(right(right(right(L))))
* You can at run time insert/delete cells, which changes the list's size/shape, and
* thereby those expressions no longer target the same cell.
* You can 'target' cells by content: form a list by filtering.

* For extra fun, consider that each cell could itself be a doubly-linked list.

So what would be the doubly-linked equivalent of update-through-views vs to-base? Perhaps targetting through the left vs through the right. Both are feasible; and for every leftwards update there's an equivalent rightwards update. But each time you insert/delete cells you have to recalibrate those equivalences.

You could also target by content an update to doubly-linked list: insert before the leftmost cell value 'XYZ'; delete 3 cells to the right of the rightmost cell value 'ABC'.

The rewrites for updates given in this approach take it that a target for update can be any relational expression, with a view name (virtual relvar) merely standing for its defining expression in a target context.

== [[Update through views: rewrites]] ==

Click on the section heading to go to the page with rewrites.