Venn Diagrams

of 13

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
13 pages
0 downs
0 views
Share
Description
Venn Diagrams. 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.
Transcript
Venn DiagramsDatabase PrinciplesVenn 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 intersection set differenceDatabase PrinciplesExercise:
  • 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 SuppliersSuppliers who supplynothing at allSuppliers of Red PartsSuppliers of both Red and non-Red PartsSuppliers of non-Red PartsDatabase PrinciplesDatabase PrinciplesQuery Types:
  • Hard Queries: These are queries that have words such as “only”, “all” and “no” in the query condition.
  • Easy Queries: Queries without such words in the condition.
  • 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.
  • Find the suppliers of all/no/only red partsFind the suppliers who supply some red partDatabase PrinciplesEasy 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 PrinciplesHard Queries:
  • 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
  • Remember Pr(A) = 1 – Pr(¬A)“Only” Query
  • Find the suppliers (SName) who supply only red parts.
  • PartSuppliers = πSNo(Supplies) . s5. s2. s3. s1suppliers of only red parts = ?. s4Describe this set.OnlyRedPartSuppliers = PartSuppliers \ NonRedpartSuppliersFinalAnswer = πSName(Supplier OnlyRedPartSuppliers)suppliers of at least onepart that is not redNonRedParts = πPNo(σColour != ‘red’ (Part))NonRedPartSuppliers =πSNo(Supplies NonRedParts)Database PrinciplesDatabase PrinciplesExercise:
  • 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?
  • ReplacewithPartSuppliers = πSNo(Supplies) PartSuppliers = πSNo(Supplier) 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
  • Database PrinciplesNegation Queries (Some are Easy):
  • Find the Suppliers who do not come from Boston.
  • Find all entity instances where the value of Location is not BostonQuery 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 PrinciplesNegation Queries (Some are Hard):
  • Find the Suppliers who do not supply any Parts.
  • Find all entity instances that do notparticipate in the <supplies> relationship.Query Mechanism: Pick a Supplier. Look at every row in the Supplies tableand 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 PrinciplesNegation 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.
  • Database PrinciplesDatabase PrinciplesQuotient 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 forS = 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” conditionExample: Find the books reserved by all cardholders from New PaltzQ = {isbn}, since we are looking for booksS = {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}
    Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks