Get Relational concept for computer system Professionals currently with O’Reilly online learning.

You are watching: The difference operator subtracts one table from the other.

O’Reilly members suffer live online training, plus books, videos, and digital contents from 200+ publishers.

Having identified the relvars in the suppliers-and-parts database (see Chapter 3), and also having “loaded” or initialized them (again, watch Chapter 3), we have the right to now start to use them because that “real work.” more specifically, we can now problem queries—i.e., retrieval requests—against those relvars, using operators the what’s referred to as the relational algebra, and also in this chapter I desire to begin our investigation into those operators. Caveat: The chapter is, regrettably, fairly long, and you might want to take it a piece at a time. To assist you in this regard, ns haven’t left every one of the exercises and also answers come the an extremely end of the chapter yet have instead interspersed them at intervals amongst the regular explanatory text.

The relational algebra is composed of a collection of operators that (speaking an extremely loosely) permit us to have “new” connections from “old” ones. Each such operator bring away one or an ext relations as input and also produces another relation together output. For example, the distinction operator (MINUS, in Tutorial D) takes two connections as input and also “subtracts” one indigenous the other, come derive one more relation as output. And it’s really important that the output is an additional relation (that’s the so dubbed closure home of the relational algebra). The reason it’s so important is this: It permits us to create nested relational expressions. To spell the suggest out, due to the fact that the calculation from every operation is the very same kind of point as the input, the calculation from one procedure can end up being the intake (or one of the inputs) come another. For example, we can take the distinction r1 MINUS r2, feeding the result as input to a union v some relationship r3, feed that an outcome as input to an intersection with some relation r4, and also so on.

There’s one analogy right here that might help, to execute with simple arithmetic. In arithmetic, we deserve to (for example) take the amount of two numbers a and also b to acquire a result, c; and that calculation c is the very same kind of thing as the input—they’re every numbers—and so we can take the output and feed it together input to, say, a multiplication operation; and then we can feed the an outcome of that multiplication together input to a subtraction (and so on). In other words, numbers form a closed device under the regular arithmetic operators, and it’s that truth that permits us to write nested arithmetic expressions. Likewise, relations are close up door under the operator of the relational algebra, and also the significance is exactly analogous: together I’ve said, we deserve to write nested relational expressions.

Now, any variety of operators can be defined that to the right the simple definition of “one or much more relations in, precisely one relation out.” listed below I briefly define what are usually assumed of as the initial operators (essentially the ones that Codd defined in his earliest papers);<26> okay give more details that those operator in succeeding sections of the chapter, and also then in Chapter 5 I’ll describe a variety of additional operators. Figure 4-1 gives a photographic representation of those original operators. Note: If you unfamiliar with these operators and also find the descriptions in this preliminary ar a little hard to understand, don’t worry around it. As I’ve already said, I’ll be going right into much much more detail, with many examples, later in the chapter.

Restrict

Returns a relation containing all tuples native a specified relation that accomplish a stated condition. Because that example, we can restrict the companies relation to just those tuples wherein the status value is less than 25.

Project

Returns a relationship containing all (sub)tuples that stay in a specified relation after ~ specified features have to be removed. (As provided in the answer come Q: in Chapter 3, a subtuple is tho a tuple, just as—and indeed exactly because—a subset is tho a set.) for example, we might project the suppliers relation on simply the SNO and CITY qualities (thereby removed the SNAME and also STATUS attributes).

Product

Returns a relationship containing all possible tuples that room a mix of two tuples, one from every of two specified relations. Because that example, allow r1 it is in the forecast of the service providers relation ~ above SNO and let r2 it is in the projection of the parts relation on PNO. Then—thanks to the closure property—we could form the product the r1 and also r2, and the an outcome would consists all possible SNO-PNO pairs such that the SNO value is a caterer number showing up in the service providers relation and also the PNO worth is a component number showing up in the parts relation. Note: “Product” here really way cartesian product, and the operator is occasionally so called.

Intersect

Returns a relationship containing all tuples that show up in both that two specified relations.

Union

Returns a relation containing all tuples that show up in either or both the two stated relations.

Difference

Returns a relation containing all tuples that show up in the first and not the second of two mentioned relations.

Join

Returns a relation containing all feasible tuples that space a combination of 2 tuples, one from every of two mentioned relations, such that the 2 tuples contributing to any type of given result tuple have typical values for the common attributes of the two relations (and those typical values show up just once, no twice, in that result tuple). Note: This type of join was originally referred to as the natural join, to distinguish it from various other kinds—especially the so dubbed θ-join (“theta join”), come be disputed briefly in Chapter 11 in Part III of this book. Since natural sign up with is far and away the most necessary kind, however, it’s come to be standard practice to take it the unqualified ax join to median the natural join specifically, and I’ll follow that practice throughout this book.

