Final Examination Notes | EduRev

Created by: Dheeraj Singla

: Final Examination Notes | EduRev

 Page 1


Name:
CSEP 544, Spring 2009, Final Examination
Take-home Exam
June 2-4, 2009
Rules
• Open books, open notes, access to the computer.
• No communication/collaborations allowed with your colleagues.
• Questions ? Send email to Dan Suciu and cc’ Bhushan Mandhani.
• Posted: Tuesday, June 2nd, 9:30pm.
• Return by: Thursday, June 4th, 11:59pm.
• Dropbox:https://catalysttools.washington.edu/collectit/dropbox/bhushan/5598
• What to turn in: text ?le, or Word ?le.
• WRITE YOUR NAME !
Question Max Grade
1 25
2 15
3 20
4 10
5 20
6 10
Total 100
1
Page 2


Name:
CSEP 544, Spring 2009, Final Examination
Take-home Exam
June 2-4, 2009
Rules
• Open books, open notes, access to the computer.
• No communication/collaborations allowed with your colleagues.
• Questions ? Send email to Dan Suciu and cc’ Bhushan Mandhani.
• Posted: Tuesday, June 2nd, 9:30pm.
• Return by: Thursday, June 4th, 11:59pm.
• Dropbox:https://catalysttools.washington.edu/collectit/dropbox/bhushan/5598
• What to turn in: text ?le, or Word ?le.
• WRITE YOUR NAME !
Question Max Grade
1 25
2 15
3 20
4 10
5 20
6 10
Total 100
1
Name:
1. (25 points) Relational Model A large IT corporation stores their access control policy to their
objects in a database with the following schema:
User(uid, uname) /* all the users */
Group(gid, gname) /* all the groups */
Member(uid, gid) /* users belong to groups (many-many) */
Object(oid, oname) /* all the objects */
AccessGranted(gid, oid) /* access to an object is granted on a per group basis */
AccessDenied(uid, oid) /* access is denied on a per user basis; overrides AccessGranted */
AccessLog(uid, oid, t) /* logs whenever a user accesses an objectq; t=timestamp */
Thesepoliciesareenforcedintheapplications,whichhavetoreadthedatabasetodetermineifarequest
to an object should be granted or denied, then proceed accordingly. Grant policies are group-based:
that is, an entire group is granted access to an object. Deny policies are user based: a particular user
may be denied access to an object, even if the user belongs to a group that has access to the object.
For auditing purposes, every time an object is accessed by a user, the system logs an entry into the
AccessLog table.
(a) Describe the SQL schema and the constraints for this data. You have to turn in seven CREATE
TABLE statements that contain the primary key and the foreign key constraints. All user ids,
groupids, objectids, andthetimestampsareintegers; allotherattributesare VARCHAR(n), where
you can choose a suitable value for n.
(b) Write a SQL query that computes the total number of distinct objects accessed by the system, in
a sliding window of width 10. That is, your query should report pairs (t, count) where count
represents the number of distinct objects accessed during the timestamps t...t+9.
(c) Write a SQL query that checks if any of the accesses recorded in AccessLog were illegal. Your
query should return all illegal accesses, i.e. accesses where the user uid was not permitted to
access the object oid.
2
Page 3


Name:
CSEP 544, Spring 2009, Final Examination
Take-home Exam
June 2-4, 2009
Rules
• Open books, open notes, access to the computer.
• No communication/collaborations allowed with your colleagues.
• Questions ? Send email to Dan Suciu and cc’ Bhushan Mandhani.
• Posted: Tuesday, June 2nd, 9:30pm.
• Return by: Thursday, June 4th, 11:59pm.
• Dropbox:https://catalysttools.washington.edu/collectit/dropbox/bhushan/5598
• What to turn in: text ?le, or Word ?le.
• WRITE YOUR NAME !
Question Max Grade
1 25
2 15
3 20
4 10
5 20
6 10
Total 100
1
Name:
1. (25 points) Relational Model A large IT corporation stores their access control policy to their
objects in a database with the following schema:
User(uid, uname) /* all the users */
Group(gid, gname) /* all the groups */
Member(uid, gid) /* users belong to groups (many-many) */
Object(oid, oname) /* all the objects */
AccessGranted(gid, oid) /* access to an object is granted on a per group basis */
AccessDenied(uid, oid) /* access is denied on a per user basis; overrides AccessGranted */
AccessLog(uid, oid, t) /* logs whenever a user accesses an objectq; t=timestamp */
Thesepoliciesareenforcedintheapplications,whichhavetoreadthedatabasetodetermineifarequest
to an object should be granted or denied, then proceed accordingly. Grant policies are group-based:
that is, an entire group is granted access to an object. Deny policies are user based: a particular user
may be denied access to an object, even if the user belongs to a group that has access to the object.
For auditing purposes, every time an object is accessed by a user, the system logs an entry into the
AccessLog table.
(a) Describe the SQL schema and the constraints for this data. You have to turn in seven CREATE
TABLE statements that contain the primary key and the foreign key constraints. All user ids,
groupids, objectids, andthetimestampsareintegers; allotherattributesare VARCHAR(n), where
you can choose a suitable value for n.
(b) Write a SQL query that computes the total number of distinct objects accessed by the system, in
a sliding window of width 10. That is, your query should report pairs (t, count) where count
represents the number of distinct objects accessed during the timestamps t...t+9.
(c) Write a SQL query that checks if any of the accesses recorded in AccessLog were illegal. Your
query should return all illegal accesses, i.e. accesses where the user uid was not permitted to
access the object oid.
2
(d) A group is called useless if all the access grant permissions given through that group are over-
ridden by a access deny entry. That is, the group is useless if for every member U of that group
and for every object O to whom that group is being granted access, there is an entry (U,O) in
AccessDenied: it means that the group is not useful in granting any access at all, since all the
accesses are overridden in the AccessDenied table. Write a SQL query to ?nd all useless groups.
3
Page 4


