4) Using SQL and Relational Algebra (ungraded!!)a) Give relational algebra expressions and SQL-queries for the following queries that involve the boats/sailors/reservation relations that are explained in our textbook:Dr. Christoph F. EickHomework1 COSC 6340Spring 2005Available Points: 45Due: Problems 1-3 are due Tu., Feb. 22 in class. Handwritten solutions will not be accepted!Last updated: Feb. 17, 2005, 1:15p1) Mapping E/R to a Relational Database Schema [15]Take the Hotel-Reservation E/R diagram from the “Designing E/R Diagrams” teachingmaterial and map it using Dr. Eick’s mapping to a Relational Schema. Define therelations generated by this mapping in proper SQL-syntax. Also specify necessaryprimary keys and foreign keys and all uniqueness constraints.2) Physical Database Design [15]Assume a relation R(A, B, C) is given; R is stored as an unordered file1 and contains1000000 (1 million) tuples. Attributes A, B and C need 4 byte of storage each, and blockshave a size of 4096 Byte. Attribute A is a candidate key. Moreover, we assume that statichashing is used to implement index structures, and that index pointers require 4 byte ofstorage; furthermore, you can assume that pages of index blocks are 80% full and do notcontain any overflow pages); each B-value occurs at an average 10000 times in thedatabase and each C value occurs 10 times in the database. What index structures wouldyou create to speed up the following 4 SQL statements (value is a placeholder for aninteger constant)?S1: Select A, C S2: Delete S3: Select sum(R.A) S4: Insert from R from R from R into R where B=value; where C=value values (3,4,5) returns 10000 answers deletes 10 tuples returns one answer inserts 1 tupleDescribe which index structures you would create (justify your design!) trying tominimize the sum of the cost of executing the four sql-statements; indicate for eachstatement how you would implement it and give the cost for your chosen implementationplan (in number of block accesses including the formula you used to compute the cost).1 You can assume that the blocks of the heap-file are 100% filled13) B+ Trees [15]a) Assume an entry is deleted from a B+-tree of height 2 (that is, it has a root anintermediate layer and a leaf layer). Also assume with each node of the B+-treecorresponds to one block on the disk. How many different blocks have to be accessed(using read or write) in the worst case to perform this deletion? Give reasons for youranswer! [3]b) B+-trees are very popular for implementing index structures. Why is this the case?What properties of B+ trees make them a good choice for implementing index structures?[3]c) Assume the tuples of a relation R(A,B,C) are stored in a B+-tree using attribute C asthe search key with m=400 and p=300 of height 3 (one root, 2 more intermediate layer,one leaf layer) with each node of the tree corresponding to one block on the disk.Moreover, the following query Q1 is given that returns 2000 answers: Select A from R where C < 5523 and C > 2345How would you implement Q1 trying to take advantage of the B+-tree? Also compute thenumber of block accesses of the best implementation of the query as precisely aspossible, and explain your computations! [6]d) Assume that the following B+-tree with p=5 and m=3 is given. Furthermore, assumethat the keys 1, 21, 24, 99, 34, 35 are deleted in the indicated order. Show how the treelooks like after each deletion. [3]23521 2440 43 551 2123 2431 34 3539 4042 4351 5566 994) Using SQL and Relational Algebra (ungraded!!)a) Give relational algebra expressions and SQL-queries for the following queries that involve the boats/sailors/reservation relations that are explained in our textbook:1. Give the sid of all sailors that have a reservation for 10/13/2003 but not for 10/17/2003.2. Give the name and sid of all sailors that have reservations for all red boats3. Give the name and sid of all sailors that have exactly one reservation for 11/11/20031. (sid (day=10/13/2003(Reserves)) (sid ( day=10/17/2003(Reserves))2. sid ((sid,bid(Reserves)) ( bid(color=red(Boats))) |X| Sailor)3.a. r(Reserves2, (1àsid2,2àbid2, 3àday2), sday=11/11/2003 (Reserves))b. r(2+R, (psid(sday=11/11/2003(Reserves)) |X|sid=sid2 and bid¹bid2 Reserves2))c. psid,sname((psid(Reserves) ¾ 2+R) |X| Sailors))Remark: SQL Solution to Problems 2 is not relevant for Exam0 2005!!Solution Problem a3 for SQL:SELECT S.sid, S.snameFROM Sailors S, Reserves RWHERE S.sid=R.sid AND R.day=’11/11/2003’ AND NOT EXISTS (SELECT R1.sid FROM Reserves R1 WHERE R1.sid=R.sid AND not(R1.bid=R.bid))b) Write an SQL-query (or a sequence of SQL queries) that computes the sids of all sailorthat have a reservation for all except one boat (e.g. if there are 12 boats those sailors that have at least one reservation for 11 different of those boats should be returned, but neitherthe sailors that have reservation for all the boats nor the sailors that have reservations for less than 11 different boats should be returned).