Closed Access

#### Database Management Systems IITR 2018

The aim of this course is to introduce the concepts of database management systems and the design of relational databases. Few advanced topics on database management systems are also covered in this course.
113 Members
##### The Alipore Zoo has many types of animals. Every type has a unique nam...
The Alipore Zoo has many types of animals. Every type has a unique name. Every animal of the same type has a unique animal ID. Animals in two types may have the same animal ID. Animals also have age and gender. Animals may have diseases. The beginning time and the duration of a disease need to be recorded. A disease has a unique name.

A type keeper takes care of only one type of animals. Every type may have many type keepers. A type keeper may or may not be familiar with diseases. But every disease must be handled by at least one type
keeper. Type keepers have name, employee ID, ssn, address and phone number.

All animals are in cages. Some cage may be empty. Every cage has a cage ID, space and height. A cage keeper may take care of many cages. Every non-empty cage must have at least one cage keeper. Empty cages don’t need any cage keepers. Cage keepers have name, employee ID, ssn, address and phone number.

(a) Model the entities and relationships (including attributes and constraints of relationships) described above in an ER-diagram. Write down any assumptions you make.

(b) Design the schema diagram (clearly showing the relation schemas and the foreign key connections) for this database.

Answer will be updated soon. You are encouraged to solve on your own and discuss the solution in the comments.
lee
17 Sep 2019 03:17 pm
islam
23 Apr 2020 02:55 am
Exercise 19.8 Answer each of the following questions briefly. The questions are based on
the following relational schema:
Emp(eid: integer, ename: string, age: integer, salary: real, did: integer)
Dept(did: integer, dname: string, floor: integer)
and on the following update command:
replace (salary = 1.1 * EMP.salary) where EMP.ename = ‘Santa’
1. Give an example of a query that would conflict with this command (in a concurrency
control sense) if both were run at the same time. Explain what could go wrong, and how
locking tuples would solve the problem.
2. Give an example of a query or a command that would conflict with this command, such
that the conflict could not be resolved by just locking individual tuples or pages, but
requires index locking.
3. Explain what index locking is and how it resolves the preceding conflict
##### Recently, Bob the Builder coded up a Relational Query Language Transla...