Name:
CSEP 544, Spring 2009, Final Examination
Take-home Exam
June 2-4, 2009
Rules
• Open books, open notes, access to the computer.
• No communication/collaborations allowed with your colleagues.
• Questions ? Send email to Dan Suciu and cc’ Bhushan Mandhani.
• Posted: Tuesday, June 2nd, 9:30pm.
• Return by: Thursday, June 4th, 11:59pm.
• Dropbox:https://catalysttools.washington.edu/collectit/dropbox/bhushan/5598
• What to turn in: text ?le, or Word ?le.
• WRITE YOUR NAME !
Question Max Grade
1 25
2 15
3 20
4 10
5 20
6 10
Total 100
1
Name:
1. (25 points) Relational Model A large IT corporation stores their access control policy to their
objects in a database with the following schema:
User(uid, uname) /* all the users */
Group(gid, gname) /* all the groups */
Member(uid, gid) /* users belong to groups (many-many) */
Object(oid, oname) /* all the objects */
AccessGranted(gid, oid) /* access to an object is granted on a per group basis */
AccessDenied(uid, oid) /* access is denied on a per user basis; overrides AccessGranted */
AccessLog(uid, oid, t) /* logs whenever a user accesses an objectq; t=timestamp */
Thesepoliciesareenforcedintheapplications,whichhavetoreadthedatabasetodetermineifarequest
to an object should be granted or denied, then proceed accordingly. Grant policies are group-based:
that is, an entire group is granted access to an object. Deny policies are user based: a particular user
may be denied access to an object, even if the user belongs to a group that has access to the object.
For auditing purposes, every time an object is accessed by a user, the system logs an entry into the
AccessLog table.
(a) Describe the SQL schema and the constraints for this data. You have to turn in seven CREATE
TABLE statements that contain the primary key and the foreign key constraints. All user ids,
groupids, objectids, andthetimestampsareintegers; allotherattributesare VARCHAR(n), where
you can choose a suitable value for n.
(b) Write a SQL query that computes the total number of distinct objects accessed by the system, in
a sliding window of width 10. That is, your query should report pairs (t, count) where count
represents the number of distinct objects accessed during the timestamps t...t+9.
(c) Write a SQL query that checks if any of the accesses recorded in AccessLog were illegal. Your
query should return all illegal accesses, i.e. accesses where the user uid was not permitted to
access the object oid.
2
(d) A group is called useless if all the access grant permissions given through that group are over-
ridden by a access deny entry. That is, the group is useless if for every member U of that group
and for every object O to whom that group is being granted access, there is an entry (U,O) in
AccessDenied: it means that the group is not useful in granting any access at all, since all the
accesses are overridden in the AccessDenied table. Write a SQL query to ?nd all useless groups.
3
2. (15 points) Functional Dependencies and Database Design
(a) Consider the following three relations, their attributes, and their keys:
R(A,B,C)
S(D,E)
T(F,G,H)
For each of the viewsV
1
,...,V
5
below indicate their attributes, and list a set of functional depen-
dencies (FDs) such that all the FDs that hold in the view can be inferred from these.
V
1
= R1
B=D
S
V
2
= S1
E=G
T
V
3
= s
H=55
(T)
V
4
= ?
AB
(R)
V
5
= ?
H,sum(G) as K
(T)
For example, your answer could look as follows:
V
9
(A,B,D,F,G) AB?DFG; F ?B
(b) Consider a table R(A,B,C,D,E,F) and the following functional dependencies:
BC ? A
BDE ? F
EF ? B
Compute a BCNF representation of R. Explain your steps.
(c) The MomPopDairy Company has a database with a single table:
Orders(customerID, customerName, customerAddress, milkQuantity, date)
Intheircurrentoperation,everytimeacustomercallstoplaceanorderformilkdelivery,theseller
enters a new record in Orders with all the customer information. The company has operated for
about ten years, and during this time there have been about 10,000 records inserted in Orders.
Now, the owners want to create a Web interface to allow customers to place their own orders
online: existing customers will provide their customer ID then can place their order, while new
4
Page 5


