Give an algorithm for testing whether a relation scheme is in BCNF. The algorithm should be polynomial in the size of the set of given FDs. (The size is the sum over all FDs of the number of attributes that appear in the FD.) Is there a polynomial algorithm for testing whether a relation scheme is in 3NF?

Give an algorithm for testing whether a relation scheme is in BCNF. The algorithm should be polynomial in the size of the set of given FDs. (The size is the sum over all FDs of the number of attributes that appear in the FD.) Is there a polynomial algorithm for testing whether a relation scheme is in 3NF?

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

i need the answer quickly
write this in relation algebra: SELECT s.sname FROM student s, reservation r WHERE s.sid!=r.sid
Suppose we have the table Employee[id, name, supervisor] This table implements an employee entity type and the relationship "a person has a supervisor", similar to the Company database. Even if we have referential integrity it is possible for us to have corrupt data. Consider two cases: • we could have data where an employee is their own supervisor (last row below), or • where the supervisor of A is B but B shows its supervisor to be A (first two rows belov. id supervisor A B C D name John Joyce Jim Jennifer Peter null Write an SQL statement to list any rows with the type of bad data as outlined in the above.
The division operator of relational algebra, “÷”, is defined as follows. Let r(R)and s(S) be relations, and let S ⊆ R; that is, every attribute of schema S isalso in schema R. Given a tuple t, let t[S] denote the projection of tuple t onthe attributes in S. Then r ÷ s is a relation on schema R − S (that is, on theschema containing all attributes of schema R that are not in schema S). A tuplet is in r ÷ s if and only if both of two conditions hold:• t is in ΠR−S(r)• For every tuple ts in s, there is a tuple tr in r satisfying both of the following:a. tr[S] = ts[S]b. tr[R − S] = tGiven the above definition:a. Write a relational algebra expression using the division operator to findthe IDs of all students who have taken all Comp. Sci. courses. (Hint:project takes to just ID and course id, and generate the set of all Comp.Sci. course ids using a select expression, before doing the division.)b. Show how to write the above query in relational algebra, without usingdivision. (By doing so, you…
Consider the relation prereg in the University Database and its transitive closure defined in Section 5.4 of the textbook. Consider the recursive query in Figure 5.16 that outputs this transitive closure. Write a recursive query that finds all direct or indirect prerequisite of BIO-301. Output a table with one column that contains the IDs of all such prerequisites. Note that your query must work correctly not only for the given instance of prereg, but also for all possible instances. Run this query.
Consider a relation schema R = (X, Y, Z) on which the following functional dependencies hold: {XYZ, Z-X}. Show that the schema R is not in BCNF (Boyce-Codd Normal Form) but it is in 3NF (Third Normal Form).
Select all binary relation properties that apply to the following relation: Equal magnitude: |x| = lyl O antisymmetric O reflexive O symmetric O transitive
Decompose the relations, as necessary, into collections of relations that are in BCNF. R(A,B,C,D) with FD’s AB->C,C->D,and D->A. Could you show step by step procedure for this with detailed explaination?
Explain aproximiation and how it can be achieved by fuzzy relation with simple example
In Discrete Math
1.A known relationship mode of R (U, F), U= (A, B, C, D, E, G); F={AB->C, D->EG,C->A, BE->C, BC->D, CG->BD, ACD->B, CE->AG}; find the minimum cover of F,then use the Normal Form decomposition algorithm to decompose this mode to 3NF, andcheck if the decomposition has the nonadditive join property.
Given: Relation R = {(a,a), (a.b), (b,a). (b,b). (c,c)} and Set S = {a, b, c} Complete Relation R to be Transitive with Set S