B561 Assignment 3 Boolean queries solution

$24.99

Category:

Description

5/5 - (2 votes)

In this assignment, you will be required to use PostgreSQL. Your solutions
should include the PostgreSQL statements for solving the problems. Turn in a
.sql file with your solutions on IUCanvas as well as a .txt with outputs generated by your solutions. (I.e., use the standard turn-in procedure for assignments.) We furthermore encourage, but not require you to include comments
that explain your solutions.
1 Queries with expressions and functions; Boolean
queries
For the problems in this section, you can use views (including parameterized
views, i.e., user-defined functions) but you can not use aggregate functions nor
the GROUP BY and HAVING clauses. You can also not use the INNER JOIN (or
other joins) operators.
1. Let A(x) and B(x) be two unary relation schemas that represent a set A
and a set B, respectively. (The domain of x is INTEGER.)
(a) Write a SQL statement that determines whether it is true or not
if A − B is empty, B − A is empty, and A ∩ B is empty. Make
appropriate use of the SQL operators UNION, INTERSECT and/or
EXCEPT in your SQL statement. In this problem, you can not use
the set predicates of SQL.
(b) Repeat problem 1a but this time you can not use UNION, INTERSECT and/or EXCEPT. However, you can use the IN, NOT IN,
EXISTS and/or NOT EXISTS.
For example, if A = {1, 2, 3} and B = {1, 3} then your SQL statements
should produce the output:
empty_a_minus_b | empty_b_minus_a | empty_a_intersection_b
—————–+—————–+—————————-
f | t | f
(1 row)
because A − B = {2}, B − A = ∅, and A ∩ B = {1}.
Your solution should work for arbitrary A and B.
2. SQL uses 3-valued logic where it concerns the treatment of NULL (i.e., the
value “unknown”). (Read your textbook or search the web for relevant
information.) Consider relation schemas p(value), q(value), and r(value)
where the type of the attribute value is boolean. In other words, p, q,
1
and r represent propositional (boolean) variables. Populate each of these
relations with the possible values true, false, and NULL (i.e., the value
unknown).
In other words, p, q, and r are as follows:
p
value
t
f
NULL
q
value
t
f
NULL
r
value
t
f
NULL
Write a SQL statement that generates the 3-valued truth table for the
Propositional Logic formula
(p → q) → (¬r)
Your statement should return the following answer:
p | q | r | value
—+—+—+——-
t | t | t | f
t | t | f | t
t | t | |
t | f | t | t
t | f | f | t
t | f | | t
t | | t |
t | | f | t
t | | |
f | t | t | f
f | t | f | t
f | t | |
f | f | t | f
f | f | f | t
f | f | |
f | | t | f
f | | f | t
f | | |
| t | t | f
| t | f | t
| t | |
| f | t |
| f | f | t
| f | |
| | t |
| | f | t
| | |
(27 rows)
The blank characters in this table represent the NULL (unknown) value.
3. Consider the relation schema Point(pid, x, y) of a relation of points in
the plane. The attribute pid (of type INTEGER) is the identifier of a
point, and the attributes x and y, both of type FLOAT, are its x and y
coordinates.
(a) Write a SQL query that returns the (p1, p2) pairs of different pids
of points that are closest in distance from each other. Recall that
if p1 = (x1, y1) and p2(x2, y2) are two points in the plane, then the
distance between them is given by the formula
p
(x1 − x2)
2 + (y1 − y2)
2
For example if you have the following points,
2
pid | x | y
—-+—+—
1 | 0 | 0
2 | 0 | 1
3 | 1 | 0
Then your answer should be
p1 | p2
—-+—+—
1 | 2
2 | 1
1 | 3
3 | 1
Notice that the pairs (2, 3) and (3, 2) are not in this answer because
the distance between points 2 and 3 is larger than the distance between each pair of points reported in the above answer.
(b) Determine the triples of different points (p1, p2, p3) that are collinear.
Recall that points p1, p2, and p3 are collinear if they lie on the same
straight line.
4. Let R(A, B, C) be a relation schema. The attributes A, B, and C have as
their domain INTEGER.
(a) Write a SQL statement that determines whether or not A is a primary
key for the relation R.
(b) Provide two R instances where one of these instances has A as primary key and the other does not have A has a primary key. Of
course, the determination of the primary key property for these instances needs to be verified by using your SQL statement for this
problem.
2 Queries using aggregate functions
In the problems in this section, you will practice working with aggregate functions. As explained in the lecture on aggregate functions and partitioning, there
are various approaches to accomplish this:
• the GROUP BY map COUNT method;
• the user-defined COUNT FUNCTION method; and
• the SELECT COUNT-expression method.
3
To solve the problems in this section, you can freely use any of these methods.
For some of the problems in this section, use the relations student, major,
book, and buys that can be found in the data.sql file.
5. Let M be an n × n matrix of integers (n is a positive integer).
For i, j ∈ [1, n], we will denote by M[i, j] the element in matrix M at row
i and column j.
Given an n×n matrix M, denotes by M2
the n×n the matrix define such
that for i, j ∈ [1, n], row i and column j of M2
is defined by the formula
M2
[i, j] = Xn
k=1
M[i, k]M[k, j].
The matrix M can be represented using a ternary relation M with schema
(row, colmn, value)
1 as follows: for each pair i, j ∈ [1, n], tuple (i, j, v) in
M represents that v = M[i, j].
For example if M is the 3 × 3 matrix
M =
1 2 3
1 −3 5
4 0 −2
then M is the following relation of 9 tuples:
M
row colmn value
1 1 1
1 2 2
1 3 3
2 1 1
2 2 −3
2 3 5
3 1 4
3 2 0
3 3 −2
Let M be an n × n matrix represented by the relation M.
Write a SQL query that computes a relation over schema (row, column,
value) that represents the matrix M4
, where M4
is defined as the matrix
(M2
)
2
.
Your solution should work for any n ≥ 1.
1Notice that we use the attribute name ‘colmn’ since the word ‘column’ is a reserved word
in PostgreSQL.
4
6. Let A(x) be a unary relation schema that represent a set A of integers.
(So the domain of x in INTEGER.)
Define the following equivalence relation on A: for each pair of elements x
and y in A, we say that x and y are equivalent if x mod 4 = y mod 4. (Recall
that x mod 4 is the remainder of the integer division of x by 4.)
Given a relation A(x) storing a set of integers, determine for each possible
remainder value, i.e. 0, 1, 2, or 3, the number of elements in A that are
equivalent relative to these values.
7. Let A(x) be a unary relation schema that represent a bag A of integers.
(So the domain of x in INTEGER.)
For example, we may have the following bag:
A
x
5
3
3
2
1
3
5
Write a SQL query that coerces such a bag into a set which contains the
same elements as the bag. (In this problem, you can not use the DISTINCT
clause.)
In other words, for the bag above, the query should output the set
x
1
2
3
5
8. Formulate the following queries in SQL:
(a) “Find the bookno’s and titles of books that cost less than $40 and
that where bought by fewer than 3 CS students.”
(b) “For each student, find the sid and name of that student along with
the number of books bought by that student, provided that the collective cost of these books is less that $200.”
(c) “Find the sids and names of the students who spent the most on the
books that they bought.”
5
(d) “For each major, specify the combined cost of all the books bought
by students with that major.”
(e) “Find the pairs of different booknos (b1, b2) that were bought by the
same number of CS students.”
3 Queries with quantifiers using Venn diagrams
with conditions
For the following problems, use the relations student, major, book, and buys
that can be found in the data.sql file.
Using the method of Venn diagrams with conditions and without using the
COUNT function, write SQL queries for the following queries with quantifiers.
In these problems, you must write appropriate views and parameterized
views for the sets A and B that occur in the Venn diagram with conditions for
these queries. (See the lecture on Queries with Quantifiers.)
9. Find the sid and name of each student who did not buy all the books that
cost more than $50.
10. Find the bookno and title of each book that was not only bought by
students who major in ‘CS’ or in ’Math’.
11. Find the sid and name of each student who bought none of the least
expensive books.
create or replace view leastExpensiveBook as (select b.bookno from book
b where b.price = (select min(b1.price) from book b1));
12. Find the pairs of booknos (b1, b2) of different books that where bought by
the same set of CS students.
4 Queries with quantifiers using Venn diagrams
with counting conditions
Using the method of Venn diagram with counting conditions, write SQL queries
for the following queries with quantifiers.
In these problems, you should write appropriate views and parameterized
views for the sets A and B that occur in the Venn diagrams for these queries.
(See the lecture on Queries with Quantifiers Using the COUNT function.)
13. Find sid and name of each CS student who bought fewer than 4 books
that cost less that $50.
14. Find the bookno and title of each book that was bought by an odd number
of CS students.
6
15. Find the sid and name of each student who bought all but 3 books.
16. Find the pairs of booknos (b1, b2) of different books such that all the
students who bought book b1 also bought book b2.
7