Medium 9781449357849

View Updating and Relational Theory

Views: 1051
Ratings: (0)

Views are virtual tables. That means they should be updatable, just as "real" or base tables are. In fact, view updatability isn’t just desirable, it’s crucial, for practical reasons as well as theoretical ones. But view updating has always been a controversial topic. Ever since the relational model first appeared, there has been widespread skepticism as to whether (in general) view updating is even possible.

In stark contrast to this conventional wisdom, this book shows how views, just like base tables, can always be updated (so long as the updates don’t violate any integrity constraints). More generally, it shows how updating always ought to work, regardless of whether the target is a base table or a view. The proposed scheme is 100% consistent with the relational model, but rather different from the way updating works in SQL products today.

This book can:

  • Help database products improve in the future
  • Help with a "roll your own" implementation, absent such product improvements
  • Make you aware of the crucial role of predicates and constraints
  • Show you how relational products are really supposed to behave

Anyone with a professional interest in the relational model, relational technology, or database systems in general can benefit from this book.

List price: $31.99

Your Price: $25.59

You Save: 20%

 

17 Slices

Format Buy Remix

1. A Motivating Example

ePub

Example is always more efficacious than precept

Samuel Johnson:

Examples throughout this book are based for the most part on the familiar (not to say hackneyed) suppliers-and-parts database. I apologize for dragging out this old warhorse yet one more time, but as Ive said elsewhere, I believe using the same example in a variety of different publications can be a help, not a hindrance, in learning. In SQL terms,[4] the database contains three tablesmore specifically, three base tablescalled S (suppliers), P (parts), and SP (shipments), respectively. Sample values are shown in Figure1-1.

Figure1-1.The suppliers-and-parts databasesample values

The semantics (in outline) are as follows:

Table S represents suppliers under contract. Each supplier has one supplier number (SNO), unique to that supplier; one name (SNAME), not necessarily unique (though the sample values shown in Figure1-1 do happen to be unique); one status value (STATUS); and one location (CITY). Note: In the rest of this book Ill abbreviate suppliers under contract, most of the time, to just suppliers.

 

2. The Technical Context

ePub

What I assume you shall assume

Walt Whitman:

The discussions in the previous chapter were based on SQL for reasons of familiarity. Unfortunately, however, SQL really isnt suitable as a basis for the kind of investigation and detailed technical discussion the subject at hand demands. For one thing, the concepts we need to examine often cant be formulated in SQL at all; for another, even when they can, SQL usually manages to introduce so much irrelevant and unnecessary complexity that it becomes hard to see the forest for the trees, as it were. For such reasons, I intend to use as a foundation for the rest of the book, not SQL as such (though Ill still have a few things to say about SQL as such from time to time), but rather a hypothetical language called Tutorial D.[13] Now, I believe that language is pretty much self-explanatory; however, a comprehensive description can be found if needed in the book Databases, Types, and the Relational Model: The Third Manifesto, by Hugh Darwen and myself (3rd edition, Addison-Wesley, 2006).[14]

 

3. The View Concept: A Closer Look

ePub

Distance lends enchantment to the view

Thomas Campbell:

Every scientific discipline has its share of unsolved problems. In mathematics, for example, theres the Riemann Hypothesis, which nobody has managed to prove or disprove in over 150 years; in computer science, theres the P = NP? question, which is still open after some 40 years; in physics and cosmology, theres the long search for a theory of everything, which remainsin many peoples opinion, though possibly not in everyonesjust that, a search; and in database theory, theres the problem of view updating. Now, I obviously dont mean to suggest that the problem of view updating is in the same league as the Riemann Hypothesis or the P = NP? question or some hypothetical theory of everything;[35] however, I do claim its of considerable practical importance and much theoretical interest. In this chapter, therefore, I want to lay some of the groundwork thats necessary for a systematic attack on that problem.

I begin with the trite observation that a view is a relvara virtual relvar, to be precise, or in other words a relvar that looks and feels just like a real, or base, relvar but (unlike a real or base relvar) doesnt exist independently of other relvars; rather, its defined in terms of, or derived from, such other relvars. Heres a definition:

 

4. Restriction Views

ePub

Updating restrictions

Leads to no contradictions

Anon.:

The bulk of the remainder of this book consists of an investigation into whats involved in updating through the various relational operators (to use the conventional jargon). Thus, this chapter can be seen as the first in a series. In it, I propose to examine in detail the question of updating restriction views specifically (i.e., updating through a restriction operation). Note, however, that many of the issues to be raised in connection with that specific question will turn out to have more general significance; thus, this chapter is thus partly a continuation of Chapter3, in a way. Ill begin by taking a closer look at the motivating example from Chapter1 (with apologies for the small amount of repetition that closer look will necessarily entail).

