Problem 4.28. The language of sets and relations may seem remote from the practical world of programming, but in fact there is a close connection to relational databases, a very popular software application building block implemented by such software packages as MySQL. This problem explores the connection by considering how to manipulate and analyze a large data set using operators over sets and relations. Sys- tems like MySQL are able to execute very similar high-level instructions efficiently on standard computer hardware, which helps programmers focus on high-level de- sign. Consider a basic Web search engine, which stores information on Web pages and processes queries to find pages satisfying conditions provided by users. At a high level, we can formalize the key information as: A set P of pages that the search engine knows about A binary relation L (for link) over pages, defined such that p L P2 iff page P links to p2 A set E of endorsers, people who have recorded their opinions about which pages are high-quality A binary relation R (for recommends) between endorsers and pages, such that e R p iff person e has recommended page p A set W of words that may appear on pages A binary relation M (for mentions) between pages and words, where p M w iff word w appears on page p Each part of this problem describes an intuitive, informal query over the data, and your job is to produce a single expression using the standard set and relation operators, such that the expression can be interpreted as answering the query cor- rectly, for any data set. Your answers should use only the set and relation symbols given above, in addition to terms standing for constant elements of E or W, plus the following operators introduced in the text: set union U. set intersection n. set difference relational image-for example, R(A) for some set A, or R(a) for some spe- cific element a. relational inverse-1. .... and one extra: relational composition which generalizes composition of functions a (ROS)c::= 3b B. (a S b) AND (b Rc). In other words, a is related to c in RoS if starting at a you can follow an S arrow to the start of an R arrow and then follow the R arrow to get to c. Here is one worked example to get you started: Search description: The set of pages containing the word logic Solution expression: M-("logic) Find similar solutions for each of the following searches: (a) The set of pages containing the word logic but not the word "predicate" (b) The set of pages containing the word "set" that have been recommended by "Meyer" . 10 (C) The set of endorsers who have recommended pages containing the word al- gebra" (d) The relation that relates endorser e and word w iff e has recommended a page containing w (e) The set of pages that have at least one incoming or outgoing link (f) The relation that relates word w and page p iff w appears on a page that links to p (g) The relation that relates word w and endorser e iff w appears on a page that links to a page that e recommends (h) The relation that relates pages P and p2 iff p2 can be reached from pi by following a sequence of exactly 3 links 10Note the reversal of R and S in the definition; this is to make relational composition work like function composition. For functions, fog means you apply g first. That is, if we let h be fog, then h(x) = f(g(x)). Problem 4.28. The language of sets and relations may seem remote from the practical world of programming, but in fact there is a close connection to relational databases, a very popular software application building block implemented by such software packages as MySQL. This problem explores the connection by considering how to manipulate and analyze a large data set using operators over sets and relations. Sys- tems like MySQL are able to execute very similar high-level instructions efficiently on standard computer hardware, which helps programmers focus on high-level de- sign. Consider a basic Web search engine, which stores information on Web pages and processes queries to find pages satisfying conditions provided by users. At a high level, we can formalize the key information as: A set P of pages that the search engine knows about A binary relation L (for link) over pages, defined such that p L P2 iff page P links to p2 A set E of endorsers, people who have recorded their opinions about which pages are high-quality A binary relation R (for recommends) between endorsers and pages, such that e R p iff person e has recommended page p A set W of words that may appear on pages A binary relation M (for mentions) between pages and words, where p M w iff word w appears on page p Each part of this problem describes an intuitive, informal query over the data, and your job is to produce a single expression using the standard set and relation operators, such that the expression can be interpreted as answering the query cor- rectly, for any data set. Your answers should use only the set and relation symbols given above, in addition to terms standing for constant elements of E or W, plus the following operators introduced in the text: set union U. set intersection n. set difference relational image-for example, R(A) for some set A, or R(a) for some spe- cific element a. relational inverse-1. .... and one extra: relational composition which generalizes composition of functions a (ROS)c::= 3b B. (a S b) AND (b Rc). In other words, a is related to c in RoS if starting at a you can follow an S arrow to the start of an R arrow and then follow the R arrow to get to c. Here is one worked example to get you started: Search description: The set of pages containing the word logic Solution expression: M-("logic) Find similar solutions for each of the following searches: (a) The set of pages containing the word logic but not the word "predicate" (b) The set of pages containing the word "set" that have been recommended by "Meyer" . 10 (C) The set of endorsers who have recommended pages containing the word al- gebra" (d) The relation that relates endorser e and word w iff e has recommended a page containing w (e) The set of pages that have at least one incoming or outgoing link (f) The relation that relates word w and page p iff w appears on a page that links to p (g) The relation that relates word w and endorser e iff w appears on a page that links to a page that e recommends (h) The relation that relates pages P and p2 iff p2 can be reached from pi by following a sequence of exactly 3 links 10Note the reversal of R and S in the definition; this is to make relational composition work like function composition. For functions, fog means you apply g first. That is, if we let h be fog, then h(x) = f(g(x))
