Introduction to Relational Model/2 — Transcript

Full transcript

1. 0:00[Music]
2. 0:18welcome to module 5
3. 0:21of
4. 0:21database management systems
5. 0:24in the previous module we started
6. 0:27discussions on
7. 0:28introducing relational model
8. 0:32we will conclude that in this module
9. 0:36so in the last
10. 0:37module we have talked about attributes
11. 0:40relational
12. 0:41schemas and instances in mathematical
13. 0:44form and very importantly we have tried
14. 0:47to
15. 0:48introduce discuss about the concept of
16. 0:50keys
17. 0:52in this module we will try to understand
18. 0:55more on the relational algebra
19. 0:57and familiarize with the operations of
20. 1:00relational algebra so these are the
21. 1:02different operations that we will
22. 1:04ah look at
23. 1:06ah select project union and so on some
24. 1:08of them are simple set theoretic
25. 1:10operations some are newly defined
26. 1:12operations and we look at the
27. 1:14aggregators
28. 1:16so relational operators
29. 1:18ok so what is a relation as we have seen
30. 1:22already a relation is nothing but a
31. 1:23table
32. 1:25it has a set of columns
33. 1:27and it has a
34. 1:28set of rows or records
35. 1:31that fill up data according to those
36. 1:33columns
37. 1:35select is an operation
38. 1:38which
39. 1:39chooses
40. 1:41a
41. 1:42subset of rows from a relation
42. 1:44based on a certain condition
43. 1:47so it is written in terms of
44. 1:52in relational algebra we write it with a
45. 1:54notion of ah notation of sigma
46. 1:58and
47. 1:59following a
48. 2:00parenthesis we put the name of the
49. 2:03relation so we say we are selecting from
50. 2:07the relation r
51. 2:10and then we put a condition here
52. 2:13which is
53. 2:14a
54. 2:16propositional condition
55. 2:25so if
56. 2:27for this all rows of r
57. 2:29will be checked
58. 2:31if a row
59. 2:33will satisfy this condition
60. 2:37then it will be included in the result
61. 2:39if it does not satisfy the condition
62. 2:42then it will not be included in the
63. 2:44result
64. 2:45so let us look at this example
65. 2:48so our condition is
66. 2:52sorry let us put this back so our
67. 2:54condition theta is
68. 2:57a is equal to b
69. 2:59and
70. 3:00d is greater than five
71. 3:02so we are saying that
72. 3:04that any row to be selected
73. 3:06the value of its
74. 3:09a attribute should equal the value of
75. 3:11its b attribute
76. 3:14and when that happens
77. 3:16the value of its d attribute must be
78. 3:18greater than five
79. 3:20so we can easily if we look through this
80. 3:22we can easily say by the first condition
81. 3:24a equal to b
82. 3:25can say that this
83. 3:27row
84. 3:28does not satisfy this condition because
85. 3:31a is alpha and b is beta
86. 3:34whereas
87. 3:35these three rows
88. 3:36satisfy because a is equal to beta
89. 3:41then we again look at d
90. 3:46we find that this d is less than five so
91. 3:50we say this also
92. 3:51does not satisfy
93. 3:54because it fails the second condition
94. 3:56both have to hold
95. 3:58so we finally come to that this record
96. 4:00and this record
97. 4:02are
98. 4:03the selected record in the result
99. 4:06alpha alpha one seven alpha alpha one
100. 4:09seven beta beta twenty three ten beta
101. 4:12beta twenty three ten
102. 4:14in both of these records a is equal to b
103. 4:17in both of these records
104. 4:20d is greater than five
105. 4:22so selection is a process is a operation
106. 4:25which
107. 4:26selects a sub set of rows
108. 4:30from a table
109. 4:32from a relation
110. 4:33and creates a new relation
111. 4:35based on a selection condition that must
112. 4:38be true
113. 4:39for all the rows for all the records
114. 4:42that have been selected
115. 4:45but the set of columns do not change
116. 4:47they remain the same
117. 4:49so for example if i if ah if in the
118. 4:52contrary if we say
119. 4:53that
120. 4:55sigma
121. 4:56a
122. 4:58not equal to b r
123. 5:00then naturally i will have
124. 5:02a
125. 5:03relation
126. 5:07with fields a b c d
127. 5:09and
128. 5:12that relation will be
129. 5:14only this
130. 5:15row
131. 5:16because as the only row where a is not
132. 5:18equal to b
133. 5:23we can i can have a selection saying r
134. 5:27where
135. 5:30c is greater than zero
136. 5:35naturally this will satisfy this will
137. 5:37satisfy this will satisfy this will
138. 5:39satisfy
139. 5:41so this whole relation
140. 5:44would be the result of the selection
141. 5:47so it is possible that it is not
142. 5:48necessary that some rows will have to
143. 5:50get eliminated in the result
144. 5:53i say that
145. 5:55this is
146. 6:01is
147. 6:05the selection is d is less than one
148. 6:08this will fail this will fail this will
149. 6:11fail this will fail
150. 6:14so all of them will fail
151. 6:16so it is possible that the result of an
152. 6:18operation could be
153. 6:20either the whole relation as we saw last
154. 6:22time
155. 6:23or a null relation which has where none
156. 6:26of the records will
157. 6:27feature because none of the records
158. 6:29satisfy the condition
159. 6:32so there is a basic select operation
160. 6:35let us move on look at the next one
161. 6:39is called the projection operation so
162. 6:41select
163. 6:42chooses a subset of the rules
164. 6:45projection
165. 6:46necessarily
166. 6:48chooses projects
167. 6:52a
168. 6:53set of columns
169. 6:55from the original relation
170. 6:58so this is
171. 6:59quite straight forward to see it is
172. 7:01written in terms of
173. 7:02this notation pi
174. 7:05and then you write the
175. 7:08columns that you want in the result
176. 7:10of projection
177. 7:12so
178. 7:13you say this is a c so which means
179. 7:16basically
180. 7:18the column which is not
181. 7:20selected in the projection you can
182. 7:22simply forget about that
183. 7:24simply erase it
184. 7:25if you erase that you get
185. 7:27this
186. 7:28relation
187. 7:30and once you get that
188. 7:33please recall that a relation is a set
189. 7:36and in a set
190. 7:38every element has to be distinct
191. 7:40so after erasing b
192. 7:44this first and the second row have
193. 7:46become identical
194. 7:48so naturally
195. 7:50both of them cannot be there
196. 7:52it will have to be made distinct by
197. 7:55erasing any one of them
198. 7:57and hence
199. 7:58they become one row in the result
200. 8:04obviously i can project on
201. 8:08any of the in fields singly
202. 8:11or all the fields also i can do a
203. 8:14projection of
204. 8:16of this
205. 8:18a b c of r of course that means
206. 8:22in this case that will mean that it is a
207. 8:24set which is equal to r interval
208. 8:27but obviously
209. 8:28i must have at least one column at least
210. 8:31one attribute to project on i cannot
211. 8:33project on a null set of attributes
212. 8:35because that does not give me a schema
213. 8:38so there will have to be some
214. 8:40attribute one or more attribute on which
215. 8:43i project
216. 8:45so selection and projection
217. 8:47ah selection has given me the set of
218. 8:50rows to written and projection has given
219. 8:52me what are the columns to written in
220. 8:54the result and combining them i can do
221. 8:57several different
222. 8:58operations in a database table which can
223. 9:01give me several interesting results
224. 9:04ah before proceeding further let us look
225. 9:06into some of the
226. 9:08typical
227. 9:10other operations that relational algebra
228. 9:12allows
229. 9:13the next one is union
230. 9:15given two relations i can take a union
231. 9:17this is nothing but a set theoretic
232. 9:19union
233. 9:20the two relations r and s
234. 9:22must have the same set of columns a and
235. 9:24b
236. 9:26because if the columns are not same then
237. 9:28the union does not make sense they
238. 9:31because certainly if the columns are
239. 9:32different attributes are different
240. 9:34their types on type of data values would
241. 9:36be different so they cannot be put to a
242. 9:38same table
243. 9:39so
244. 9:40when two relations have the same set of
245. 9:42attributes
246. 9:43then their instances can be
247. 9:46taken a union of
248. 9:48so all records that
249. 9:51exist in
250. 9:53both these relations will be put
251. 9:55together into a single table
252. 9:57so here
253. 10:01alpha one is coming here
254. 10:03beta 1 is coming here
255. 10:08in terms of relation alpha 1
256. 10:10is coming here
257. 10:12alpha 2 is coming here
258. 10:15beta 1 is coming here
259. 10:18beta 3 is coming here
260. 10:21and alpha 2 is coming here you can see
261. 10:23that
262. 10:25this record alpha 2 exist in both the
263. 10:28relations
264. 10:29and
265. 10:30by the set theoretic
266. 10:33notion of uniqueness in the union
267. 10:36they have to be uniquified
268. 10:38so one of them will be removed it does
269. 10:41not matter because they are identical
270. 10:42anyway
271. 10:44so
272. 10:45for relations having
273. 10:47the same set of attributes we can simply
274. 10:49make a
275. 10:51union of all its records
276. 10:58so other the third operation is ah
277. 11:02a fourth operation is
278. 11:04doing a set difference its works simply
279. 11:07as set theoretic difference
280. 11:09again the two relations must have the
281. 11:11same set of ah
282. 11:13attributes
283. 11:14and
284. 11:15i can do a difference of
285. 11:18r minus s which mean that
286. 11:22all tuples which exist in r
287. 11:25but do not exist in s
288. 11:27will be included
289. 11:29so this is included because this is not
290. 11:33here
291. 11:34but this is not included because it is
292. 11:37in s
293. 11:39this is included
294. 11:41because
295. 11:42this is this does not exist
296. 11:45in the set s
297. 11:47so it is the set so you take the set r
298. 11:52and then
299. 11:54erase all the records
300. 11:56like this which exist in s
301. 12:00and you get r minus s so
302. 12:03if i
303. 12:04look into just to recap
304. 12:08if i look into the
305. 12:10ah venn diagram then this is
306. 12:15these are set r minus s which belongs to
307. 12:18r but does not belong to s
308. 12:22so this is a fourth operation that
309. 12:25one can do
310. 12:27with the
311. 12:29in relational algebra
312. 12:32fifth is a
313. 12:34set intersection
314. 12:36of two relations
315. 12:38so again the two relations need to have
316. 12:40the same set of attributes
317. 12:42you can take their intersection which is
318. 12:44the
319. 12:45record which belongs to
320. 12:47both
321. 12:48it is the record
322. 12:50that belongs to
323. 12:53both of them
324. 12:55and as you
325. 12:58are aware now set intersection actually
326. 13:01is not a
327. 13:02new operation
328. 13:04its not a fundamental operation because
329. 13:07if i have r if i have s
330. 13:09then
331. 13:11ah this is
332. 13:13r minus s
333. 13:16now if i subtract
334. 13:18this r minus s which is this set
335. 13:22from r
336. 13:24which is this bigger set
337. 13:27then what will be remaining
338. 13:29this is what will be remaining
339. 13:34so if i subtract r minus s from r
340. 13:37then what will remain is necessarily the
341. 13:39intersection of this is our intersection
342. 13:42s
343. 13:43so set intersection is not a fundamental
344. 13:46operation of relational algebra but
345. 13:50can be
346. 13:51used because
347. 13:52it can be expressed in terms of set
348. 13:55difference
349. 14:04next comes ah how can we join two
350. 14:06different relations which have different
351. 14:08set of
352. 14:10attributes
353. 14:11so relation r has a b
354. 14:13and relation
355. 14:15s as c d e
356. 14:16so we can take a cartesian product so
357. 14:19taking cartesian product is making all
358. 14:21possible combinations so necessarily if
359. 14:24since this has two relations and this
360. 14:26has three relations
361. 14:28so this will have
362. 14:30one two three
363. 14:32four five six seven
364. 14:34a
365. 14:35this has four relations so these are
366. 14:37eight
367. 14:39eight total all possible
368. 14:41pairing of relations of r
369. 14:44or records of r
370. 14:46and records of s are included so that is
371. 14:49a cartesian product all possible
372. 14:51combinations
373. 14:53this is ah this is how we can join two
374. 14:55relations but ah certainly
375. 14:58what is
376. 15:00important is something which we will
377. 15:02discuss shortly now in the cartesian
378. 15:05product
379. 15:06then issue may happen because ah there
380. 15:09could be attributes which are common
381. 15:11between two relations
382. 15:13so if you if two attributes are common
383. 15:15when you take cartesian product how do
384. 15:16you put their name because as with the
385. 15:19example show here between r and s the
386. 15:21attribute b is common so how do you take
387. 15:24care of that
388. 15:25so
389. 15:26when the such common names happen then
390. 15:28we actually change the name of ah
391. 15:32the attribute with the name of the
392. 15:34relation so
393. 15:36b coming from r will be called r dot b
394. 15:38and s b coming from s will be called r
395. 15:42dot s
396. 15:43and accordingly
397. 15:44the
398. 15:45relational algebra gives you a way to
399. 15:49rename
400. 15:50a
401. 15:51a a table and put its name differently
402. 15:55so this is a given
403. 15:58the
404. 15:59a
405. 16:01this is given by this relation
406. 16:04is given by this
407. 16:05symbol rho
408. 16:07so you can using a relation r
409. 16:11you can
410. 16:12actually give it a different name s
411. 16:15and ah
412. 16:17do that in terms of
413. 16:19so
414. 16:20with that you can actually because
415. 16:23otherwise you cannot compute r cross r
416. 16:26because if you try to do r cos r
417. 16:28then you will have r dot a r dot b and
418. 16:31again have r dot a r dot b
419. 16:34so you are using this to
420. 16:36rename r to s
421. 16:38and then compute this so renaming a
422. 16:40table is another feature which is
423. 16:42provided of course its not a fundamental
424. 16:45operation of the algebra but this is ah
425. 16:48what makes the any kind of cartesian
426. 16:51product possible
427. 16:54ah finally
428. 16:56we can
429. 16:57make composition of operations
430. 17:00that for example what we show here
431. 17:02is ah we have two relations r and s
432. 17:05we have taken a cartesian product and
433. 17:08then we have taken a selection
434. 17:11so taken a cartesian product of r and s
435. 17:13to produce the table as you can see the
436. 17:16r cross s and then it did a selection
437. 17:19based on a equal to c based on that
438. 17:22condition so
439. 17:23all these operations can be combined in
440. 17:25multiple different ways
441. 17:27to give you really complex relational
442. 17:30algebra operations
443. 17:34ah there is a nice
444. 17:37operation which is a derived one which
445. 17:38can be written in terms of other
446. 17:40operations
447. 17:42which is called a natural join which we
448. 17:44will use very heavily let me first
449. 17:47show you an example of that
450. 17:49ah suppose i have two relations ah
451. 17:53r and s
452. 17:55and what is important is
453. 17:57there are some attributes which are
454. 18:00common between them
455. 18:04now we saw earlier that in in
456. 18:08cartesian product in terms of common
457. 18:10attributes we basically the attributes
458. 18:12got renamed in terms of the table name
459. 18:14but this is not what we are looking at
460. 18:16in relation natural join
461. 18:18what we want to say is if
462. 18:21an attribute is common between two two
463. 18:24tables
464. 18:25then
465. 18:27while you join them
466. 18:30the records
467. 18:32from two fields can be joined if their
468. 18:35value
469. 18:37on that common attribute is same
470. 18:41so it is ah what it tries to do is
471. 18:45it tries to make
472. 18:47a cartesian product of these two tables
473. 18:50first
474. 18:51take all possible combinations
475. 18:53but then
476. 18:55you select only those rows
477. 19:00where
478. 19:01the values are identical between columns
479. 19:06having the same name
480. 19:08so for example if you if you if you look
481. 19:10into this row and this row
482. 19:14so what will happen in in the
483. 19:17cartesian product i will have
484. 19:23this
485. 19:26alpha one alpha a
486. 19:28one a alpha
487. 19:30let me write it in smaller
488. 19:33so i am doing a cartesian product i am
489. 19:35looking at this row i am looking at this
490. 19:37row so i have a b
491. 19:40c d
492. 19:41i have b d
493. 19:44e
494. 19:46and alpha
495. 19:47alpha a
496. 19:49one e alpha
497. 19:54now they match on b
498. 19:57they match on d
499. 19:59so i will say this is this will get
500. 20:01retained
501. 20:03but in the cartesian product i will also
502. 20:05have the first row
503. 20:07of
504. 20:09r going with the second row of s
505. 20:11alpha one alpha a
506. 20:14three a beta
507. 20:17here
508. 20:18the b does not match
509. 20:23d does not does match but the b does not
510. 20:26match
511. 20:30so this
512. 20:31particular entry
513. 20:34will not go in the final result
514. 20:39so you take the cartesian product
515. 20:41and
516. 20:42you only retain
517. 20:44those
518. 20:45rows where
519. 20:47the values match for the identically
520. 20:50named attribute
521. 20:53that is why so you take the artisan
522. 20:55product now look at the expression
523. 20:58the
524. 20:59attributes common attributes are b and c
525. 21:02b and d
526. 21:04so the b attribute is r dot b
527. 21:07and
528. 21:08s dot b so we say that in the cartesian
529. 21:11product
530. 21:12r dot b must equal s dot b
531. 21:15the name is common the value will have
532. 21:16to be same further
533. 21:19similarly d is a common attribute so r
534. 21:22dot d value in the r dot d and the value
535. 21:24in the s dot d has to be same
536. 21:27so based on the
537. 21:29cartesian product
538. 21:31you do a selection
539. 21:33for equality of values on
540. 21:37attributes which are identical between
541. 21:40the two between the two relations
542. 21:43between the two tables
543. 21:45this is the final selection
544. 21:48as you do that
545. 21:52you get a table where there are two b's
546. 21:54r dot b s dot b
547. 21:56there are two d's r dot d s dot d
548. 21:59but according to this selection
549. 22:01for all at all records for all rows
550. 22:06the value on r dot b and value on s dot
551. 22:08b are same
552. 22:10value on r dot d and value on r s dot d
553. 22:13are same because that is how we have
554. 22:14done the selection
555. 22:16so there is no
556. 22:18reason to keep two b columns or two d
557. 22:22columns
558. 22:23so now you project
559. 22:26based on a
560. 22:28r dot b c r dot d and e which means that
561. 22:32s dot b
562. 22:34and s dot d
563. 22:36are left out
564. 22:38you do not project them
565. 22:41so after
566. 22:43you have done this projection
567. 22:46you get the final result of the natural
568. 22:48join
569. 22:49which has
570. 22:51a union of all the attributes that the
571. 22:54two relations at abcd
572. 22:56and bde union is abcde
573. 23:00and you have all those records
574. 23:05whose
575. 23:07values matched
576. 23:09on the common attributes between
577. 23:11relation r and relation d
578. 23:13so you can say that if i now do a
579. 23:15selection if i now do a projection on a
580. 23:18b c
581. 23:20or rather a b c d
582. 23:22i will get a subset of r
583. 23:24if i do a
584. 23:26projection on b d e
585. 23:28i will get a subset of s
586. 23:31so this is the natural join operation in
587. 23:34relational algebra as you can see this
588. 23:35is a derived operation
589. 23:37because we could use the
590. 23:40cartesian product selection and
591. 23:42projection to get this but
592. 23:44as i tell you we will see see more of
593. 23:46this when we look at
594. 23:49the ah look at all these different
595. 23:52query coding but natural join is one of
596. 23:55the most
597. 23:56widely used most fundamental relational
598. 23:59algebra operation that you will often
599. 24:01need beyond selection and projection so
600. 24:04these were the six ah operations and the
601. 24:07important derived operations of
602. 24:09relational algebra besides that
603. 24:11relational algebra has some aggregation
604. 24:13operators
605. 24:15for example ah given a table we could
606. 24:19compute the sum of values on a column we
607. 24:21could compute average of values max of
608. 24:23values mean of values
609. 24:25so these somehow aggregate
610. 24:27values of multiple rows on a particular
611. 24:30column
612. 24:32and therefore these are called aggregate
613. 24:34operators ah
614. 24:36we will see when we talk about sql we
615. 24:39will see how these really can be coded
616. 24:41in sql and used but these are these
617. 24:45become very convenient to use because
618. 24:47often we will need to know k if this is
619. 24:50ah
620. 24:50i mean ah these are the instructors and
621. 24:53so let us see which instructor has a
622. 24:55maximum load of courses how many based
623. 24:59on hours or
624. 25:01which instructor has what is the average
625. 25:03load on the different instructors and so
626. 25:06on so in every possible context
627. 25:08different aggregate operators are
628. 25:09frequently required and they are also
629. 25:11available as operators in most of the
630. 25:14pure as well as commercial query
631. 25:16languages
632. 25:19ah finally to note
633. 25:21that
634. 25:22relational algebra in relational average
635. 25:25every query input is a table
636. 25:28and the output is also a table
637. 25:32so it is always manipulating one or more
638. 25:34tables into a single table that
639. 25:37what we are i mean
640. 25:38in very simple terms thats a way you can
641. 25:40look at it and all data in the output
642. 25:43table appears in
643. 25:45one of the input tables that is no new
644. 25:47data gets generated
645. 25:49it is basically
646. 25:51taking
647. 25:53selecting
648. 25:54combining data from different input
649. 25:56tables it does not generate a new data
650. 25:59that that has to be that is ah if if i
651. 26:02see that a v
652. 26:04an attribute for a particular row has a
653. 26:07value 15
654. 26:08then there must be some input table
655. 26:10where there is a record where in that
656. 26:13field there is an attribute value 50.
657. 26:15otherwise this cannot happen
658. 26:18again relational algebra is not turing
659. 26:20complete in the sense that there are
660. 26:22algorithms which cannot be coded in
661. 26:24relational algebra
662. 26:26we mentioned this earlier too
663. 26:28and
664. 26:29that is the reason that is a
665. 26:30foundational reason of why
666. 26:33the sql language commercial sql language
667. 26:35which is based on relational algebra is
668. 26:37not turing complete either
669. 26:39so we might need to use other
670. 26:41programming languages along with the
671. 26:43relational algebra coding
672. 26:45for solving some of the application
673. 26:47problems
674. 26:49to summarize this is the
675. 26:52so this table is what you not only
676. 26:54should remember but you should become an
677. 26:56expert of
678. 26:57in terms of the operators of relational
679. 26:59algebra which we will start using very
680. 27:01heavily
681. 27:03as we start doing the query coding and
682. 27:05processing
683. 27:06so we talked about selection which takes
684. 27:08rows selectively talked about projection
685. 27:11which takes out certain columns of a
686. 27:13table
687. 27:14we talked about cartesian product of two
688. 27:17relations which make all possible
689. 27:19combined relations
690. 27:21we talked about union of
691. 27:24records from two tables having identical
692. 27:26set of attributes
693. 27:28we talked about set difference
694. 27:31which again is ah the
695. 27:34difference of records
696. 27:37of one relation from another
697. 27:40given that they have identical
698. 27:42set of attributes
699. 27:44we have shown that set difference can be
700. 27:46used to also
701. 27:48compute set intersection so its not in
702. 27:51the fundamental operation but is the
703. 27:53derived one
704. 27:54and we have shown a very interesting ah
705. 27:56operation based on cartesian product
706. 27:59selection and projection called natural
707. 28:02join where two tables can be joined
708. 28:04based on
709. 28:06one or more common attributes they have
710. 28:08now i am sure you have already noted
711. 28:11that if i am doing a natural join
712. 28:13between two tables which do not have any
713. 28:16common attribute then the result is
714. 28:18merely the cartesian product because the
715. 28:21selection around the cartesian product
716. 28:22has no condition to select
717. 28:24any
718. 28:26ah any of the
719. 28:28you know any of the fields any of the
720. 28:30rows separately so it merely turns out
721. 28:33to be a cartesian product
722. 28:39so in this module we have introduced the
723. 28:41relational algebra and we have
724. 28:44familiarized ourselves with the
725. 28:47fundamental and derived operators of
726. 28:50relational algebra
727. 28:51ah going forward in the next module will
728. 28:55take a deeper look into the relational
729. 28:57model and start progressing towards the
730. 29:01query design and database design