Post on 30-Jan-2016
description
ISOM
MIS710 Module 2aComplex SQL Queries
Arijit Sengupta
ISOM
Monotonic and Non-Monotonic Queries
• Monotonic queries: queries for which the size of the results either increase or stay the same as the size of the inputs increase. The result size never decreases
• Non-monotonic queries: queries for which it is possible that the size of the result will DECREASE when the size of the input increases
• Examples of each?
ISOM
Examples of monotonic queries
ISOM
Examples of non-monotonic queries
ISOM
Which of the operations is non-monotonic?
A. Selection
B. Projection
C. Cross Product
D. Union
E. Set Difference
What does this signify?
ISOM
Identify – monotonic/non-monotonic?
• Find students who have taken algebra but not calculusA. MonotonicB. Non-monotonic
• Find students who have taken calculus but are not math majorsA. MonotonicB. Non-monotonic
ISOM
Answers to prev. slide
• Find students who have taken algebra but not calculus Non-monotonic – you take a student who has taken
algebra but not calculus, add a new registration for calculus, and he is gone from the result
• Find students who have taken calculus but are not math majors Monotonic! Assume Joe has taken calculus and is not
a math major – can you remove him from the result by adding more rows?
• Moral: If something is monotonic, you can solve it with basic SELECT-FROM-WHERE
• If something is non-monotonic – you HAVE to use something else
• Options are: MINUS, NOT IN, NOT EXISTS, Special grouping
ISOM
Identify – monotonic/non-monotonic
1. Find the students who have taken some CS courses
2. Find the students who have only taken CS courses
3. Find the students who have taken all the CS courses
4. Find the students who have not taken any CS course
5. Find the students who have taken a non-CS course
ISOM
Answers to previous slide
1. Monotonic – if someone has taken some CS course, he stays in the results regardless of what you add/remove
2. Non-monotonic – someone who has only taken CS course will disappear from the result if you add a registration for them for a non-cs course
3. Non-monotonic – if you add a new CS course, then …
4. Non-monotonic – if you add a registration for a CS course…
5. Monotonic! Someone who has taken a non-CS course will continue to stay in the result!
ISOM
Thumb rules
• Some clues to identify non-monotonic queriesEvery, AllNo, None, NeverOnly
• Remember – these are just thumb rules and not absolute laws – you need to think about how the queries will behave to determine non-monotonicity
ISOM
Lets do the monotonic first!
• Find students who have taken some CS course
SELECT s.*FROM Student s, Reg r, Course cWHERE s.sid = r.sid AND c.cno = r.cno AND c.dept = 'CS'
ISOM
The other monotonic query
• Find Students who have taken a Non-CS Course
SELECT s.*FROM Student s, Reg r, Course cWHERE s.sid = r.sid AND c.cno = r.cno AND c.dept != 'CS'
ISOM
Solving non-monotonic queries
• We know that MINUS can solve non-monotonic
• Unfortunately representing all queries using MINUS is not easy
• Some are easy:Students who have not taken any CS
courseAll students MINUS students who have
taken some CS course
ISOM
Non-monotonic queries using MINUS
• All students MINUS students who have taken some CS course
SELECT s1.*FROM Student s1
MINUS
SELECT s.*FROM Student s, Reg r, Course cWHERE s.sid = r.sid AND c.cno = r.cno AND c.dept = 'CS'
ISOM
Nesting Queries - Syntax
SELECT attribute(s)
FROM relation(S)
WHERE attr [not] {in | comparison operator | exists }
( query statement(s) );
List names of students who are taking “MIS415”
select Name
from Student
where SID in
( select SID
from REG
where Cno = ‘MIS415’);
ISOM
Sub Queries
List all students enrolled in MIS coursesselect namefrom STUDENTwhere SId in
(select SIdfrom REGwhere cno like ‘MIS%’);
List all students enrolled in MIS coursesselect namefrom STUDENTwhere SId in
(select SIdfrom REGwhere cno like ‘MIS%’);
List all courses taken by Student (Id 1011) select cnamefrom COURSEwhere cnum = any
(select cnofrom REGwhere SId = 1011);
So, IN and ANY essentially are like joins, not that interesting
ISOM
Sub Queries - continued
Who received the highest score in MIS 415select SIdfrom REGwhere cno = ‘MIS415’ and
score >=all(select scorefrom REGwhere cno = ‘MIS415’);
Who received the highest score in MIS 415select SIdfrom REGwhere cno = ‘MIS415’ and
score >=all(select scorefrom REGwhere cno = ‘MIS415’);
List all students enrolled in MIS courses.select namefrom STUDENT Swhere exists
(select *from REGwhere SId = S.SId
and cno like ‘MIS%’);
ALL is quite powerfulSince it works on the wholeSet returned by the subquery
Exists is again likeA join!
ISOM
Non-monotonic queries using NOT IN and NOT Exists
• Students who have not taken CS courses
Using NOT IN
SELECT s.*FROM Student sWHERE s.sid not IN ( SELECT r.sid FROM Reg r, Course c WHERE r.cno = c.cno AND c.dept = ‘CS’)
Using NOT EXISTS
SELECT s.*FROM Student sWHERE NOT EXISTS ( SELECT * FROM Reg r, Course c WHERE r.cno = c.cno AND c.dept = ‘CS’ AND r.sid = s.sid)
Notice how the alias ‘s’ from outside thesubquery is used in the subquery!These are called “correlated” subqueries.
ISOM
The “default” results
• Notice that sometimes queries using not exists will give you results that appear “by default”
• For example, students who have not taken ANY course will show up in the result of the last query
• Okay for this query?
ISOM
Writing non-monotonic queries
• See if you can rewrite the statement below in English with double negatives.
• Remember – the new sentence MUST mean the same!• Find students who have taken ALL CS courses
ISOM
Try another one
• Find students who have got A’s in All courses they took
ISOM
Tackling non-monotonic queries
• Try 1: See if you can write it as a difference between two setsSolve using MINUS or NOT IN
• Try 2: Rewrite the query to use the tables and finding ways to use not existsFind students who have taken all CS coursesFind students such that there is no CS course
that they have not takenFind students such that there doesn’t exist
any CS course for which there doesn’t exist a registration for that student in that course!
Yes, a lot of double negatives!
ISOM
Step by Step
• Find students who have taken all CS courses
Find students
such that there doesn’t exist
any CS course
for which there doesn’t exist
a registration
for that student
in that course!
SELECT s.*FROM Student s
WHERE not exists (
SELECT c.* FROM Course c WHERE c.dept = ‘CS’
AND NOT EXISTS (
SELECT r.* FROM Reg r WHERE
r.sid = s.sid
AND r.cno = c.cno))
ISOM
Should we do one more?
• Find students who have ONLY taken CS courses
• Find students such that every course they have taken is a CS course
• Find students such that every registration they have corresponds to a CS course
• Find students such that there doesn’t exist any registration record for that student corresponding to a non-CS course
ISOM
Translating this query
Find students
such that
there doesn’t exist
any registration record
for that student
corresponding to a
non-CS course
SELECT s.*
FROM Student s
WHERE not Exists ( SELECT r.*
FROM Reg r, Course c
WHERE r.sid = s.sid
AND r.cno = c.cno
AND c.cno != ‘CS’)
ISOM
Default result here
• You will notice that students who have not taken any courses will show up in this query’s results!
• Why?• Logically, students who haven’t taken
any courses haven’t taken any non-cs courses
• To get rid of this default behavior, you may want to perform a join on the outermost query, so that you retrieve students who have taken some course
ISOM
Query with the default removed
SELECT s.*
FROM Student s, Reg R1
WHERE s.sid = R1.sid
AND not Exists ( SELECT r.*
FROM Reg r, Course c
WHERE r.sid = s.sid
AND r.cno = c.cno
AND c.cno != ‘CS’)
Now this query will only retrieve students who have taken at least one course, none of which is CS.
ISOM
Relational Views
• Relations derived from other relations.• Views have no stored tuples.• Are useful to provide multiple user views.
View 1 View 2 View N
BaseRelation 1
BaseRelation 2
•What level in the three layer model do views belong?•Which kind of independence do they support?
ISOM
View Creation
Create View view-name [ ( attr [ , attr ] ...) ]
AS subquery
[ with check option ] ;
DROP VIEW view-name;
Create a view containing the student ID, Name, Age and GPA for those who are qualified to take 300 level courses, i.e., GPA >=2.0.
ISOM
View Options
• With Check Option enforces the query condition for insertion or update
To enforce the GPA >=2.0 condition on all new student tuples inserted into the view
• A view may be derived from multiple base relations
Create a view that includes student IDs, student names and their instructors’ names for all CIS 300 students.
ISOM
View Retrieval
Queries on views are the same as that on base relations.
Queries on views are expanded into queries on their base relations.
select Name, Instructor-Name
from CIS300-Student
where Name = Instructor-Name;
ISOM
View: Update
Update on a view actually changes its base relation(s)!
update Qualified-Student
set GPA = GPA-0.1
where StudentID = ‘s3’;
insert into Qualified-Student
values ( ‘s9’, ‘Lisa’, 4.0 )
insert into Qualified-Student
values ( ‘s10’, ‘Peter’, 1.7 )
Why are some views not updateable?
What type of views are updateable?
ISOM
Summary
• SQL is a low-complexity, declarative query language
• The good thing about being declarative is that internally the query can be changed automatically for optimization
• Good thing about being low-complexity? No SQL query ever goes into an infinite loopNo SQL query will ever take indefinite amount of
space to get the solution
• Can be used for highly complex problems!