Recently, Bob the Builder coded up a Relational Query Language Translator (RQLT). The RQLT is simple and only operates on a single schema as given below:
Tool(tid, brand, cost)
Toolbox(tbid, location)
Holds(tbid, tid

(a) Bob sets the RQLT to translate the following SQL query to Relational Algebra:
SELECT T.tid
FROM Tool T, Holds H, Toolbox B, Jobsite J
WHERE T.tid = H.tid AND H.tbid = B.tbid
AND B.location = J.location AND J.task = `Plumbing'}
What will be the equivalent Relational Algebra query?

(b) Bob switches the RQLT to translate Relational Algebra into Tuple Relational Calculus and passes in:

What will be the equivalent Tuple Relational Calculus Query?

(c) Bob then translates the following Tuple Relational Calculus query:

What will be the equivalent SQL Query?

*Point out if you find some mistake.

Vinayak Aggarwal
23 Nov 2018 09:37 am
In a), don't we have exactly replicate the query? I mean the SQL query wants to find the Cartesian product and then reduce the output table based on the given conditions.
Ranita Biswas
25 Nov 2018 10:59 am
No need to replicate, you just need to find equivalent which means producing same result on same database instance.
##### Consider the following B+ tree index of order 3:(a) Assume we ...

Consider the following B+ tree index of order 3:

(a) Assume we modify the B+ tree by adding the following keys in the

following order: 20, 27, 18, 30, 19. Show every steps to insert these five key values one after another into the initial tree. Assume that we split up a node after insertion of the new element, and the left node gets one more than the right.

(b) Suppose we were to insert all integers in the range 26 to 4112 inclusive (i.e. 26, 27, 28 ... , 4111, 4112) into the initial tree given in the figure, one at a time. At most how many levels would the resulting B+-tree have? (Hint: You should not need to draw a B+-tree to figure this out!)

*Point out if you find some  mistake.

Harsh Jain
23 Nov 2018 04:43 pm
Ma'am, in part (b) I considered level of a tree with single node as 1 which gave me the answer 12 levels
Sakshi Goyal
25 Nov 2018 03:05 am
I have done the same, Ma'am.
Ranita Biswas
25 Nov 2018 10:57 am
It’s absolutely fine. In fact it’s 0th level to 11th, so count is 12.
##### (a) Your cousin, who is studying at a Bay Area university often noted ...

(a) Your cousin, who is studying at a Bay Area university often noted for its sports programs, claims to have learned "Lance's Axioms" for reasoning about Functional Dependencies. He claims that one such axiom, is
Reversitivity: if A → B then B → A
Give an example relation instance that proves that Reversitivity is invalid. (for simplicity, use integers and/or single letters as your attribute values)

(b) After viewing your counterexample for part (a), your cousin launches into a review of the final scores of the "Big Game" over the past decade. He then claims that there is another axiom:
Kindatransitivity: if A → C and AB → C then B → C
Give an example relation instance that proves that Kindatransitivity is invalid.

(c) It turns out however, that your cousin almost got it right. In fact, there is a rule as follows:
Pseudotransitivity: if A → B and BC → D then AC → D
Show that Pseudotransitivity is in fact valid. Be sure to show the steps for your derivation.

(d) Why can't you use an example relation instance to answer part (c), as you did for parts (a) and (b) of this question?

(e) Consider the relation schema R(ABCDE) and the following functional dependencies on R: A → D, BC → E, D → AB
What are the candidate keys of R and what is the highest normal form of R. Explain.

*Point out if you find some mistake.

##### Consider the attributes A B C D E F G which have the following functio...

Consider the attributes A B C D E F G which have the following functional dependencies: AD → F, AE → G, DF → BC, E → C, G → E

(a) List all the candidate keys (not superkeys).

(b) Which of the following dependencies are implied by those above: G → C, A → G, ADF → E, ADC → B, AGF → E

(c) Consider the decomposition into 4 relations: (ADF) (CE) (EG) (ABDG). What is the highest normal form of this decomposition? Is this decomposition dependency preserving? Is it lossless? Justify your answer.

(d) Consider the decomposition into 3 relations: (ADF) (EC) (ABDEG). What is the highest normal form of this decomposition? Is this decomposition dependency preserving? Is it lossless? Justify your answer.

*Point out if you find any mistake.

DIVYANSHU SAXENA
21 Nov 2018 02:26 pm
b) only these two FDs implied: ADC → B, AGF → E
c) (ADF) is in BCNF; (CE) is also in BCNF; (EG) is in
BCNF and(ABDG) is in 2NF as here partial
dependency exist.
It is lossless but not dependency preserving
Vinayak Aggarwal
22 Nov 2018 08:42 pm
For the c part, if you consider the closure of the dependencies given, then AD determine B (which is not fully functional dependent on the key ADG) hence ABDG should be in 1NF.
##### Draw an E-R diagram for the following situation: - This is a simplifi...
Draw an E-R diagram for the following situation:
- This is a simplified model for reserving baseball tickets.
- There are teams, which are identified by the team name. Teams are also located in a city.
- Teams play with each other in games, which occur on a particular date at a particular time. Games are identified by a game ID, and each game has exactly two teams that play in it.
- A game is played in exactly one stadium.
- A stadium is identified by its name, and is also located in a city.
- Stadiums have seats, which have a section number, a row number, and a seat number.
- Ticket holders reserve seats for a game. Ticket holders are identified by their name.
- Some ticket holders are students (students get discounts, but we are not including that in the model).
Using SQL, convert your designed ER diagram to the relational model.
Discuss the solution in the comments section.
##### Consider the following relational schemas:DEPT(dname, location)STU...

Consider the following relational schemas:
DEPT(dname, location)
STUDENT(name,regno,gpa,level,dept)
COURSE(cno,cname,dept)
TAKE(regno,cno)

Write down the relational algebra (RA) and tuple relational calculus (TRC) for the following queries.

(a) The names of the students who take exactly the same courses as Rosie takes.

(b) The names and departments of the students who take the largest number of courses among students in their departments. Students without a department should not be considered.

(c)

Vipul Jain
19 Nov 2018 06:03 pm
Ranita Biswas
19 Nov 2018 07:06 pm
Samagra Sharma
20 Nov 2018 09:13 am

@ranita mam. The first solution(TRC) seems a bit incorrect. It will give me all those students whose courses are a superset of Rosie's courses. I guess a bi-implication is required for the "exactly same" clause.

Ranita Biswas
20 Nov 2018 09:39 am
Thanks Samagra. Yes, you are right! I completely ignored the exactly same part. Replacing the implication by double implication will serve the purpose.
Ranita Biswas
20 Nov 2018 09:45 am
And v should also have forall clause I think. And in the RA, we should go with subtraction, rather than division.
Samagra Sharma
20 Nov 2018 10:46 am
Yes mam. Division will have extra tuples

I am not clear where $\forall$ should come.
I guess I am missing something.

Ranita Biswas
20 Nov 2018 10:52 am
For single implication as we were taking forall the courses taken by Rosie, similarly while using double implication, we should consider forall the courses taken by the other student.
Samagra Sharma
20 Nov 2018 11:08 am

Ohh Okay. Thanks a lot mam. There are a lot of subtleties.

Ranita Biswas
20 Nov 2018 11:32 am
Yes, indeed there is. I am teaching this for last 3 years, and still get confused a lot.
##### Consider the following relational schemas:employee(person-name, st...

Consider the following relational schemas:
employee(person-name, street, city)
works(person-name, company-name, salary)
company(company-name, city)
manages(person-name, manager-name)
Write down the relational algebra (RA) and tuple relational calculus (TRC) for the following queries.

(a) Find the names of all employees who live in the same city and on the same street as do their managers.

(b) Find the names of all employees in this database who do not work for State Bank of India. Assume that there may be information in the database about people who do not work for any company right now.

(c) Assume the companies may be located in several cities. Find all companies located in every city in which HDFC Bank is located.

VEMULA SAI SRI VATHSA
19 Nov 2018 01:34 pm
Ranita Biswas
19 Nov 2018 01:52 pm
Yes, let me check and update the marks first; then I will upload the answers, by 8pm or so it should be done. Will notify.
Vipul Jain
19 Nov 2018 06:00 pm
Vipul Jain
19 Nov 2018 06:01 pm
Nitin Sethi
19 Nov 2018 06:24 pm
Is there a symbol for not equal to in RA, RTC?
Samagra Sharma
19 Nov 2018 09:22 pm
Yes, you can use $\neq$ in both of them.
Ranita Biswas
19 Nov 2018 07:05 pm
Ranita Biswas
19 Nov 2018 10:18 pm
Nitin, use ~ to represent negation in both RA and TRC.
Vipul Jain
20 Nov 2018 10:54 am
@ranita mam, in RA of part(b), when we take left outer join, then we would have NULL values for the cname attribute if an employee doesn't work for any company. So when select operation condition is applied on the cname which basically compares cname <> "SBI", the value returned for NULL values would be NULL, then on what basis they would be selected?
Ranita Biswas
20 Nov 2018 11:01 am
NULL is not equal to ‘SBI’, so the tuples having NULL in cname should be selected.
Samagra Sharma
20 Nov 2018 11:11 am
@ranita mam. Refering to page number 83 in Silberschatz if we try to calculate (NULL == 'SBI'). The answer is unknown(Third logical value) and not false.
Ranita Biswas
20 Nov 2018 11:26 am
Yes, to implement this in SQL, you must use "cname <> 'SBI' or cname IS NULL" in the where clause. However, as RA is a theoretical concept, we do write "a = NULL" or "a <> NULL" in RA SELECT clauses, which also does not produce correct result if used in SQL where clause.
Samagra Sharma
20 Nov 2018 11:29 am
Thanks Mam
Samagra Sharma
20 Nov 2018 11:24 am
https://en.wikipedia.org/wiki/Null_(SQL)#Comparisons_with_NULL_and_the_three-valued_logic_.283VL.29

Mam please have a look. Should we use the Codd's appproach or the normal one used in programming languages?

Ranita Biswas
20 Nov 2018 11:30 am
As SQL provides you with the separate notion of handling NULL values using "IS NULL", "IS NOT NULL" etc. you should be using that. However, it's not mandatory to go into this trouble while using RA or TRC. They are theoretical languages, and their implementation can be handled separately while doing so in SQL.
##### The following functional dependencies hold for relations R(A,B,C) and ...

The following functional dependencies hold for relations R(A,B,C) and S(B,D,E): B → A, and A → C. The relation R contains 200 tuples and the relation S contains 100 tuples. What is the maximum number of tuples possible in the natural join R ⋈ S? Explain.

B is the candidate key for R and R ∩ S = {B}. As R contains 200 tuples and S contains 100 tuples, for each tuple of S, there can be atmost 1 tuple in R. Hence, R ⋈ S will contain a maximum of 100 tuples.

Sachin Jain
20 Nov 2018 05:42 am
Are we assuming that all tuples are distinct? Do we ignore duplicate tuples while taking natural join?
Ranita Biswas
20 Nov 2018 08:11 am
We assume relations by default have distinct tuples. If R and S both have distinct tuple, their natural join will also produce distinct tuples in this case.
##### The following B+ Tree has order 3. Answer each of the following questi...

The following B+ Tree has order 3. Answer each of the following questions independently of each other.

(a) What value(s) would be in the root node if we were to insert 0?

(b) What value(s) would be in the root node if we were to insert 6?

(c) Starting with the height 2 tree in the picture above, suppose we start inserting keys 6, 7, 8, … and so on. After inserting what key will the height of the tree become 4?

(a) 0 will be inserted in the leaf node containing 1, and hence, no change will be there in the root node. Root node will contain values (2, 4).

(b) 6 will be inserted in the leaf node containing (4, 5), and hence splitting of node with 5 getting copied in the root node, which splits again resulting in a new root containing only 4.

(c) Insertion of 14 should make the tree reach height 4 if we split the nodes reaching 3 values in 2:1. On the other hand, insertion of 10 should make the tree reach height 4 if we split the nodes reaching 3 values in 1:2. The second case is the solution followed by the standard algorithm given in wikipedia. A step-by-step analysis can be done to prove this value and is required to complete the answer.

Akshat Arora
18 Nov 2018 08:06 pm
maam, my answer for part c) is coming 14. Can you please upload the solution for this part?
Ranita Biswas
19 Nov 2018 10:43 am
Yes, the answer to part (c) will be 14 if you use split after insertion, and will be 10 if you split before insertion. Note that in a real scenario, the second approach is preferred. 16 was obtained by using value sharing with siblings, which is incorrect and not used during insertion algorithm. I will correct it.
Vipul Jain
19 Nov 2018 11:36 am
Ma'am, in Silberschatz book, it's written that we allow leaf nodes to contain as few as ceil( (n-1)/2 ) values while in slides it's written ceil(n/2) -1. Which value should we consider while solving questions?
No Body
20 Nov 2018 06:46 am
both give same result
Ranita Biswas
19 Nov 2018 11:52 am
Min no of pointers = ceil(n/2), No of key values is one less than the no of pointers. So, min no of key values = ceil(n/2) - 1. There are many different conventions for these things. Stick with any one, and to avoid confusion, mention the rule you are following. The rule should ensure similar performance/complexity compared to other standard methods.