Just to remind you, the motivating example from Chapter1 involved base relvar S (suppliers) from the suppliers-and-parts database and two restriction views of that base relvar, LS (London suppliers) and NLS (non London suppliers). Here are Tutorial D definitions:

 

5. Projection Views

ePub

Updating projections?

Just follow directions!

Anon.:

Now I want to consider whats involved in updating projection views (i.e., updating through a projection operation). Note: I claimed in the previous chapter that restriction and union views are two sides of the same coin, so to speak; well, a similar remark applies to projection and join views, as well see in this chapter and the next three.

Let me give you some idea as to how the chapter is structured. The discussion overall centers round a set of examplesthree of them, to be exact. The first two both have to do primarily with situations in which we have full information equivalence; the third shows what happens if we dont (i.e., if certain information is hidden). In all three cases, Ill appeal to The Principle of Interchangeability and begin by considering what happens if all of the relvars concerned are base ones; then Ill go on to see how the situation changes if some of them are in fact views.

Lets agree for simplicity to drop attribute SNAME from the suppliers relvar, so that throughout this chapter the name S refers to the following reduced form of that relvar:

 

6. Join Views I: One to One Joins

ePub

This phrase I have coined

For views to be joined

Updating through V

Updates A, also B

Anon.:

Id like to begin this chapter by repeating something I said at the end of Chapter3:

The topic of view updating can unfortunately be quite confusing, even when its not particularly controversial. Part of the difficulty lies in the fact that theres unavoidably a lot of detail to wade through, and its easy to lose ones way in debates and discussions. In particular, its all too easy to forget, especially in examples, which relvars are base ones and which ones are views. Its important to keep a clear head!

I repeat these remarks here because I think its only fair to warn you that they seem to be especially applicable in the case of join views in particular.

Given the foregoing, I thought it might be helpful to give some idea right at the outset of where were going to wind up in our investigations into this topic. Our target, of course, is a set of rules for updating through join. And what I claim were going to finish up with is a set of rulesa single, uniform set of rulesthat work for all joins.[81] In particular, its not going to make any difference whether the join were dealing with is one to one, one to many, or many to many. In fact, let me immediately show in outline what the rules in question look like. Assume were trying to update a view V defined as A JOIN B. Then the rules can be stated as follows:

 

7. Join Views II: Many to Many Joins

ePub

Recent researches at Harvard

And further researches at Yale

Show that joins can all be updated

By removing the spikes from their tail

Anon.:

Now I want to examine the question of many to many joins (Im deliberately leaving the one to many case till last). As in Chapter6, I think it might help to state right at the outset where our investigations are going to take us. As you might intuitively expect, the many to many case is going to turn out to involve certain complications, complications that didnt arise in the one to one case; nevertheless, I claim were still going to wind up with essentially the same rules as before. That is, given a view V defined as A JOIN Bwhere the join is now a many to many join specificallythe rules are still going to look like this (in outline):

Consider a simplified version of our usual suppliers and parts relvars in which suppliers have no attributes except SNO and CITY and parts have no attributes except PNO and CITY, thus:

Suppose also for the sake of the example that every supplier city is required to be a part city and vice versain other words, theres a constraint in effect (actually an equality dependency once again) that looks like this:

 

8. Join Views III: One to Many Joins

ePub

What Codd hath joined

Update such without blunder

Anon.:

Chapters Chapter6 and Chapter7 discussed one to one and many to many joins, respectively; this chapter is concerned with the sole remaining case, one to many joins. But of course you know by now where our investigations are going to take uswere going to wind up with the same general rules as we did in the previous two chapters:

Once again Ill start with our usual suppliers-and-parts database, but I want to focus in this chapter on relvars S and SP and ignore relvar P (Ill also continue to ignore attribute SNAME and, for simplicity, attribute STATUS as well). So we have two base relvars looking like this:

Moreover, suppose for the sake of this first example that every supplier has to supply at least one part. In other words, suppose theres a constraint in effect (actually an equality dependency once again) that looks like this:

In order to conform to this requirement, lets also agree for the sake of the example to drop the tuple for supplier S5 from our usual suppliers relation.

 

9. Intersection Views

ePub

Updating intersections

Can sometimes need corrections

Anon.:

In this chapter and the next two, I turn my attention to intersection, union, and difference views. Of course, Ive already said something in Chapter6 about intersection views in particular (the subject of the present chapter)recall that intersection is a special case of one to one joinbut theres quite a lot more to be said on the subject.

