B561-Assignment 3 Expressions and Functions and Aggregate Functions Solved

In this assignment, you will be required to use PostgreSQL.

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 notif 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, 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                      q                      r

value
 
value
 
value
t f

NULL
t f

NULL
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,

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.

1         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.

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

 .

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

                                                                       1      2       3

                                                                 M = 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.

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 xmod4 = y mod4. (Recall that xmod4 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 andthat where bought by fewer than 3 CS students.”

(b)   “For each student, find the sid and name of that student along withthe 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 thebooks that they bought.”

(d)   “For each major, specify the combined cost of all the books boughtby students with that major.”

(e)   “Find the pairs of different booknos (b1,b2) that were bought by the same number of CS students.”

2         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 thatcost more than $50.

10.   Find the bookno and title of each book that was not only bought bystudents who major in ‘CS’ or in ’Math’.

11.   Find the sid and name of each student who bought none of the leastexpensive 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.

3         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 booksthat cost less that $50.

14.   Find the bookno and title of each book that was bought by an odd numberof CS students.

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.


 
[1] Notice that we use the attribute name ‘colmn’ since the word ‘column’ is a reserved word in PostgreSQL.