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 Rp 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 Mw iff word w appears on page P