First I need to say something about the structure of the chapter. Let DB1 and DB2 be a set of base relvars and a set of views, respectively. Now, in the last few chapters, on restriction, projection, and join views, I proceeded in general terms as follows: First, I considered a particular DB1; then I considered a particular DB2 that was information equivalent to that DB1; finally, I considered another DB2 that wasnt information equivalent to that DB1 but involved some information hiding instead. But that approach doesnt work very well for intersection views.[100] The reason is this: Suppose DB1 consists of base relvars A and B (only) and DB2 consists of view V only, defined as the intersection of A and B (i.e., V = A INTERSECT B). Then DB2 will be information equivalent to DB1 only if A = Bin which case (as I hinted in a footnote near the end of Chapter6) theres not much point in defining view V in the first place.

 

10. Union Views

ePub

Listen to mego spread the news

Its easy to update union views!

Anon.:

Now lets move on to union. You wont be surprised to learn that the structure of this chapter is very similar to that of the previous one, on intersection. Just one preliminary remark: A UNION B resembles A INTERSECT B in that its not very interesting if A = B; unlike A INTERSECT B, however, it certainly is interestingwell, somewhat interestingif A and B are disjoint. So my first example will be exactly that, an example involving a disjoint union.

This example is essentially the inverse of the motivating example from Chapters Chapter1 and Chapter4. Thus, were given two relvars, LS (London suppliers) and NLS (non London suppliers), that look like this:

Of course, in terms of our usual suppliers-and-parts database, these relvars are probably viewsviews of relvar S, to be specificbut you can think of them as base relvars if you like. More to the point, observe that these relvars are indeed disjoint, inasmuch as its impossible for the very same tuple to appear in both. Here are the predicates:

 

11. Difference Views

ePub

Ill teach you differences: away, away!

William Shakespeare:

In this chapter Ill consider the question of updating through the relational difference operator (MINUS, in Tutorial D). Now, Im sure you wont be surprised to learn the chapter is fairly similar in structure to its immediate predecessors, on intersection and union. However, it also differshow appropriate!in certain important respects, as youll quickly see. To elaborate briefly: Suppose were given two relvars A and B. Clearly, if A = B, the difference A MINUS B and the difference B MINUS A are both empty, so that case isnt very interesting. Also, if A and B are disjoint, then A MINUS B is equal to A and B MINUS A is equal to B, so that case isnt very interesting either. So the interesting case is the one in which A and B arent equal but do overlap. As in Chapter9, therefore (on intersection), Ill consider two examples, one in which the overlap is explicit and one in which its merely implicit. For reasons that will become clear later, however, this time I want to consider the implicit case first.

 

12. Group and Ungroup Views

ePub

Updating groups

Dont need no loops

Anon.:

I turn now to the question of updating through the relational grouping and ungrouping operators (GROUP and UNGROUP, in Tutorial D). Since you might not be familiar with those operators, Ill begin with a brief tutorial.

Consider the relations shown in Figure12-1, which we can take to be the current values of two relvars called SP and SPQ, respectively. Of course, relvar SP is just the shipments relvar from our usual suppliers-and-parts database.

Figure12-1.Relvars SP and SPQsample values

Now, I hope its at least intuitively obvious that we have information equivalence here once again[119] (certainly the relations shown in the figure both represent the exact same information).

Now, with regard to those two relations, the one on the left of the figure is just a reduced version of our usual sample value for relvar SP, while the one on the right is what we get if we evaluate the following expression on that sample SP value:

Aside: In fact the GROUP invocation just shown is logically equivalent to a certain EXTEND invocationto be specific, the invocation EXTEND SP{SNO}:{PQ := s!!SP}, where !!SP denotes a certain image relation[120]and there are reasons to prefer this EXTEND formulation over its GROUP equivalent. Detailed discussion of such matters is beyond the scope of this book, however. Refer to SQL and Relational Theory for further explanation. End of aside.

 

13. Extension and Summarization Views

ePub

Flimmery flummery

Extension and summary

Both follow the rules

Taught in all the best schools

Anon.:

The relational EXTEND and SUMMARIZE operators resemble each other inasmuch as they both produce a result containing a new computed attribute.[128] Informally, we might say that EXTEND performs computation across tuples, while SUMMARIZE performs computation down attributes. However, I hasten to add that this characterization is loose in the extreme, as is shown byamong other thingsthe fact that SUMMARIZE can actually be defined in terms of EXTEND, as is explained in SQL and Relational Theory (and as indeed was noted in passing in the previous chapter).

Ill begin with a simplified version of an example from Chapter2. First, lets agree for simplicity to ignore all attributes of relvar P other than PNO and WEIGHT. Second, suppose WEIGHT values in that relvar are given in pounds. Third, suppose we want to see those weights in grams. There are 454 grams to a pound, and so we can write:

Given our usual sample values, the result looks like this:

 

14. Updating through Expressions

ePub

When expressions conflict

And views contradict

The results that emerge

These rules will predict

Anon.:

