Gujarat Technological University 2009 M.C.A Semeter I - Question Paper

Semester I

Seat No.    Enrolment No.

GUJARAT TECHNOLOGICAL UNIVERSITY

MCA Sem-I Examination January 2010

Subject code: 610005 Subject Name: Database Management Systems-I

Date: 28 / 01/ 2010    Time: 12.00 -2.30pm

Total Marks: 70

Instructions:

1.    Attempt all questions.

2.    Make suitable assumptions wherever necessary.

3.    Figures to the right indicate full marks.

Q.1 (a) Compare and contrast two-tier and three-tier database architecture. Also 07 explain the types of database users and the role of a database administrator.

(b) What are the advantages and disadvantages of providing secondary indexes 07 and primary indexes? How does multilevel indexing improve the efficiency of searching an index file?

Q.2 (a) A university registrars office maintains data about the following entities : 07

(a) courses, including number, title, credits, syllabus, and prerequisites; (b) course offerings, including course number, year, semester, section number, instructor(s) timings, and classroom; (c) students, including student-id, name, and program; and (d) instructors, including identification number, name, department, and title. Further, the enrollment of students in courses and grades awarded to students in each course they are enrolled for must be appropriately modeled. Construct an E-R diagram for the registrars office. Document all assumptions that you make about the mapping constraints.

(b) Define the concept of aggregation in E-R model. Give two examples where 07 aggregation is useful.

OR

(b) State Armstrongs axioms to find logically implied functional dependencies. 07 Use these axioms to prove the soundness of the decomposition rule.

Distinguish between data manipulation languages and data definition 07 languages giving suitable examples.

OR

What do you understand by repetition of information and inability to represent information ? Explain why each of these properties may indicate a bad relational database design.

Distinguish between a weak entity set and a strong entity set. Explain how a weak entity set can be converted into a strong entity set and how it can participate in relationships, giving suitable examples.

Explain the difference between physical and logical data independence. Suppose that we decompose the schema R = (A, B, C, D, E) into (A, B, C) and (A, D, E). Show that this decomposition is a lossless decomposition if the following set F of functional dependencies holds : A BC, CD E, B D and E A. Also, give a lossless, dependency-preserving decomposition into 3NF of schema R.

OR

Q.4 (a) Compare and contrast the different types of constraints and generalizations. (b) Compare the terms primary key, candidate key and super key, giving suitable examples. Also, explain the mapping cardinalities that can exist between two entity sets in a binary relationship.

Q.5 (a) What is UML ? Explain the parts of UML ? Show the UML class diagram notations for its equivalent E-R diagram constructs.

(b) Distinguish between a file-processing system and a database management system.

OR

Q.5 (a) Define the constraint multivalued dependency. Explain fourth normal form (4NF). Why is 4NF more desirable than BCNF ?

(b) Distinguish between entity sets and relationship sets. Also, compare binary relationship sets and n-ary relationship sets.

2

Seat No.    Enrolment No.

GUJARAT TECHNOLOGICAL UNIVERSITY

MCA Sem-I Examination January 2010

Subject code: 610003

Subject Name: Discreet Mathematics for Computer Science Date: 21 / 01/ 2010    Time: 12.00 -2.30 pm

Total Marks: 70

Instructions:

1.    Attempt all questions.

2.    Make suitable assumptions wherever necessary.

3.    Figures to the right indicate full marks.

Q.1 (a) Define Boolean expression. Show that

[a * (b c)] * [b (a * c)] = a * b * c

Define Symmetric Boolean expression. Determine whether the 07 following functions are symmetric or not:

(i)    abc + acd + abcd + abcd

(ii)    abc + abc + abc + abc + abc + abc

Q.2 (a) Define Universal quantifier and Existential quantifier.    07

(i) Express the following sentences into logical expression using First Order Predicate Logic:

All lines are fierce

Some student in this class has got university rank

Show the following implication without constructing the truth tables first and thereafter show it through the truth tables.

(P Q) Q => (P v Q)

(b) Define equivalence relation.    07

Let Z be the set of integers and R be the relation called Congruence modulo 5 defined by

R = {<x,y> | xe Z a y e Z a (x - y)is divisible by 5}

Show that R is an equivalence relation. Determine the equivalence classes generated by the elements of Z.

OR

(b) Define compatibility relation and maximal compatibility block. Let 07 the compatibility relation on a set (x₁, x₂,...., x₆} be given by the matrix

x2	1
x3	1	1
x4	0	0	1
x5	0	0	1	1
x6	1	0	1	0	1
	x1	x2	x3	x4	x5

Draw the graphs and find the maximal compatibility blocks of the relation.

Define Composite relation and Converse of a relation.

Given the relation matrix M_R of a relation R on the set {a, b, c}, find the relation matrices of ~R (Converse of a R),