The operator of the algebra space generic: they apply, in effect, to all possible relations. For example, us don’t need one sign up with operator to sign up with (say) suppliers and shipments and another completely different join operator to sign up with (say) departments and also employees.

The operator are likewise read-only: lock “read” their operands and they return a result, yet they don’t upgrade anything. In various other words, they operate on relations, not relvars.

Finally, given that the operators of the algebra are undoubtedly all read-only, it complies with that INSERT, DELETE, and also UPDATE (and relational assignment), despite they’re definitely relational operators, aren’t relational algebra operators as such—though, regrettably, you’ll often come across statements come the contrary in the literature. (In fact, of course, INSERT, DELETE, UPDATE, and relational assignment space all, special, update operators, conversely, the algebraic operators are, together I’ve said, all read-only.)

Now us can begin to research the operators of the algebra in more detail. I’ll start with restrict. Consider this query: “Get part information for parts whose load is less than 12.5 pounds.” (I’m suspect here, simply to it is in definite, that part weights are tape-recorded in relvar ns in pounds avoirdupois.) right here then is a Tutorial D formulation of this query:

P whereby WEIGHT and here’s the result, provided our usual sample values:<28>

As you deserve to see, the result is absolutely a relation; what’s more, the heading of that result is the very same as that of the input (i.e., the parts relation, i beg your pardon is to say the current value the relvar P), and also the body of that an outcome consists of simply those tuples the the input because that which the stated restriction condition—viz., weight

 PNO COLOR CITY P1 Red London P2 Green Paris P3 Blue Oslo P4 Red London P5 Blue Paris P6 Red London

 COLOR CITY Red London Green Paris Blue Oslo Blue Paris

Aside: Observe that the result in this example is “all key,” meaning the sole crucial is the whole heading (note the dual underlining in the picture). However, check out Q: in the following chapter for further conversation of this point. End of aside.

By the way, I’d favor to suggest out the it’s intuitively reasonable, as well as being logically correct, to perform duplicate removed in the foregoing example. Consider the initial query as soon as again: “What component color and also city combinations right now exist?” Well, the combination “red and also London” certainly exists; in fact, of course, it appears three times. However the query didn’t ask how numerous times that mix appeared, it just asked even if it is it existed. And also the right answer come a question of the form “Does x exist?” is either yes or no, no a count.<29>

Note: In principle duplicate elimination was done in the vault projection example too, yet in that case it had no effect. And the factor it had no result was that, in the example, the collection of qualities on which the forecast was gift done contained a vital (actually the only key) that the basic relvar. To run ahead the myself because that a moment, let me include that conceptually, at least, duplicate remove is always excellent as component of the procedure of developing the an outcome of part algebraic operator. In practice, however, the just operators (out of the ones questioned in this chapter) because that which duplicate elimination could actually be required—i.e., can actually have actually some result on the result—are projection, i m sorry is the topic of the present section, and also union, come be disputed later in the chapter.

Here then is a definition of the projection operator:

Definition: Let relation r have features called A1, A2, ..., An (and maybe others). Then the expression rA1, A2, ..., An denotes the projection that r top top A1, A2, ..., An, and it returns a relation through heading A1, A2, ..., An and also body consist of of every tuples t such the there exist a tuple in r that has actually the same value for features A1, A2, ..., An as t does.

Points developing from this definition:

 PNO COLOR CITY P1 Red London P5 Blue Paris

SP SNO , PNO , QTY

P whereby CITY = CITY

P where FALSE

 CITY Athens London Oslo Paris

Definition: Let relationships r1 and also r2 be of the same type T. Climate the expression r1 UNION r2 denotes the union the r1 and r2, and also it returns the relation of type T v body the set of every tuples t such the t appears in either or both that r1 and also r2.

 CITY London Paris

 CITY Athens

 CITY Oslo

Definition: Let relation r have an attribute called A and no attribute called B. Climate the expression r RENAME A together B return a relation with heading the same to that of r except that attribute A in the heading is renamed B, and also body the same to the of r except that all referrals to A in the body—more precisely, in tuples in the body—are replaced by references to B.

And here’s an example:

S RENAME CITY together SCITY The an outcome looks like this (it’s the same to our usual providers relation, other than that the city attribute is referred to as SCITY):

 SNO SNAME STATUS SCITY S1 Smith 20 London S2 Jones 10 Paris S3 Blake 30 Paris S4 Clark 20 London S5 Adams 30 Athens

The subexpression S RENAME SNAME as NAME return a relation basically identical come the existing value that relvar S, other than that the SNAME attribute is change the name NAME. Let’s speak to that result r1. Relation r1 is climate projected on NAME, to offer as a an outcome relation r2, say.