Throughout the book prior to this point, Ive been concerned primarily with the question of updating through some individual relational operation (updating a restriction, updating a projection, and so on). Whats more, Ive been assuming, more or less tacitly, that the rules for updating a relvar defined by means of some more complicated expression can be determined by combining the rules for the operations involved in that expressionfor example, updating a union of two joins can be done by first applying the rules for updating a union and then applying the rules for updating joins. Now its time to take a closer look at that assumption.

I observe first of all that the assumption is surely correct in principle. The reason is that the alternative is just too horrible to contemplate! To spell it out, the alternative in question would mean treating every expression as a special casei.e., defining one set of rules for updating the union of two joins, and another for updating the difference of two joins, and another for updating the join of a union and a difference, and so on and so forth ad infinitum.

 

15. Ambiguity Revisited

ePub

Seal up the mouth of outrage for a while,

Till we can clear these ambiguities

William Shakespeare:

As mentioned at several points in earlier chapters, David McGoveran has a proposal for resolving the ambiguities that can arise in connection with view updating (in the absence of information equivalence, that is). In this final chapter, I want to say something about that proposal. Before I do, however, there are some points I must make absolutely clear:

To say only that his proposal resolves the ambiguities doesnt begin to do justice to Davids scheme overall. Rather, that scheme is (of course) a scheme for addressing the database updating issue in its entirety. It begins by recognizing that, as I explained in Chapter2, the only true variablethe only thing that can really be updated, logically speakingis the entire database (or dbvar, rather, though it doesnt use that term). The database, and the relvars within that database, are characterized by predicates; however, those predicates, unlike the ones Ive been talking about in this book, are completely formal in nature. In particular, they completely subsume what in Chapter2 I called the total database constraint. Update requests too are expressed in terms of such predicates (they might refer to relvars by name for user convenience, but such references serve merely as shorthand for the pertinent relvar predicates). Implementing an update request then consists in combining the database predicates and update predicates appropriately and computing the relation or relations that together satisfy such combined predicates; those relations then effectively constitute the updated portion of the database.[149] For further details, I refer you to Davids patents, which were cited in the Concluding Remarks section of Chapter3.

 

A. Some Remarks on Relational Assignment

ePub

Change is not made without inconvenience

Samuel Johnson:

I claimed in Chapter2 that the generic relational assignment

(where R is a relvar reference, or in other words a relvar name, syntactically speaking, and rx is a relational expression)is logically equivalent to an assignment of the form:[157]

Well, actually, in Chapter2 I used the keywords MINUS and UNION in place of the set difference symbol and the set union symbol , respectively. In this appendix I find it more convenient to use the symbols. Other symbols Ill be using include (set intersection), (set inclusion) and (the empty set). Whats more, in all of these contexts I ought really to be talking in terms of relations rather than general sets, but I propose to overlook this point of detail in what follows. Note: In Chapter2 I also enclosed the subexpression r d (or r MINUS d, rather) in parentheses; in fact, however, no parentheses are needed, as well soon see.

Be that as it may, let me now explain my notation in detail and elaborate on a few important points:

 

B. Relational Operators

ePub

Civilization advances by extending the number of important operations which we can perform without thinking about them

Alfred North Whitehead:

In this appendix, I give for purposes of reference definitions of all of the relational operators discussed in the body of the book. The definitions are given in alphabetical order by name (i.e., the name by which the operator in question is known in Tutorial D); theyre based on definitions in my book The Relational Database Dictionary, Extended Edition (Apress, 2008), but Ive deliberately simplified them slightly here and there for present purposes. Observe in particular that the operators all return a result with a defined heading and therefore a defined relation type, which is thereby the type of any expression that represents an invocation of the operator in question. For further discussion, please refer to SQL and Relational Theory.

EXTEND: 1. (New attribute) Let relation r not have an attribute called A. Then the expression EXTEND r : {A := exp} returns a relation with heading the heading of r extended with attribute A and body the set of all tuples t such that t is a tuple of r extended with a value for A thats computed by evaluating exp on that tuple of r. 2. (Existing attribute) Let relation r have an attribute called A. Then the expression EXTEND r : {A := exp} returns a relation with heading the same as that of r and body the set of all tuples t such that t is derived from a tuple of r by replacing the value of A by a value thats computed by evaluating the expression exp on that tuple of r.

 

Details

Print Book
E-Books
Slices

Format name
ePub
Encrypted
No
Sku
9781449357801
Isbn
9781449357801
File size
0 Bytes
Printing
Not Allowed
Copying
Not Allowed
Read aloud
No
Format name
ePub
Encrypted
No
Printing
Allowed
Copying
Allowed
Read aloud
Allowed
Sku
In metadata
Isbn
In metadata
File size
In metadata