This test is closed book. Do all parts of all questions. Do question 1 and any other two questions. If you do more than three questions, you will be graded on question 1 and the best two of the others. When you do a question, answer all parts. Please follow these guidelines:
e --> e OR t | t t --> tf | f f --> p* | p+ | p p --> (e) | OPERANDwhere
OR and OPERAND are terminal symbols.
Make this grammar LL(1) by removing left recursion and other operations if
needed.
Consider the following program:
1 program Main(input, output); 2 3 var 4 Size : integer; 5 6 procedure Outer(Size : integer); 7 type 8 ArrayType = array [1 .. Size] of integer; 9 10 procedure Inner(Size : integer); 11 var 12 MyArray : ArrayType; 13 begin (* Inner *) 14 MyArray[10] := Size; 15 end; (* Inner *) 16 17 begin (* Outer *) 18 if Size < 10 then 19 Outer(Size*2) 20 else 21 Inner(Size/2); 22 end; (* Outer *) 23 24 begin (* Main *) 25 Outer(2); 26 end.
Size does the compiler use: the one
in line 4, line 6, or line 10?
MyArray when execution reaches line 14 for the
first time? (The length will determine if the subscript 10 is valid.)
Conventional computers use main memory (RAM) and disk to store file system data. However, a new technology called NVRAM (which stands for Non-volatile RAM) is becoming cheap and is being used in addition to RAM and disks. NVRAM is just like RAM except that: (1) it takes a little more time to access data in NVRAM than RAM. (2) NVRAM does not lose data if the power goes off or if the machine reboots. Unfortunately, NVRAMs are still quite small (tens of MB).
How might you change the file system in an operating system to make use of NVRAM and disk? Be as specific as possible, and justify your suggestions. Many different answers are ``correct'' if you can justify them.
|
v
4-way
-> stop <-
sign
^
|
{A, B, C, D, E, F, G}.
A through G are the attributes of our table.
The set F of functional dependencies is given by:
F =B C D --> A
B C --> E
A --> F
F --> G
C --> D
A --> G
(a) Find a minimal cover for this set of functional dependencies.
(b) Starting with a table T that contains all the attributes above,
form a lossless decomposition of T into two tables that make up a
2NF decomposition. Carefully, list the candidate keys of T
and of each decomposition.
c) Continue the decomposition to make the database 3NF. Is your
decomposition BCNF? Justify your answer.