P PNO MINUS ( SP where SNO = "S2" ) PNO

( S CITY crossing P CITY ) UNION ns CITY

S SNO MINUS ( S SNO MINUS SP SNO )

SP MINUS SP

S intersect S

( S wherein CITY = "Paris" ) UNION ( S WHERE standing = 20 )

Q:

4.7 compose Tutorial D expressions for the complying with queries:

Q:

4.8 shot writing Tutorial D expression for part queries of your own—preferably ~ above a database that your own but, failing that, top top the suppliers-and-parts database.

Part numbers for components not provided by caterer S2.

Supplier numbers for carriers who supply at least one part.

The empty collection of shipments.

All suppliers.

Suppliers with city Paris or standing 20 or both.

4.7 The following answers aren’t the only ones possible, in general.

This expression requirements a particular amount that explanation!—though the explanation that follows is deliberately rather informal. First, note that we have here one illustration (the first we’ve seen) the the point that, in Tutorial D at least, the boolean expression in a wherein clause can, in general, be more complex than just a simple restriction condition. Second, the innermost subexpression S whereby SNO = ‘S2’ evaluate to a relationship containing just one tuple. Yet that relationship is still a relation, and what we require is not that relation as such, however rather the status value that’s included in the single tuple that’s had in that single-tuple relation. So very first we need to extract the pertinent tuple from the relation, making use of TUPLE native (which is one operator that extracts the distinctive tuple native a one-tuple relation); then we should extract the pertinent status value from the tuple, using condition FROM (in general, the operator “attribute name native t” extracts the value of the mentioned attribute indigenous the tuple denoted through the tuple expression t). The condition value so obtained—call it x—is the status value because that supplier S2, and the expression all at once thus reduces to the restriction expression S WHERE standing x.

Note: An alternate answer to this exercise is provided in footnote 14 in the ar Update operator expansions later on in the chapter.

WITH ( t1 := S wherein CITY = "Paris" , t2 := t1 SNO , t3 := SP RENAME PNO together x ) : ( P wherein ( t3 wherein x = PNO ) SNO ⊇ t2 ) PNO Again a particular amount that (deliberately informal) explanation is needed. First, v isn’t one operator together such, it’s just a syntactic trick that lets us present names because that subexpressions and also thereby enables us to see the forest and also the trees, as it were. Thus, t1 is providers in Paris; t2 is supplier number for companies in Paris; and t3 is the totality shipments relation, other than that the PNO attribute is renamed x. Then the last heat asks because that an expression the the form P wherein bx to be evaluated—in various other words, it picks the end a details subset the the components relation—and then it tasks that subset on PNO, in order to returning component numbers as desired. Together for that boolean expression bx, observe an initial that it involves a comparison between two connections (let’s contact them r1 and also r2).<36> keep in mind that those two relations are both of degree one; those more, their single attribute is the same, viz., SNO, in both cases (thus, the relationships are both that the same type). Relationship r2 is just t2; in various other words, the supplier number for carriers in Paris. Together for relationship r1: Well, i shouldn’t really refer to it together “relation r1” (as if it to be a solitary thing) in ~ all, due to the fact that actually it relies on i beg your pardon tuple that the components relation we take place to be talk about. In fact, if we think about the components tuple for part p, then r1 is efficiently the supplier numbers because that the companies who supply part p. So, because that each component p, bx is successfully asking whether the supplier number for suppliers who it is provided that component p room a superset the the supplier number for companies in Paris. Thus, bx evaluate to TRUE precisely for those components that are gave by all companies in Paris, as required.

Of course, we don’t need to use with if us don’t desire to. The complying with Tutorial D expression is logically tantamount to the one presented above:

( P whereby ( ( SP RENAME PNO as x ) where x = PNO ) SNO ⊇ ( ( S wherein CITY = "Paris" ) SNO ) ) PNO Note: SQL support a with construct too, however it’s not as useful as that is Tutorial D counterpart due to the fact that (as we’ll watch in Part III that this book) the syntactic framework of SQL doesn’t loan itself so easily to the idea that breaking large expressions down into smaller ones.

4.8 No price provided.

 SNO SNAME STATUS CITY PNO QTY S1 Smith 20 London P1 300 S1 Smith 20 London P2 200 S1 Smith 20 London P3 400 S1 Smith 20 London P4 200 S1 Smith 20 London P5 100 S1 Smith 20 London P6 100 S2 Jones 10 Paris P1 300 S2 Jones 10 Paris P2 400 S3 Blake 30 Paris P2 200 S4 Clark 20 London P2 200 S4 Clark 20 London P4 300 S4 Clark 20 London P5 400

