hamburger

Important Formula Notes of DBMS for GATE & Computer Science Engineering Exams

By BYJU'S Exam Prep

Updated on: September 25th, 2023

Here is the list of important formulas which can be used in a Database Management System.

Number of Online Classroom Program Keys

Let n be the number of attributes in a particular relation. let A be the candidate key for that relation than, No of Online Classroom Program Keys= 2n-1

Here is the list of important formulas which can be used in a Database Management System.

Number of Online Classroom Program Keys

Let n be the number of attributes in a particular relation. let A be the candidate key for that relation than, No of Online Classroom Program Keys= 2n-1

Normal Forms

  • First Normal Form: A relation is in first normal form if it does not contain any multi-valued or composite attribute.
  • Second Normal Form: A relation is in second normal form if it does not contain any partial dependency. A dependency is called partial dependency if any proper subset of candidate key determines non-prime (which are not part of candidate key) attribute.
  • Third Normal Form: A relation is in third normal form if it does not contain any transitive dependency. For a relation to be in Third Normal Form, either LHS of FD should be Online Classroom Program key or RHS should be prime attribute.
  • Boyce-Codd Normal Form: A relation is in Boyce-Codd Normal Form if LHS of every FD is Online Classroom Program key.

    The relationship between Normal Forms can be represented as:  

1NF⊂2NF⊂3NF⊂BCNF

 

Mapping Constraints

Let R1 and R2 be two entity set which are related to each other through relation R following some mapping constraint.

Mapping Constraints No of tables required
One to One with partial participation 2
One to One with total participation of atleast one table 1
Many to One  2
Many to Many 3

Cardinalities

Let R and S be two relations with n and m distinct tuples respectively, than, the cardinality for the given operation will be

Operation Cardinality
R×S n*m tuples
R⋈S 0 to nm tuples
RCS 0 to nm tuples
RS n to nm tuples
RS m to nm tuples
RS max(m,n) to mn tuples
R∪S max(m,n) to m+n tuples
R∩S 0 to min(m,n) tuples
R-S 0 to n tuples
R/S 0 to n/m tuples

Formula Over Indexing

  • Block Factor: Maximum possible records per block.
  •  B/B+ tree:
    • Calculating Best Possible order:
      • B tree node: Let P be the order of the given node i.e. Maximum No of pointers per node, than, P*BP+ (P-1)[RP+ key]<= Block Size
      • B+ tree node: For Internal Nodes: P*BP+ (P-1)[RP+ key]<= Block Size

     For External/Leaf Nodes: BP+ (P-1)[RP+ key]<= Block Size

Where, BP= Block Pointer Size,

           RP= Record Pointer Size, and

           Key= Size of key

Serializability and Recoverability

Serializability: It is of two types: 

  • Conflict Serializability
  • View Serializability

Conflict Serializability: A schedule is conflict serializable if it is conflict equivalent to a serial schedule.

Conflict Pairs: Two operations are said to be conflicting if all conditions satisfy:

  • They belong to different transaction.
  • They operation on same data item.
  • At Least one of them is a write operation.

Checking For Conflict Serializability:

  • To check whether a schedule is conflict serializable or not, find all conflicting operations pairs of a schedule and draw precedence graph.
  • For all conflicting operation pair, an edge from Ti to Tj if one operation of conflicting pair is from Ti and other from Tj and operation of Ti occurs before Tj in schedule.
  • If graph does not contain cycle, the schedule is conflict serializable else it is not conflict serializable.

Conflict Equivalent Schedule: Schedules are said to be conflict equivalent if 1 schedule can be converted into another by swapping non conflicting operations.

View Equivalent Schedules: Two schedules S1 and S2 are said to be view-equivalent if all conditions are satisfied for all objects:

  • If the transaction Ti in S1 reads an initial value for object X, in S2 also, Ti must read the initial value of X.

  • If the transaction Ti in S1 reads the value written by transaction Tin S1 for object X, same should be done in S2.

  • If the transaction Ti in S1 is the final transaction to write the value for an object X, in S2 also, Timust write the final value of X.

View Serializable Schedule: A schedule is view serializable if it is view equivalent to any serial schedule.

Recoverability:

Irrecoverable Schedules: For a transaction pair < Ti, Tj >, if Tj is reading the value updated by Ti and Tj is committed before commit of Ti, the schedule will be irrecoverable.

Recoverable Schedules: For a given transaction pair of  < Ti, Tj >, if Tj is reading the value which is updated by Ti and Tj is committed after commit of Ti, then the schedule will be recoverable.

Cascadeless Recoverable Schedules: For a given transaction pair < Ti, Tj >, if value updated by Ti is read by Tj only after the commit of Ti, the schedule will be cascadeless recoverable schedule.

Strict Recoverable: For every transaction pair < Ti, Tj >, if value updated by Ti is read or write by Tj only after commit of Ti, the schedule will be strict recoverable. The relationship between them can be represented as:

Strict Recoverable  Cascadeless Recoverable ⊂ Recoverable Schedule  Schedule

Two Phase Locking: A transaction following Locking and Unlocking phenomenon in below given two phases is said to Two Phase Locking.

  • Growing Phase: New locks on data items may be acquired but none can be released.
  • Shrinking Phase: Existing locks may be released but no new locks can be acquired.

Problem caused by 2PL: Two-phase locking guarantees serializability of the schedule but causes

  • Starvation
  • Deadlock

Variations of Two-Phase Locking: The solution to these problems is provided by making some variations in the two-phase locking:

  • Conservative 2PL: The difference between 2PL and conservative 2PL is that C2PL’s transactions obtain all the locks they need before the transactions begin. This is to ensure that a transaction that already holds some locks will not block waiting for other locks. Conservative 2PL prevents deadlock.
  • Strict 2PL: The first phase of Strict-2PL is same as 2PL. After acquiring all the locks in the first phase, the transaction continues to execute normally. But in contrast to 2PL, Strict-2PL does not release a lock after using it. Strict-2PL holds all the locks until the commit point and releases all the locks at a time.

 

You can follow the detailed champion study plan for GATE CS 2022 from the following link:

Detailed GATE CSE 2022 Champion Study Plan

Candidates can also practice 112+ Mock tests for exams like GATE, NIELIT, BARC with BYJU’S Exam Prep Test Series check the subsequent link:

Click Here to Avail GATE CSE Test Series!(112+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Thanks

Our Apps Playstore
POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com
Home Practice Test Series Premium