BTCOC501 Database Systems
[Unit 1] 6 Hrs
Database system architecture: Data Abstraction, Data Independence, Data Definition
Language (DDL), Data Manipulation Language (DML).
Data models: Entity-relationship model, Relational integrity constraints, data manipulation
operations.
[Unit 2] 6 Hrs
Relational query languages: Relational algebra, Tuple and domain relational calculus,
SQL3, DDL and DML constructs, Open source and Commercial DBMS – MYSQL,
ORACLE, DB2, SQL server.
[Unit 3] 6 Hrs
Relational database design: Domain and data dependency, Armstrong's axioms, Normal
forms, Dependency preservation, Lossless design.
[Unit 4] 6 Hrs
Query processing: Evaluation of relational algebra expressions, Query equivalence, Join
strategies.
[Unit 5] 6 Hrs
File Organization and Indexing: Indices, B-trees, hashing.
[Unit 6] 6 Hrs
Transaction processing: Concurrency control, ACID property, Serializability of scheduling,
Locking and timestamp based schedulers, Multi-version and optimistic Concurrency Control
schemes, Database recovery.
Text Books:
Henry Korth, Abraham Silberschatz & S. Sudarshan, Database System Concepts,
McGraw-Hill Publication, 6th Edition, 2011.
Reference Books:
J. D. Ullman, “Principles of Database and Knowledge – Base Systems”, Vol 1,
BTCOC502 Theory of Computations
[Unit 1] 6 Hrs
Finite Automata and Regular Expressions: Definition of deterministic finite automata,
Non-deterministic finite automata, Moore and Mealy machines and their conversions, Regular
expressions, Recursive definition, NFA with e-moves, Inter-conversion between NFA and
DFA, Regular expression and FA, Pumping lemma.
[Unit 2] 6 Hrs
Context Free Grammars: Definition, Production rules, Ambiguous grammar, Removal of
ambiguity, Chomsky hierarchy, Context Free Grammar (CFG) – definition, Simplification of
CFG.
[Unit 3] 6 Hrs
Context Free Languages: Definition of context free languages, Regular grammar definition,
Left linear, Right linear grammar, Inter-conversion between left linear and right linear regular
grammar, Regular grammar and finite automata, CNF, GNF, Derivation graphs, Type 0 and
Type 1 grammars.
[Unit 4] 6 Hrs
Pushdown Automata: Formal definition, Pushdown automata (PDA), Deterministic
Pushdown automata (DPDA) – definition, Non-deterministic Pushdown automata (NPDA) -
definition, relative powers of DPDA and NPDA.
[Unit 5] 6 Hrs
Turing Machines and Undecidability: Definition, Computing with Turing machine,
Extensions of Turing machines, Random access Turing machines, Non-deterministic Turing
machines, Grammars, The Church’s Turing hypothesis, Universal Turing machines, The
Halting problem, Unsolvable problems about Turing machines.
Reference Books:
1. John C. Martin, Introduction to Languages and Theory of Computation, McGrawHill Publication, 4th Edition, 2010.
2. Krithivasan Kamala, Introduction to Formal Languages, Automata Theory and
Computation, Pearson Education, 1st Edition, 2009.
3. Papadimitriou, Lewis, Elements of the Theory of Computations, PHI Publication,
2
nd Edition, 1997.
4. E. V. Krishnmurthy, Introductory Theory of Computer Science, Springer-Velang
New York Inc., 1st Edition, 1985.
Text Books:
1. Hopcroft, Ullman, Motwani, Introduction to Automata Theory, Languages, and
Computation, Addison Wesley Publication, 2nd Edition, 2001.
2. Daniel I. A. Cohen, Introduction to Computer Theory, Wiley Publication, 1st Edition,
1986.