Team Name :

IU-Techies 2015
Database Design Competition

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

1. Database design (40%)

For each researcher, his/her name, year of birth, and current position (if any).
For each institution, its name, country, and inauguration year.
For each institution, the names of its schools (e.g. School of Law, School of
Business, School of Computer Science,. . .). A school belongs to exactly one
institution.
An employment history, including information on all employments (start and end
date, position, and what school).
Information about co-authorships, i.e., which researchers have co-authered a
research paper. The titles of common research papers should also be stored.
For each researcher, information on his/her highest degree (BSc, MSc or PhD),
including who was the main supervisor, and at what school.
For each professor, information on what research projects (title, start date, and
end date) he/she is involved in, and the total amount of grant money for which
he/she was the main applicant.

a) Draw an E/R diagram for the data set described above. Make sure to indicate all
cardinality constraints specified above. The E/R diagram should not contain
redundant entity sets, relationships, or attributes. Also, use relationships
whenever appropriate. If you need to make any assumptions, include them in
your answer.

b) Convert your E/R diagram from question a) into relations, and write SQL
statements to create the relations. You may make any reasonable choice of data
types. Remember to include any constraints that follow from the description of
the data set or your E/R diagram, including primary key and foreign key c

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

2. Normalization (30%)
We consider the following relation:
Articles(ID, title, journal, issue, year, startpage, endpage, TR-ID)
It contains information on articles published in scientific journals. Each article has a unique ID, a
title, and information on where to find it (name of journal, what issue, and on which pages). Also,
if results of an article previously appeared in a technical report (TR), the ID of this technical
report can be specified. We have the following information on the attributes:

ID
42
33
33
39
57
77
78

For each journal, an issue with a given number is published in a single year.
The endpage of an article is never smaller than the startpage.
There is never (part of) more than one article on a single page. The following is an
instance of the relation:
title
Cuckoo Hashing
Deterministic Dictionaries
Deterministic Dictionaries
Dictionaries in less space
P vs NP resolved
What Godel missed
What Godel missed

Journal
JAlg
JAlg
JAlg
SICOMP
Jacm
SICOMP
Nature

issue
51
41
41
31
51
51
222

year
2004
2001
2001
2001
2008
2008
2008

startpage
121
69
69
111
1
1
22

endpage
133
85
85
133
3
5
22

TR-ID
87
62
56
47
99
98
98

a) Based on the above, indicate for each of the following sets of attributes whether it
is a key for Articles or not. Use the answer sheet of the exam for your answer.
1. {ID}; 2. {ID,TR-ID}; 3. {ID,title,TR-ID} 4. {title}; 5. {title,year}; 6. {startpage,
journal,issue}. If you wish, you may additionally write a brief explanation for each
answer, which will be taken into account, but is not necessary to get full points.

b) Based on the above, indicate for each of the following potential functional
dependencies, whether it is indeed an FD or not. Use the answer sheet of the
exam for your answer. 1. ID title; 2. startpage endpage; 3. journal issue
year 4. title ID; 5. ID startpage endpage journal issue; 6. TR-ID ID. If you
wish, you may additionally write a brief explanation for each answer, which will
be taken into account, but is not necessary to get full points.

c) Based on a) and b), perform normalization into BCNF, and state the resulting
relations
The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/
Page 3 of 12

Team Name :

3. SQL (30 %)
We consider again the relation Articles from problem 2.

a) Indicate for each of the following expressions whether it is a valid SQL statement
or not. A valid statement should be accepted by a standard SQL interpreter,
whereas an invalid statement should result in an error message. Use the answer
sheet of the exam for your answer. 1. SELECT * FROM Articles WHERE endpage startpage > 10; 2. SELECT * FROM Articles WHERE endpage - startpage < 0; 3.
SELECT SUM(title) FROM Articles; 4. SELECT AVG(year) FROM Articles WHERE
title LIKE 'C%'; 5. SELECT COUNT(*) FROM Articles GROUP BY year; 6. SELECT
year,COUNT(*) FROM Articles WHERE COUNT(*) > 10 GROUP BY year;

b) Indicate for each of the following queries, how many tuples would be returned if
it was run on the instance of Articles from problem 2. Use the answer sheet of the
exam for your answer. 1. SELECT ID FROM Articles WHERE year < 2006; 2.
SELECT DISTINCT ID FROM Articles WHERE year < 2006; 3. SELECT AVG(year)
FROM Articles GROUP BY journal; 4. SELECT ID FROM Articles WHERE title LIKE
'%d';

c) Write an SQL query that returns the titles of articles authored by 'Robert Tarjan'.

d) Write an SQL query that returns for the titles appearing in more than one
journals.

e) Write an SQL query that returns the number of co-authors of 'Robert Tarjan'. (i.e.,
the number of authors who have written at least one article together with him.)

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

Answer Sheet
1.a)

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

1.b)

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

2.a)
#
Key
Not a Key

2.b)
#
FD
Not an FD

2.c)

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

3.a)
#
Valid
Invalid

3.b)
#
Number of tuples

3.c)

3.d)

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

3.e)

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/

Team Name :

The problem was formulated by Rasmus Pagh - http://itu.dk/people/pagh/