Explanation: as the an interpretation below makes clear, join in Tutorial D space performed on the basis of common attributes. In the situation at hand, the sign up with is excellent on the basis of caterer numbers, SNO being the sole attribute the two operand relations have in common. Thus, every SP tuple t1 that has SNO value s, say, join to every S tuple t2 through that very same SNO value s, and also the result is as displayed above. (Actually, of course, there’ll be precisely one together t2 for any kind of given t1, because the sole common attribute SNO constitutes a foreign crucial in SP and also the equivalent target crucial in S. Also, keep in mind that yes no t1 at all through SNO value S5, and also so there’s no tuple because that supplier S5 in the overall result.) note too the the typical attribute SNO appears once, not twice, in the result.

Before I obtain to the definition of sign up with as such, it’s helpful to introduce the ide of joinability. Okay say connections r1 and also r2 room joinable if and also only if characteristics with the very same name are of the same type, an interpretation that in truth they’re the an extremely same attribute.<37> So right here now is the join definition (note exactly how it appeals come the fact that headings and also tuples room both sets and also can as such be activate upon by collection theory operators such as union):

 SNO SNAME STATUS CITY PNO PNAME COLOR WEIGHT S1 Smith 20 London P1 Nut Red 12.0 S1 Smith 20 London P4 Screw Red 14.0 S1 Smith 20 London P6 Cog Red 19.0 S2 Jones 10 Paris P2 Bolt Green 17.0 S2 Jones 10 Paris P5 Cam Blue 12.0 S3 Blake 30 Paris P2 Bolt Green 17.0 S3 Blake 30 Paris P5 Cam Blue 12.0 S4 Clark 20 London P1 Nut Red 12.0 S4 Clark 20 London P4 Screw Red 14.0 S4 Clark 20 London P6 Cog Red 19.0

Like union and also intersection, sign up with is commutative, associative, and also idempotent.

 SNO PNO S1 P1 S1 P2 .. .. S5 P6

As you have the right to see, this an interpretation is similar to the definition I provided for join, except that instead of requiring r1 and r2 to it is in joinable we’re currently requiring them to have actually no common attribute names. But wait a minute ... Joinable just method attributes with the very same name must be of the exact same type. But if there aren’t any type of attributes through the very same name, then this requirement is to solve trivially! (If over there aren’t any kind of attributes through the exact same name, then there definitely aren’t any type of attributes v the very same name the aren’t of the very same type.) Thus, r1 and r2 having no attribute name in typical is just a special instance of r1 and r2 being joinable, and TIMES is as such just a special case of JOIN.

Here’s one more example, because that interest. The questions is “Get SNO-PNO bag such the supplier SNO no supply component PNO.” Tutorial D formulation:

( S SNO TIMES p PNO ) MINUS SP SNO , PNO We can replace TIMES right here by sign up with without making any logical difference. In fact, times is sustained in Tutorial D largely for psychological reasons.

Aside: yes a small technical concern here. Recall the the operators of the relational algebra are supposed to type a closeup of the door system, in the sense that the result of every together operator is claimed to it is in a relation. Yet the result of the relational comparison operator is, that course, not a relation but a truth value; thus, the not totally clear the these latter operators should really be related to as part of the algebra because of this (writers differ on this point). Still, we don’t have to worry around this question; the crucial thing as far as we’re pertained to is the the operators space certainly obtainable for use once we need them. End that aside.

Note: One very common need is to have the ability to perform an “=” comparison between some provided relation r and also an empty relation of the applicable type—in various other words, a check to see whether r is empty. For this reason it’s convenient to define a shorthand:

IS_EMPTY ( r )This expression is defined to return TRUE if r is empty and also FALSE otherwise. I’ll it is in relying top top it heavily in chapters come come (especially Chapter 6). The station operator is valuable too:

IS_NOT_EMPTY ( r )This expression is logically indistinguishable to no (IS_EMPTY(r)).

( S SNO , CITY sign up with P PNO , CITY ) PNO , SNO

SP SNO I_MINUS S SNO

Q:

4.11 create Tutorial D expressions because that the following queries:

Q:

4.12 try writing Tutorial D expressions for some queries of her own—preferably on a database that your very own but, failing that, ~ above the suppliers-and-parts database.

( SP join ( S where CITY = "London" ) ) PNO

P PNO MINUS ( SP sign up with ( S wherein CITY = "London" ) ) PNO

Note: offered our normal sample data values, providers S1, for example, offers both part P1 and component P2, and also so the pair (P1,P2) shows up in the result here. Yet for precisely the same reason, therefore does the pair (P2,P1)! involved that, so does the pair (P1,P1), necessarily. We might eliminate these redundancies, if we want to, through restricting the an outcome to simply those pairs wherein PX No price provided.

See more: How New York City Became The Nation’S Greatest Commercial Center Because ?