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. Systems like MySQL are able to execute very similar high-level instructions efficiently on standard computer hardware, which helps programmers focus on high-level design. 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 piL 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 piff person e has recommended page p 2/4 A set W of words that may appear on pages A binary relation M (for mentions) between pages and words, where p Mwiff 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 correctly, 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 - relation image-for example, R(A) for some set A, or R(a) for some specific element a. relation inverse - 1 .... and one extra: relational composition which generalizes composition of functions a (ROS)c::= 3 B. (a Sb) A (BRc). In other words, a is related to c in RoS if starting at a you can follow an arrow to the start of an R arrow and then follow the R arrow to get to c. Here is one worked examaple 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 "Wiggins" (c) The set of endorsers who have recommended pages containing the word "algebra" (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 pi and p2 iff p2 can be reached from pi by following a sequence of exactly 3 links 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. Systems like MySQL are able to execute very similar high-level instructions efficiently on standard computer hardware, which helps programmers focus on high-level design. 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 piL 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 piff person e has recommended page p 2/4 A set W of words that may appear on pages A binary relation M (for mentions) between pages and words, where p Mwiff 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 correctly, 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 - relation image-for example, R(A) for some set A, or R(a) for some specific element a. relation inverse - 1 .... and one extra: relational composition which generalizes composition of functions a (ROS)c::= 3 B. (a Sb) A (BRc). In other words, a is related to c in RoS if starting at a you can follow an arrow to the start of an R arrow and then follow the R arrow to get to c. Here is one worked examaple 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 "Wiggins" (c) The set of endorsers who have recommended pages containing the word "algebra" (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 pi and p2 iff p2 can be reached from pi by following a sequence of exactly 3 links
