Show that the iterative process of computing the transitive closure of Prereq terminates after a ?nite number of steps. Show that this process can compute the transitive closure in polynomial time.
What will be an ideal response?
A recursive de?nition of IndirectPrereqView can be viewed as an operator, T(X ), which computes a relational algebra expression that involves X and some other, constant relations. For any X , T(X ) is a relation whose tuples consist of constants that appear in X and in the other constant relations that are used by T .
The computation starts by computing T(?), then T(T(?)), etc. First, it is easy to see from the form of the de?nition of indirectPrereqView that T is a monotone operator, i.e., if X ? Y then T(X ) ? T(Y ). Since ??T(?), it is easy to see that
??T(?) ? T(T(?)) ? ...
Let us denote the nth application of T by Tn(?). Due to an earlier observation, the tuples in Tn(?) must be composed only of the constants that appear in the constant relations that are part of T .Thus, the relation Tn(?) cannot grow inde?nitely and for some m we must have Tm+1(?)=Tm(?), and the computation can stop there.
To see how this computation can be done in polynomial time, observe that T(X1? X2)=T(X1) ? T(X2). Thus, the above computation can be modi?ed as follows. Let us extend the de?nition of Tn with T1(?)=T(?) and T0(?)=?.
?0 = ?
S0 = ?
?1 = T(?0) - S0
S1 =?1 ? S0
?2 = T(?1) - S1
S2 = ?2 ? S1
... ... ...
?n = T (?n-1) - Sn-1
Sn = ?n ? Sn-1
... ... ...
The computation terminates when ?k = ? for some k . The number of steps in the above computation is bounded by the maximal number of tuples in Tn(?) (because at each step we must add at least one tuple), and is polynomial (it is bounded by
the number of rows in the Cartesian product of all columns of all constant relations in T . Each step in the above computation is also polynomial, because it consists of a join followed by a set-di?erence operator. Thus, the total time complexity of this
computation is polynomial.
You might also like to view...
Any construct that allows you to cycle through all the items in a container is called:
a. Pointer b. Instance variable c. Iterator d. All of the above
When capturing live memory from a computer system what is meant by the term footprint?
a. The amount of free space on the targe medium required for the copy being made. b. The amount of memory on the target system required by the software tools being used to capture memory. c. Memory content variable caused by the fact RAM is constantly changing while the system memory is being imaged. d. The I/O port required by the device acquiring the memory.
Which of the following requirements is part of the maintain a vulnerability management program PCI DSS core principle?
A. Install and maintain firewall configuration to protect cardholder data. B. Develop and maintain secure systems and applications. C. Protect all systems against malware and regularly update antivirus software. D. Encrypt transmission of cardholder data across open, public networks.
Attempting to access an array element out of the bounds of an array causes a(n) ________.
a) ArrayOutOfBoundsException. b) ArrayElementOutOfBoundsException. c) IndexOutOfRangeException. d) ArrayException.