CSE 532 Assignment #2

Due Thursday, February 28, 2013 (1 pm).


Problem Set (100 points)

  1. (25 points) Let us consider the following relations/predicates:
    Note that courses are represented by their unique numbers in relations Prereqs and Enrolls; students are represented by their ID's. Prerequisites are immediate prerequisites only. For example, if CS101 is a prerequisite of CS200, and CS200 is a prerequisite of CS342, then only the pairs (CS200, CS101) and (CS342, CS200) would appear in Prereqs. We refer to CS101 as an indirect prerequisite of CS342. Write the following questions in Datalog:
    1. Find the prerequisites, including indirect prerequisites, of CS103.
    2. Find the students who enrolled in CS488 but never (i.e., in no previous quarter) enrolled in one or more of its direct or indirect prerequisites.
  2. (25 points) Consider a database for the Paris Metro and Bus lines, consisting of two relations Metro(Station, Next) and Bus(Station, Next).
    1. Find pairs of stations (m,n), such that m can be reached from n by a bus path (using only buses) AND a metro path (using only metros).
    2. We say that the metro is useless in a bus path from m to n if by taking the metro at any intermediate point k one can return to k, but not reach any other station along the path. Find the pair of stations (m,n) such that the metro is useless in all the bus paths connecting m and n.
  3. (25 points) A graph is a set of nodes, where some pairs of nodes are connected by an edge. Let us consider a set of graphs represented by the following two relations: GraphNodes(GraphName , Node) and GraphEdges(GraphName, Node1, Node2 ). The relation GraphNodes stores the set of nodes for each graph, and a tuple (g,x,y) in the relation GraphEdges means that in graph g the nodes x and y are connected by an edge. We assume that if a tuple (g, x, y) exists in GraphEdges then (g, x) and (g, y) both exist in GraphNodes. However, GraphNodes may have additional tuples. Write stratified datalog programs for each of the following queries. 
    1. Find the set of graphs that have a diameter of at most k (i.e., the distance (length of shortest path) between each pair of nodes is at most k). Here, k is a constant and may be used as part of your datalog rules in arithmetic predicates. However, the number of rules in your program should be independent of k.
    2. A 2-center of a graph G is a node A in G such that every node is G is at most at a distance of 2 from A. For each graph, find its 2-center, if one exists.
    Assume that the given graphs are DAGS (i.e., directed acyclic graphs). Also, assume that you are given an EDB AddOne(m,n), which contains the tuple (m, m+1) for any integer m.
  4. (25 points) Suppose we have EDB relations: frequents(Drinker, Bar) , serves(Bar, Beer), and likes(Drinker, Beer). The relations have obvious meanings. Define the following predicates using safe datalog rules.
    1. veryHappy(D) if every bar that drinker D frequents serves at least one beer he likes. You may assume that every drinker frequents at least one bar.
    2. sad(D) if drinker D frequents all bars that serve no beer he likes.