R² = R o R and R o ~R.

m_r = fi 0 i 1 1 0 i i i ,

(b) Prove the following Boolean Identities:

(i)    a (a b')' = a b

(ii)    a *(a * b')' = a * b

(c) Find the six left cosets of H = {p₁, p₅, p₆} in the group (S₃, *}, given in the following table:

* Pi P2 P3 P4 P5 P6

pi	pi	p2	p3	p4	p5	p6
p2	p2	pi	p5	p6	p3	p4
p3	p3	p6	pi	p5	p4	p2
p4	p4	p5	p6	pi	p2	p3
p5	p5	p4	p2	p3	p6	pi
p6	p6	p3	p4	p2	pi	p5

OR

(i)    Define Partial order relation and Chain.

(ii)    The following figure gives the Hesse diagram of a partially ordered

set <P, R>, where P = {x_i, x₂, x₃, x₄, x₅}.

Find which of the following are true:

x_i R x₂, x₄ R x_i, xi R x_i, and x₂ R x₅. Find the upper and lower bounds

of {X2, X3, X4}, {X3, X4, X5}, {Xi, X2, X3}

(b)    Show that    04

(i)    a + 0 = a

(ii)    a +1 = a'

(iii)    a + a = 0

(iv)    a + a' = i

where a + b = (a * b') (a' * b)

(c)    Show that (S₃, *} as given in the above table [i.e. Q.3(c) main part] is a 03 group. [Note: Only one non-trivial example to show associativity will be sufficient.

Define Group, Order of a group, and Abelian Group.    07

For P = { p₁, p₂,.... p₅} and Q = { q₁, q₂,...., q₅} explain why (P, *) and <Q, A > are not groups. The operations * and A are given in the following table:

*    pi p2 p3 p4 p5 A qi q2 q3 q4 q5 pi pi p2 p3 p4 p5 qi q4 qi q5 q3 q2 p2 p2 pi p4 p5 p3 q2 q3 q5 q2 qi q4

p3 p3 p5 pi p2 p4 q3 qi q2 q3 q4 q5 p4 p4 p3 p5 pi p2 q4 q2 q4 qi q5 q3 p5 p5 p4 p2 p3 p4 q5 q5 q3 q4 q2 qi

Define Lattice as an Algebraic System, Direct Product of Lattices 07 and Complete Lattice.

Let the sets S₀, S_i,.................., S₇ be given by

S₀ = {a, b, c, d, e, f}, S_i = {a, b, c, d, e}, S₂ = {a, b, c, e, f}, S₃ = {a, b, c, e}, S₄ = {a, b, c}, S₅ = {a, b}, S₆ = {a, c},

S7 = {a}

Draw the diagram of <L, e >, where L = {S₀, S_i, S₂,........., S₇}

OR

Define Subgroup, Group Isomorphism, and Kernel of the 07 homomorphism.

Show that the groups <G, *> and <S, A > given by the following table are isomorphic.

*    pi p2 p3 p4 A qi q2 q3 q4

pi	pi	p2	p3	p4	qi	q3	q4	qi	q2
p2	p2	pi	p4	p3	q2	q4	q3	q2	qi
p3	p3	p4	pi	p2	q3	qi	q2	q3	q4
p4	p4	p3	p2	pi	q4	q2	qi	q4	q3

Define Sub Lattice, Lattice homomorphism and Distributive 07 Lattice.

Find all the sub lattices of the lattice <S_n, D) for n = i2, i.e. the lattice of divisors of i2 in which the partial ordering relation D means division.

Define Directed Graph, Cycle, Path, In degree, Binary Tree    05

Can we say that any square Boolean Matrix will definitely represent a 05 directed graph? What does a 4x4 unit matrix represent?

Draw the graph corresponding to the following Boolean Matrix:

0 i 0 0 0

0 0 i i 0 0 0 0 i i i 0 0 0 i 0 0 0 0 0

-J

How many (>=0) cycles does this graph have? Write down all the cycles. Which single edge is to be deleted to convert this graph into a cyclic graph?

(^c) From the adjacency matrix of a simple digraph, how will you determine 04 whether it is a directed tree? If it is a directed tree, how will you determine its root and terminal nodes?

OR

Q.5 (a) Define Graph, Loop, Out Degree, Tree, Node Base    05

6

Also find its unilateral components. Give brief valid reasons/justification for your answer.

(c) Define complete binary tree. Show through two examples with n_t = 7 04 and n_t = 8 of complete binary trees that the total number of edges is given by 2(n_t - 1), where n_t is the number of terminal nodes.

*************

4

Attachment: gujarat-technological-university-2009-m-c-a--53313-1.pdf gujarat-technological-university-2009-m-c-a--53313-2.pdf

Earning:   Approval pending.