Transcript Venn Diagrams

Venn Diagrams
Database Principles
Venn Diagram
• Venn Diagrams are used to represent relationships
between sets.
• They can also be used to represent set operations like
union, intersection and set difference.
• Since Relational Algebra has operations corresponding
to these set operations, Venn Diagrams are a useful
design tool for Relational Algebra Queries.
union
Table1
intersection
Table2
Table1
Database Principles
set difference
Table2
Table1
Table2
Exercise:
• Draw a Venn Diagram showing the following three sets:
– The set of all suppliers
– The set of suppliers of red parts
– The set of suppliers of non-red parts
• Label each part of the diagram.
All Suppliers
Suppliers who supply
nothing at all
Suppliers of Red Parts
Suppliers of both Red and
non-Red Parts
Suppliers of non-Red Parts
Database Principles
Query Types:
• Hard Queries: These are queries that have words such
as “only”, “all” and “no” in the query condition.
Find the suppliers of all/no/only red parts
• Easy Queries: Queries without such words in the
condition.
Find the suppliers who supply some red part
• What makes a query “easy” is that is can be answered
with at most join, select and project operators.
• What makes a query “hard” is that you must use set
difference or quotient to answer the query.
Database Principles
Easy Queries:
• Venn Diagrams do not play much part in solving easy
queries. The problem is too easy to need a design
phase.
• Easy queries are solved by joining all necessary tables,
selecting the rows of interest and projecting the columns
in the answer.
Database Principles
Hard Queries:
Remember
Pr(A) = 1 – Pr(¬A)
• In probability, it is often easier to calculate the probability
of the complement of an event (¬A) than the probability
of the event itself (A).
• This same approach can be used to solve hard queries.
• Asked to find something hard:
– Start by stating and finding its complement
– Then use the set difference operator to throw away
the newly found complement
– You are left with what you want
Database Principles
“Only” Query
• Find the suppliers (SName) who supply only red parts.
PartSuppliers = πSNo(Supplies)
. s5
. s2
. s3
. s4
. s1
suppliers of only red parts = ?
Describe this set.
OnlyRedPartSuppliers =
PartSuppliers \ NonRedpartSuppliers
suppliers of at least one
part that is not red
NonRedParts =
πPNo(σColour != ‘red’ (Part))
FinalAnswer =
πSName(Supplier
NonRedPartSuppliers =
πSNo(Supplies
NonRedParts)
Database Principles
OnlyRedPartSuppliers)
Exercise:
• In the previous Venn Diagram, find out where the
Suppliers who supply nothing at all are located.
• It turns out they are not in the answer set.
• What if we want them in the answer set?
Replace
PartSuppliers = πSNo(Supplies)
with
PartSuppliers = πSNo(Supplier)
Database Principles
Negation Queries:
• Entity Properties:
– Location of a Supplier is a property modeled as an
attribute
– What Parts a Supplier supplies is also a property
modeled as a relationship
supplies
Part
Supplier
PK
PK
Sno
(0,n)
Sname
Location
Pno
(1,n)
O_date
Database Principles
Pdesc
Colour
Negation Queries (Some are Easy):
• Find the Suppliers who do not come from Boston.
supplies
Part
Supplier
PK
PK
Sno
(0,n)
Sname
Location
Pno
(1,n)
O_date
Pdesc
Colour
Find all entity instances where the
value of Location is not Boston
Query Mechanism: Look at all the entity instances and as you find one
where the value of Location is something other than ‘Boston’, pick out
and return that instance as part of the answer.
SuppliersNotFromBoston = σLocation != ‘Boston’ (Supplier)
Database Principles
Negation Queries (Some are Hard):
• Find the Suppliers who do not supply any Parts.
supplies
Part
Supplier
PK
PK
Sno
(0,n)
Sname
Location
Pno
(1,n)
O_date
Pdesc
Colour
Find all entity instances that do not
participate in the <supplies> relationship.
Query Mechanism: Pick a Supplier. Look at every row in the Supplies table
and if you fail to see that Supplier even once then consider that Supplier as
part of the answer set. Then move on to a new Supplier.
So instead of selecting members of the answer set looking at rows one at a time
(which is what happens when we use join) we need to consider all the rows in
Supplies as a set and see if a particular Supplier is completely missing or not.
NonSuppliers = πSNo(Supplier) \ πSNo(Supplies)
Database Principles
Negation Queries (Summary):
• Negation queries that negate the value of an attribute
are “easy” and can be resolved using join, select &
project.
• Negation queries that negate the participation in a
relationship are “hard” and need set difference.
Table1
Database Principles
Table2
Quotient Queries:
• Queries that contain “all” or “every” in the query
condition.
• Venn diagrams not very useful.
Q = R/S where:
Q = the key to the thing you are looking for
S = the key to the thing described in the “all” condition
R = a table that contains the above two keys and is
related to the query.
S = the list of key values that satisfy the “all” condition
Example: Find the books reserved by all cardholders from New Paltz
Q = {isbn}, since we are looking for books
S = {borrowerid}, since borrowerid is the key for cardholders
S = πborrowerid(σb_addr = ‘New Paltz’ (Cardholder))
R = {isbn,borrowerid}, must combine Q and S.
R = πisbn,borrowerid(Reserves)
Q = R/S = {the books reserved by all cardholders from New paltz}
Database Principles