Name:
CSEP 544, Spring 2009, Final Examination
Take-home Exam
June 2-4, 2009
Rules
• Open books, open notes, access to the computer.
• No communication/collaborations allowed with your colleagues.
• Questions ? Send email to Dan Suciu and cc’ Bhushan Mandhani.
• Posted: Tuesday, June 2nd, 9:30pm.
• Return by: Thursday, June 4th, 11:59pm.
• Dropbox:https://catalysttools.washington.edu/collectit/dropbox/bhushan/5598
• What to turn in: text ?le, or Word ?le.
• WRITE YOUR NAME !
Question Max Grade
1 25
2 15
3 20
4 10
5 20
6 10
Total 100
1
Name:
1. (25 points) Relational Model A large IT corporation stores their access control policy to their
objects in a database with the following schema:
User(uid, uname) /* all the users */
Group(gid, gname) /* all the groups */
Member(uid, gid) /* users belong to groups (many-many) */
Object(oid, oname) /* all the objects */
AccessGranted(gid, oid) /* access to an object is granted on a per group basis */
AccessDenied(uid, oid) /* access is denied on a per user basis; overrides AccessGranted */
AccessLog(uid, oid, t) /* logs whenever a user accesses an objectq; t=timestamp */
Thesepoliciesareenforcedintheapplications,whichhavetoreadthedatabasetodetermineifarequest
to an object should be granted or denied, then proceed accordingly. Grant policies are group-based:
that is, an entire group is granted access to an object. Deny policies are user based: a particular user
may be denied access to an object, even if the user belongs to a group that has access to the object.
For auditing purposes, every time an object is accessed by a user, the system logs an entry into the
AccessLog table.
(a) Describe the SQL schema and the constraints for this data. You have to turn in seven CREATE
TABLE statements that contain the primary key and the foreign key constraints. All user ids,
groupids, objectids, andthetimestampsareintegers; allotherattributesare VARCHAR(n), where
you can choose a suitable value for n.
(b) Write a SQL query that computes the total number of distinct objects accessed by the system, in
a sliding window of width 10. That is, your query should report pairs (t, count) where count
represents the number of distinct objects accessed during the timestamps t...t+9.
(c) Write a SQL query that checks if any of the accesses recorded in AccessLog were illegal. Your
query should return all illegal accesses, i.e. accesses where the user uid was not permitted to
access the object oid.
2
(d) A group is called useless if all the access grant permissions given through that group are over-
ridden by a access deny entry. That is, the group is useless if for every member U of that group
and for every object O to whom that group is being granted access, there is an entry (U,O) in
AccessDenied: it means that the group is not useful in granting any access at all, since all the
accesses are overridden in the AccessDenied table. Write a SQL query to ?nd all useless groups.
3
2. (15 points) Functional Dependencies and Database Design
(a) Consider the following three relations, their attributes, and their keys:
R(A,B,C)
S(D,E)
T(F,G,H)
For each of the viewsV
1
,...,V
5
below indicate their attributes, and list a set of functional depen-
dencies (FDs) such that all the FDs that hold in the view can be inferred from these.
V
1
= R1
B=D
S
V
2
= S1
E=G
T
V
3
= s
H=55
(T)
V
4
= ?
AB
(R)
V
5
= ?
H,sum(G) as K
(T)
For example, your answer could look as follows:
V
9
(A,B,D,F,G) AB?DFG; F ?B
(b) Consider a table R(A,B,C,D,E,F) and the following functional dependencies:
BC ? A
BDE ? F
EF ? B
Compute a BCNF representation of R. Explain your steps.
(c) The MomPopDairy Company has a database with a single table:
Orders(customerID, customerName, customerAddress, milkQuantity, date)
Intheircurrentoperation,everytimeacustomercallstoplaceanorderformilkdelivery,theseller
enters a new record in Orders with all the customer information. The company has operated for
about ten years, and during this time there have been about 10,000 records inserted in Orders.
Now, the owners want to create a Web interface to allow customers to place their own orders
online: existing customers will provide their customer ID then can place their order, while new
4
customers will provide their name and address and will be assigned a customer ID that they can
use for future orders. The company owners would like to keep all the old data, but would also
like to enable the new application. They hire you as a database consultant to advise them on how
to manage their database so that it can support the new Web application. You observe quickly
that their schema is not in normal form. Advise the MomPopDiary Company on their options.
Give them two options on how to design the Web application and/or restructure the database,
explaining the immediate costs versus long term bene?ts tradeo?. Keep your explanations short:
for each of the two option, given your answer in 1-3 sentences, then brie?y enumerate the pros
and cons.
5
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!