Query Decomposition

Query Decomposition

Query decomposition transforms an SQL (relational calculus) query into relational algebra query. The steps in query decomposition are as follows:

• Normalization
• Analysis
• Elimination of Redundancy
• Rewriting

Normalization: In the process of normalization, input query can be complex. It performs lexical and syntactic analysis like compilers. It is also a treatment of WHERE clause. There are two possible forms of normalization and they are:

• Conjunctive NF: (p₁₁ vP₁₂v… vp_1n) ^ …. ^ (p_m1 vp_m2 v…. vp_mn)
• Disjunctive NF: (p₁₁ ^ p₁₂ ^ …. ^p_1n) v…. v(p_m1 ^ p_m2 ^ …. ^p_mn)

Transformation is based on equivalence rules. Example:

• SELECT eName FROM EMP, ASG
  WHERE EMP.eNo = ASG.eNo AND ASG.pNo = ‘P1’ AND
  dur = 12 OR dur = 24
• Qualification in Con NF
  eNo = ASG.eNo ^ ASG.pNo = ‘P1’ ^ (dur = 12v dur = 24)
• Qualification in Dis NF
  (EMP.eNo = ASG.eNo ^ ASG.pNo = ‘P1’ ^ dur = 12)

v (EMP.eNo = ASG.eNo ^ ASG.pNo = ‘P1’ ^ dur = 12)

Analysis: It rejects the incorrect ones. The incorrect types may be that the relations or attributes do not exist and the wrong operations. There may be the possibility of semantically incorrect ones such as:

• Components do not contribute to the result.
• Detection possible in certain cases which does not contain disjunction or negation.
• Query graph and join graph

Elimination of Redundancy: This refers to the replacement of expression that is already used in views. User mistake or this replacement may contain redundant predicates. Simplification of idempotency rules are:

• p ^ p ↔ p p ∨ p↔ p
• p ^ true↔ p p∨ false ↔ p
• p ^ false ↔ false
• p ∨ true ↔ true p ∨ ¬p ↔ true

Rewriting: It is the process of transforming SQL to Relational Algebra straightaway. Rewriting is also referred to as restructuring operators to improve efficiency. Operator tree is used for the following:

• Leaf nodes are operand relations.
• Non leaf are intermediate tables produced as a result of some relational operators
• Example Select eName
  FROM EMP, ASG, PROJ
  WHERE EMP.eNo = ASG.eNo
  AND ASG.pNo = PROJ.pNo
  AND eName≠ 'Saleem'
  AND pName = 'CAD/CAM'
  AND (dur = 36 or dur = 24)

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.