Queries

1. In 1977, President Jimmy Carter eased the immigration restrictions into the United States. That same year, Fidel Castro emptied his prisons. The following query might have been used by American Immigration officials in determining whether to deny entry to various individuals:

   retrieve NAME where (COUNTRY = Cuba AND AGE > 15 AND CRIME <> political)

   • Draw a parse tree for the above query. Now, assume that American Immigration officials have access to an international prisoner database, which consists of a main file and several inverted files. Given that secondary indices exist on the two fields, COUNTRY and CRIME, can we avoid reading the entire file sequentially in order to answer the query? You may do your work directly on the parse tree you have just drawn.

   • Now assume that a database is available, with the same information as above, but stored in the following files:
     • justice file (prisoner id, crime)
     • prison file (country, prisoner id, SIN)
     • census file (SIN, name, age)
     Write a relational algebra expression to express the original query.

2. The algorithm for determining whether secondary indices help in answering a query, Q, is given below:

      construct parse tree of Q
      mark each leaf that refers to an indexed field
      loop
         for each unmarked node
            if the node is an AND node with 
   		at least one marked child
            or it is an OR node with 
   		both children marked then 
   	    mark the node
         exit when no nodes were marked
      end loop
      if root is marked, then the indices help
   

   What traversal method would require only a single pass through the loop, for any parse tree, to determine whether or not the indices help answer Q?