{"id":79,"date":"2018-07-18T10:22:11","date_gmt":"2018-07-18T10:22:11","guid":{"rendered":"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=79"},"modified":"2018-08-01T08:42:07","modified_gmt":"2018-08-01T08:42:07","slug":"normalisation","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/chapter\/normalisation\/","title":{"rendered":"Normalisation"},"content":{"raw":"Anomalies in DBMS<\/strong>\r\n\r\n \r\n

There are three types of anomalies that occur when the database is not normalized. These are \u2013 Insertion, update and deletion anomaly. Let\u2019s take an example to understand this.<\/p>\r\n \r\n

Example<\/strong>: Suppose a manufacturing company stores the employee details in a table named employee that has four attributes: emp_id for storing employee\u2019s id, emp_name for storing employee\u2019s name, emp_address for storing employee\u2019s address and emp_dept for storing the department details in which the employee works. At some point of time the table looks like this:<\/p>\r\n\"\"\r\n

\r\n

The above table is not normalized. We will see the problems that we face when a table is not normalized.<\/p>\r\n \r\n

Update anomaly<\/strong>: In the above table we have two rows for employee Rick as he belongs to two departments of the company. If we want to update the address of Rick then we have to update the same in two rows or the data will become inconsistent. If somehow, the correct address gets updated in one department but not in other then as per the database, Rick would be having two different addresses, which is not correct and would lead to inconsistent data.<\/p>\r\n \r\n

Insert anomaly<\/strong>: Suppose a new employee joins the company, who is under training and currently not assigned to any department then we would not be able to insert the data into the table if emp_dept field doesn\u2019t allow nulls.<\/p>\r\n \r\n

Delete anomaly<\/strong>: Suppose, if at a point of time the company closes the department D890 then deleting the rows that are having emp_dept as D890 would also delete the information of employee Maggie since she is assigned only to this department.<\/p>\r\n \r\n

To overcome these anomalies we need to normalize the data. In the next section we will discuss about normalization.<\/p>\r\n \r\n

A functional dependency is an association between two attributes of the same relational database table. One of the attributes is called the determinant and the other attribute is called the determined. For each value of the determinant there is associated one and only one value of the determined.<\/p>\r\n

If A is the determinant and B is the determined then we say that A functionally determines B<\/em> and graphically represent this as A -> B. The symbols A \u00e0 B\u00b7 can also be expressed as B is functionally<\/em> determined by <\/em>A.<\/p>\r\n\r\n<\/div>\r\nExample<\/strong>\r\n\r\n \r\n

\"\"<\/p>\r\n \r\n

Functional dependency can also be defined as follows:An attribute in a relational model is said to be functionally dependent on another attribute in the table if it can take only one value for a given value of the attribute upon which it is functionally dependent.<\/p>\r\n \r\n\r\nExample: <\/strong>Consider the database having following tables:\r\n\r\n \r\n

\"\"<\/p>\r\n\r\n

\r\n\r\n \r\n\r\n<\/div>\r\n
<\/div>\r\n
\r\n\r\n\u00a0 \u00a0 Sno-<\/strong>Supplier number of supplier that is unique<\/strong>\r\n\r\nSname-Supplier name<\/strong>\r\n\r\nCity-<\/strong>City of the supplier<\/strong>\r\n\r\nStatus-<\/strong>Status of the city e.g. A grade cities may have status 10, B grad cities\u00a0<\/strong>may\u00a0<\/strong>have status 20 and so on.<\/strong>\r\n\r\n \r\n\r\nHere, Sname is FD on Sno. Because, Sname can take only one value for the given value of Sno (e.g. S<\/span>\r\n\r\n1) or in other words there must be one Sname for supplier number <\/span>\r\n\r\nS1. FD is represented <\/span>\r\n\r\nas:\u00a0<\/span>Sno \u00e0 Sname<\/span>\r\n\r\nFD is shown by \u00e0 which means that Sname is functionally dependent on Sno.<\/span>\r\n\r\nSimilarly, city and status are also FD on Sno, because for each value of Sno there will be only one city and status.<\/span>\r\n\r\n \r\n\r\nFD is represented as:\r\n\r\nSno\u00a0\u00a0 - City\r\n\r\nSno\u00a0\u00a0 - Status\r\n\r\nsno - S (Sname, City, Status)<\/span>\r\n\r\n \r\n\r\nConsider another database of shipment with following attributes:\r\n\r\n<\/div>\r\nSno-Supplier number of the supplier\r\n\r\nPno-Part number supplied by supplier\r\n\r\nQty-Quantity supplied by supplier for a particular Part no\r\n
\r\n\r\nIn this case Qty is FD on combination of Sno, Pno because each combination of Sno and Pno results only for one Quantity.\r\n\r\n \r\n\r\nSP (Sno, Pno) --> SP.QTY\r\n\r\n \r\n\r\nDependency Diagrams<\/strong>\r\n\r\n \r\n\r\nA dependency diagram consists of the attribute names and all functional dependencies in a given table.\r\n\r\nThe dependency diagram of Supplier table is.\r\n

\"\"<\/p>\r\n \r\n\r\nHere, following functional dependencies exist in supplier table\r\n\r\n-\u00a0 Sname\r\n\r\nSname\u00a0\u00a0\u00a0\u00a0\u00a0 -\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Sno\r\n\r\nSno -\u00a0 \u00a0 \u00a0 \u00a0 City\r\nSno - Status\r\nSname - City\r\nSname - Status\r\nCity - Status\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
Sno<\/td>\r\nSname<\/td>\r\n<\/tr>\r\n
Sname<\/td>\r\nSno<\/td>\r\n<\/tr>\r\n
Sno<\/td>\r\nCity<\/td>\r\n<\/tr>\r\n
Sno<\/td>\r\nStatus<\/td>\r\n<\/tr>\r\n
Sname<\/td>\r\nCity<\/td>\r\n<\/tr>\r\n
Sname<\/td>\r\nStatus<\/td>\r\n<\/tr>\r\n
City<\/td>\r\nStatus<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nThe FD diagram of relation P is\r\n

\"\"<\/p>\r\nHere following functional dependencies exist in Part table:\r\n\r\n \r\n\r\nPno - Pname\r\n\r\nPno - Color\r\n\r\nPno - Wt\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n

The FD diagram of relation Shipment is\u00a0Here following functional dependencies exist in parts table SP (Sno, Pno) - SP.QTY<\/span><\/p>\r\n\r\n<\/div>\r\nFully Functional Dependence (FFD)<\/strong>\r\n\r\n \r\n

Fully Functional Dependence (FFD) is defined, as Attribute Y is FFD on attribute\" X, if it is FD on X and not FD on any proper subset of X. For example, in relation Supplier, different cities may have the same status. It may be possible that cities like Amritsar, Jalandhar may have the same status 10.<\/p>\r\nSo, the City is not FD on Status.\r\n\r\n \r\n\r\nSo, the City is not FD on Status.\r\n

But, the combination of Sno, Status can give only one corresponding City ,because Sno\" is unique. Thus,<\/p>\r\n

(Sno, Status) \u00e0 City<\/p>\r\n

It means city is FD on composite attribute (Sno, Status) however City is not fully functional dependent on this composite attribute, which is explained below:<\/p>\r\n(Sno, Status) \u00e0 City\r\n\r\n \r\n\r\nX\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Y\r\n\r\n \r\n\r\nHere Y is FD on X, but X has two proper subsets Sno and Status; city is\u00b7 FD .on one proper subset .of X i.e. Sno\r\n\r\n \r\n\r\nSno \u00e0 City\r\n\r\n \r\n

According to 'FFD definition Y must not be FD .on any proper subset of X, but here City is FD in one subset .of X i.e. Sno, so City is not FFD on (Sno, Status)<\/p>\r\n \r\n\r\nConsider another case of SP table:\r\n\r\nHere, Qty is FD on combination of Sna, Pno.\r\n\r\n \r\n\r\n(Sno, Pno)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00e0\u00a0\u00a0\u00a0\u00a0\u00a0 Qty\r\n\r\n \r\n\r\nX\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Y\r\n\r\n \r\n

Here, X has two proper subsets Sno and Pna<\/p>\r\n

Qty is not FD on Sno, because one Sna can supply mare than .one quantity.<\/p>\r\n

Qty is also not FD on Pno, because .one Pna may be supplied many times by different suppliers with different .or same quantities.<\/p>\r\n

So, Qty is FFD and composite attribute of (Sno, Pno) \u00e0 Qty.<\/p>\r\n \r\n\r\nOther Functional Dependencies<\/strong>\r\n\r\n \r\n

There are same rather types of functional dependencies, which play a vital rule during the process .of normalization of data.<\/p>\r\n \r\n\r\nCandidate Functional Dependency<\/strong>\r\n\r\n \r\n

A candidate functional dependency is a functional dependency that includes all attributes of the table. It should also be noted that a well-fanned dependency diagram must have at least one candidate functional dependency, and that there can be more than .one candidate functional dependency for a given dependency diagram.<\/p>\r\n \r\n\r\nPrimary Functional Dependency<\/strong>\r\n\r\n \r\n

A primary functional dependency is a candidate functional dependency that is selected to determine the primary key. The determinant of the primary functional dependency is the primary key of the relational database table. Each dependency diagram must have one and only on primary functional dependency. If a relational database table has .only .one candidate functional dependency, then it automatically becomes the primary functional dependency<\/p>\r\n \r\n

Once the primary key has been determined, there will be three possible types of functional dependencies:<\/p>\r\n \r\n\r\nDescription<\/strong>\r\n\r\n \r\n\r\nA \u00e0 B A key attribute functionally determines a non-key attribute.\r\n\r\nA \u00e0 B A non-key attribute functionally determines a non-key attribute.\r\n\r\nA \u00e0 B A non-key attribute functionally determines a key attribute.\r\n\r\n \r\n

A partial functional dependency<\/strong> is a functional dependency where the determinant consists of key attributes, but not the entire primary key, and the determined consist~ of non-key attributes.<\/p>\r\n \r\n\r\nA transitive functional dependency<\/strong> is a functional dependency where the determinant consists of non-key attributes and the determined also consists of non-key attributes.\r\n\r\n \r\n

A Boyce-Codd functional dependency<\/strong> is a functional dependency where the determinant consists of non-key attributes and the determined consists of key attributes.<\/p>\r\n \r\n

A Multi-Value Dependency (MVD)<\/strong> occurs when two or more independent multi valued facts about the same attribute occur within the same table. It means that if in a relation R having A, Band C as attributes, B and Care multi-value facts about A, which is represented as A \u00e0\u00e0B and A \u00e0\u00e0C ,then multi value dependency exist only if B and C are independent on each other.<\/p>\r\n \r\n\r\nA Join Dependency<\/strong> exists if a relation R is equal to the join of the projections X Z. where X, Y, Z projections of R.\r\n\r\n \r\n\r\nClosure of set of dependencies<\/strong>\r\n\r\n \r\n

Let a relation R<\/em> have some functional dependencies F<\/em> specified. The closure of F<\/em> (usually written as F<\/em>+) is the set of all functional dependencies that may be logically derived from F. <\/em>Often F <\/em>is the set of most obvious and important functional dependencies and. F<\/em>+, the closure, is the set of all the functional dependencies including F<\/em> and those that can be deduced from F.<\/em> The closure is important and may, for example, be needed in finding one or more candidate keys of the relation.<\/p>\r\n \r\n\r\nFor example, the student<\/em> relation has the following functional dependencies\r\n\r\n \r\n\r\nsno <\/em>\u00e0 Sname<\/em>\r\n\r\ncno <\/em>\u00e0 came<\/em>\r\n\r\nsno <\/em>\u00e0 address<\/em>\r\n\r\ncno <\/em>\u00e0 instructor<\/em>\r\n\r\nInstructor \u00e0 office<\/em>\r\n\r\n \r\n

\r\n

Let these dependencies be denoted by F.<\/em> The closure of F,<\/em> denoted by F<\/em> +, includes F<\/em> and all functional- dependencies that are implied by F.<\/em><\/p>\r\n \r\n

To determine F<\/em>+, we need rules for deriving all functional dependencies that are implied: by F.<\/em> A set of rules that may be used to infer additional dependencies was proposed by Armstrong in 1974. These rules (or axioms) are a complete set of rules in\u00b7 that all possible functional dependencies may be derived from them. The rules are:<\/p>\r\n \r\n\r\n1.\u00a0 <\/em>Reflexivity Rule - <\/em>If X <\/em>is a set of attributes and Y is a subset of X, <\/em>then X \u00e0Y <\/em>holds.\r\n\r\n \r\n

The reflexivity rule is the simplest (almost trivial) rule. It states that each subset of X<\/em> is functionally dependent on X.<\/em> In other words trivial dependence is defined as follows:<\/p>\r\n \r\n\r\nTrivial functional dependency<\/strong>: A trivial functional dependency is a functional dependency of an attribute on a superset of itself.\r\n\r\n \r\n

For example: <\/strong>{Employee ID, Employee Address} \u00e0 {Employee Address} is trivial, here {Employee\u00a0Address} is a subset of {Employee ID, Employee Address}.<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n \t
  1. Augmentation Rule - <\/em>If X \u00e0 Y <\/em>holds and W <\/em>is a set of attributes, and then WX \u00e0 WY <\/em>holds.<\/li>\r\n<\/ol>\r\n

    The argumentation ('u rule is also quite simple. It states that if Y<\/em> is determined by <\/span>X<\/em> then a set of attributes <\/span>W<\/em> and <\/span>Y<\/em> together will be determined by <\/span>W<\/em> and <\/span>X<\/em> together. Note that we use the notation <\/span>WX<\/em> to mean the collection of all attributes in <\/span>W<\/em> and <\/span>X<\/em> and write <\/span>WX<\/em> rather than the more conventional <\/span>(W,<\/em><\/p>\r\n\r\n

      \r\n \t
    1. X) <\/em>for convenience.<\/li>\r\n<\/ol>\r\n \r\n\r\nFor example<\/strong>: Rno - Name; Class and Marks is a set of attributes and act as\r\n\r\nThen\u00b7 {Rno, Class, Marks} -> {Name, Class, Marks}\r\n\r\n3. Transitivity Rule - <\/em>If X -> <\/em>Y and Y -> Z <\/em>hold, then X -> Z <\/em>holds.\r\n

      The transitivity rule is perhaps the most important one. It states that if X<\/em> functionally determines Y and Y functionally determine Z<\/em> then X<\/em> functionally determines Z.<\/em><\/p>\r\n \r\n\r\nFor example: <\/strong>Rno -> City and City -> Status, then Rno -> Status should be holding true.\r\n\r\n \r\n\r\nThese rules are called Armstrong's Axioms.<\/em>\r\n\r\n \r\n

      Further axioms may be derived from the above although the above three axioms are sound and<\/em> complete <\/em>in that they do not generate any incorrect functional dependencies (soundness) and they do generate all possible functional dependencies that can be inferred from F<\/em> (completeness). The most important additional axioms are:<\/p>\r\n\r\n

        \r\n \t
      1. Union Rule - <\/em>If X -> Y <\/em>and X -> Z <\/em>hold, then X -> YZ <\/em>holds.<\/li>\r\n \t
      2. Decomposition Rule - <\/em>If X \u00e0 YZ <\/em>holds, then so do X \u00e0 Y <\/em>and X \u00e0 <\/em>Z.<\/li>\r\n \t
      3. Pseudotransitivity Rule - <\/em>If X \u00e0 Y <\/em>and WY \u00e0 <\/em>Z hold then so does WX \u00e0Z.<\/em><\/li>\r\n<\/ol>\r\nBased on the above axioms and the .functional dependencies specified for relation student,<\/em> we may write a large number of functional dependencies. Some of these are:\r\n\r\n \r\n\r\n( sno, cno) \u00e0 sno <\/em>(Rule 1)\r\n\r\n(sno, cno) \u00e0 cno <\/em>(Rule 1)\r\n\r\n(sno, cno) \u00e0 (Sname, cname) <\/em>(Rule 2)\r\n\r\ncno \u00e0 office <\/em>(Rule 3)\r\n\r\nsno \u00e0 (Sname, address) <\/em>(Union Rule)\r\n\r\n \r\n\r\nEtc.\r\n\r\n \r\n

        Often a very large list of dependencies can be derived from a given set F<\/em> since Rule 1 itself will lead to a large number of dependencies. Since we have seven attributes (sno, Sname, address, cno, cname,<\/em> instructor, office), <\/em>there are 128 (that is, 2^7) subsets of these attributes. These 128 subsets could form 128 values of X<\/em> in functional dependencies of the type X ~ Y.<\/em> Of course, each value of X<\/em> will then be associated with a number of values for Y (Y<\/em> being a subset of x) Leading to several thousand dependencies. These large numbers of dependencies are not particularly helpful in achieving our aim of normalizing relations.<\/p>\r\n \r\n

        Although we could follow the present procedure and compute the closure of F<\/em> to find all the functional dependencies, the computation requires exponential time and the list of dependencies is often very large and therefore not very useful. There are two possible approaches that can be taken to avoid dealing with the large number of dependencies in the closure. 'One' is to deal with one attribute or a set of attributes at a time and find its closure (i.e. all functional dependencies relating to them). The aim of this exercise is to find what attributes depend on a given set of attributes and therefore ought to be together. The other approach is to find the minimal\u00b7 covers.<\/em><\/p>\r\n \r\n\r\nMinimal Functional Dependencies or Irreducible Set of Dependencies<\/strong>\r\n\r\n \r\n

        In discussing the concept of equivalent FDs, it is useful to define the concept of minimal functional<\/em> dependencies <\/em>or minimal cover <\/em>which is useful in eliminating necessary functional dependencies so that only the minimal numbers of dependencies need to be enforced by the system. The concept of minimal cover of F<\/em> is sometimes called irreducible Set<\/em> of F.<\/em><\/p>\r\n \r\n\r\nA functional depending set S is irreducible if the set has three following properties:\r\n\r\n \r\n\r\nEach right set of a functional dependency of S contains only one attribute.\r\n\r\nEach left set of a functional dependency of S is irreducible. It means that reducing anyone attribute from left set will change the content of S (S will lose some information).\r\n\r\nReducing any functional dependency will change the content of S.\r\n\r\n \r\n\r\nSets of functional dependencies with these properties are also called canonical<\/em> or minimal.<\/em>\r\n\r\nIf the value in a non-key attribute is determined by the value in another non-key attribute then that field has transitive dependency.\r\n\r\n \r\n\r\nFor example, look at the relation below:\r\n

        \"\"<\/p>\r\n \r\n

        The attribute teacher_name<\/strong> is determined by the non-key attribute teacher_id<\/strong>, and not the primary key of course_id<\/strong>. This means that teacher_name is transitively dependent on the primary key of course_id.<\/p>\r\nIn order to show a relation in 3NF, all transitive dependencies must be removed.\r\n\r\n \r\n\r\nFunctional Dependency<\/strong>\r\n\r\n \r\n

        Functional dependency (FD) is a set of constraints between two attributes in a relation. Functional dependency says that if two tuples have same values for attributes A1, A2,..., An, then those two tuples must have to have same values for attributes B1, B2, ..., Bn.<\/p>\r\n \r\n

        Functional dependency is represented by an arrow sign (\u2192) that is, X\u2192Y, where X functionally determines Y. The left-hand side attributes determine the values of attributes on the right-hand side.<\/p>\r\n \r\n\r\nArmstrong's Axioms<\/strong>\r\n\r\n \r\n

        If F is a set of functional dependencies then the closure of F, denoted as F+, is the set of all functional dependencies logically implied by F. Armstrong's Axioms are a set of rules, that when applied repeatedly, generates a closure of functional dependencies.<\/p>\r\n\r\n

          \r\n \t
        • Reflexive rule <\/strong>\u2212 If alpha is a set of attributes and beta is_subset_of alpha, then alpha holds beta.<\/li>\r\n \t
        • Augmentation rule <\/strong>\u2212 If a \u2192 b holds and y is attribute set, then ay \u2192 by also holds. That is adding attributes in dependencies, does not change the basic dependencies.<\/li>\r\n \t
        • Transitivity rule <\/strong>\u2212 Same as transitive rule in algebra, if a \u2192 b holds and b \u2192 c holds, then a \u2192 c also holds. a \u2192 b is called as a functionally that determines b.<\/li>\r\n<\/ul>\r\n\u00a0 \u00a0 Trivial Functional Dependency<\/strong>\r\n
            \r\n \t
          • Trivial <\/strong>\u2212 If a functional dependency (FD) X \u2192 Y holds, where Y is a subset of X, then it is called a trivial FD. Trivial FDs always hold.<\/li>\r\n \t
          • Non-trivial <\/strong>\u2212 If an FD X \u2192 Y holds, where Y is not a subset of X, then it is called a non-trivial FD.<\/li>\r\n \t
          • Completely non-trivial <\/strong>\u2212 If an FD X \u2192 Y holds, where x intersect Y = \u03a6, it is said to be a completely non-trivial FD.<\/li>\r\n<\/ul>\r\n\"\"","rendered":"

            Anomalies in DBMS<\/strong><\/p>\n

             <\/p>\n

            There are three types of anomalies that occur when the database is not normalized. These are \u2013 Insertion, update and deletion anomaly. Let\u2019s take an example to understand this.<\/p>\n

             <\/p>\n

            Example<\/strong>: Suppose a manufacturing company stores the employee details in a table named employee that has four attributes: emp_id for storing employee\u2019s id, emp_name for storing employee\u2019s name, emp_address for storing employee\u2019s address and emp_dept for storing the department details in which the employee works. At some point of time the table looks like this:<\/p>\n

            \"\"<\/p>\n

            \n

            The above table is not normalized. We will see the problems that we face when a table is not normalized.<\/p>\n

             <\/p>\n

            Update anomaly<\/strong>: In the above table we have two rows for employee Rick as he belongs to two departments of the company. If we want to update the address of Rick then we have to update the same in two rows or the data will become inconsistent. If somehow, the correct address gets updated in one department but not in other then as per the database, Rick would be having two different addresses, which is not correct and would lead to inconsistent data.<\/p>\n

             <\/p>\n

            Insert anomaly<\/strong>: Suppose a new employee joins the company, who is under training and currently not assigned to any department then we would not be able to insert the data into the table if emp_dept field doesn\u2019t allow nulls.<\/p>\n

             <\/p>\n

            Delete anomaly<\/strong>: Suppose, if at a point of time the company closes the department D890 then deleting the rows that are having emp_dept as D890 would also delete the information of employee Maggie since she is assigned only to this department.<\/p>\n

             <\/p>\n

            To overcome these anomalies we need to normalize the data. In the next section we will discuss about normalization.<\/p>\n

             <\/p>\n

            A functional dependency is an association between two attributes of the same relational database table. One of the attributes is called the determinant and the other attribute is called the determined. For each value of the determinant there is associated one and only one value of the determined.<\/p>\n

            If A is the determinant and B is the determined then we say that A functionally determines B<\/em> and graphically represent this as A -> B. The symbols A \u00e0 B\u00b7 can also be expressed as B is functionally<\/em> determined by <\/em>A.<\/p>\n<\/div>\n

            Example<\/strong><\/p>\n

             <\/p>\n

            \"\"<\/p>\n

             <\/p>\n

            Functional dependency can also be defined as follows:An attribute in a relational model is said to be functionally dependent on another attribute in the table if it can take only one value for a given value of the attribute upon which it is functionally dependent.<\/p>\n

             <\/p>\n

            Example: <\/strong>Consider the database having following tables:<\/p>\n

             <\/p>\n

            \"\"<\/p>\n

            \n

             <\/p>\n<\/div>\n

            <\/div>\n
            \n

            \u00a0 \u00a0 Sno-<\/strong>Supplier number of supplier that is unique<\/strong><\/p>\n

            Sname-Supplier name<\/strong><\/p>\n

            City-<\/strong>City of the supplier<\/strong><\/p>\n

            Status-<\/strong>Status of the city e.g. A grade cities may have status 10, B grad cities\u00a0<\/strong>may\u00a0<\/strong>have status 20 and so on.<\/strong><\/p>\n

             <\/p>\n

            Here, Sname is FD on Sno. Because, Sname can take only one value for the given value of Sno (e.g. S<\/span><\/p>\n

            1) or in other words there must be one Sname for supplier number <\/span><\/p>\n

            S1. FD is represented <\/span><\/p>\n

            as:\u00a0<\/span>Sno \u00e0 Sname<\/span><\/p>\n

            FD is shown by \u00e0 which means that Sname is functionally dependent on Sno.<\/span><\/p>\n

            Similarly, city and status are also FD on Sno, because for each value of Sno there will be only one city and status.<\/span><\/p>\n

             <\/p>\n

            FD is represented as:<\/p>\n

            Sno\u00a0\u00a0 – City<\/p>\n

            Sno\u00a0\u00a0 – Status<\/p>\n

            sno – S (Sname, City, Status)<\/span><\/p>\n

             <\/p>\n

            Consider another database of shipment with following attributes:<\/p>\n<\/div>\n

            Sno-Supplier number of the supplier<\/p>\n

            Pno-Part number supplied by supplier<\/p>\n

            Qty-Quantity supplied by supplier for a particular Part no<\/p>\n

            \n

            In this case Qty is FD on combination of Sno, Pno because each combination of Sno and Pno results only for one Quantity.<\/p>\n

             <\/p>\n

            SP (Sno, Pno) –> SP.QTY<\/p>\n

             <\/p>\n

            Dependency Diagrams<\/strong><\/p>\n

             <\/p>\n

            A dependency diagram consists of the attribute names and all functional dependencies in a given table.<\/p>\n

            The dependency diagram of Supplier table is.<\/p>\n

            \"\"<\/p>\n

             <\/p>\n

            Here, following functional dependencies exist in supplier table<\/p>\n

            –\u00a0 Sname<\/p>\n

            Sname\u00a0\u00a0\u00a0\u00a0\u00a0 –\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Sno<\/p>\n

            Sno –\u00a0 \u00a0 \u00a0 \u00a0 City
            \nSno – Status
            \nSname – City
            \nSname – Status
            \nCity – Status<\/p>\n\n\n\n\n\n\n\n\n\n
            Sno<\/td>\nSname<\/td>\n<\/tr>\n
            Sname<\/td>\nSno<\/td>\n<\/tr>\n
            Sno<\/td>\nCity<\/td>\n<\/tr>\n
            Sno<\/td>\nStatus<\/td>\n<\/tr>\n
            Sname<\/td>\nCity<\/td>\n<\/tr>\n
            Sname<\/td>\nStatus<\/td>\n<\/tr>\n
            City<\/td>\nStatus<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

            The FD diagram of relation P is<\/p>\n

            \"\"<\/p>\n

            Here following functional dependencies exist in Part table:<\/p>\n

             <\/p>\n

            Pno – Pname<\/p>\n

            Pno – Color<\/p>\n

            Pno – Wt<\/p>\n<\/div>\n

            \"\"<\/p>\n

            \n

            The FD diagram of relation Shipment is\u00a0Here following functional dependencies exist in parts table SP (Sno, Pno) – SP.QTY<\/span><\/p>\n<\/div>\n

            Fully Functional Dependence (FFD)<\/strong><\/p>\n

             <\/p>\n

            Fully Functional Dependence (FFD) is defined, as Attribute Y is FFD on attribute” X, if it is FD on X and not FD on any proper subset of X. For example, in relation Supplier, different cities may have the same status. It may be possible that cities like Amritsar, Jalandhar may have the same status 10.<\/p>\n

            So, the City is not FD on Status.<\/p>\n

             <\/p>\n

            So, the City is not FD on Status.<\/p>\n

            But, the combination of Sno, Status can give only one corresponding City ,because Sno” is unique. Thus,<\/p>\n

            (Sno, Status) \u00e0 City<\/p>\n

            It means city is FD on composite attribute (Sno, Status) however City is not fully functional dependent on this composite attribute, which is explained below:<\/p>\n

            (Sno, Status) \u00e0 City<\/p>\n

             <\/p>\n

            X\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Y<\/p>\n

             <\/p>\n

            Here Y is FD on X, but X has two proper subsets Sno and Status; city is\u00b7 FD .on one proper subset .of X i.e. Sno<\/p>\n

             <\/p>\n

            Sno \u00e0 City<\/p>\n

             <\/p>\n

            According to ‘FFD definition Y must not be FD .on any proper subset of X, but here City is FD in one subset .of X i.e. Sno, so City is not FFD on (Sno, Status)<\/p>\n

             <\/p>\n

            Consider another case of SP table:<\/p>\n

            Here, Qty is FD on combination of Sna, Pno.<\/p>\n

             <\/p>\n

            (Sno, Pno)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00e0\u00a0\u00a0\u00a0\u00a0\u00a0 Qty<\/p>\n

             <\/p>\n

            X\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Y<\/p>\n

             <\/p>\n

            Here, X has two proper subsets Sno and Pna<\/p>\n

            Qty is not FD on Sno, because one Sna can supply mare than .one quantity.<\/p>\n

            Qty is also not FD on Pno, because .one Pna may be supplied many times by different suppliers with different .or same quantities.<\/p>\n

            So, Qty is FFD and composite attribute of (Sno, Pno) \u00e0 Qty.<\/p>\n

             <\/p>\n

            Other Functional Dependencies<\/strong><\/p>\n

             <\/p>\n

            There are same rather types of functional dependencies, which play a vital rule during the process .of normalization of data.<\/p>\n

             <\/p>\n

            Candidate Functional Dependency<\/strong><\/p>\n

             <\/p>\n

            A candidate functional dependency is a functional dependency that includes all attributes of the table. It should also be noted that a well-fanned dependency diagram must have at least one candidate functional dependency, and that there can be more than .one candidate functional dependency for a given dependency diagram.<\/p>\n

             <\/p>\n

            Primary Functional Dependency<\/strong><\/p>\n

             <\/p>\n

            A primary functional dependency is a candidate functional dependency that is selected to determine the primary key. The determinant of the primary functional dependency is the primary key of the relational database table. Each dependency diagram must have one and only on primary functional dependency. If a relational database table has .only .one candidate functional dependency, then it automatically becomes the primary functional dependency<\/p>\n

             <\/p>\n

            Once the primary key has been determined, there will be three possible types of functional dependencies:<\/p>\n

             <\/p>\n

            Description<\/strong><\/p>\n

             <\/p>\n

            A \u00e0 B A key attribute functionally determines a non-key attribute.<\/p>\n

            A \u00e0 B A non-key attribute functionally determines a non-key attribute.<\/p>\n

            A \u00e0 B A non-key attribute functionally determines a key attribute.<\/p>\n

             <\/p>\n

            A partial functional dependency<\/strong> is a functional dependency where the determinant consists of key attributes, but not the entire primary key, and the determined consist~ of non-key attributes.<\/p>\n

             <\/p>\n

            A transitive functional dependency<\/strong> is a functional dependency where the determinant consists of non-key attributes and the determined also consists of non-key attributes.<\/p>\n

             <\/p>\n

            A Boyce-Codd functional dependency<\/strong> is a functional dependency where the determinant consists of non-key attributes and the determined consists of key attributes.<\/p>\n

             <\/p>\n

            A Multi-Value Dependency (MVD)<\/strong> occurs when two or more independent multi valued facts about the same attribute occur within the same table. It means that if in a relation R having A, Band C as attributes, B and Care multi-value facts about A, which is represented as A \u00e0\u00e0B and A \u00e0\u00e0C ,then multi value dependency exist only if B and C are independent on each other.<\/p>\n

             <\/p>\n

            A Join Dependency<\/strong> exists if a relation R is equal to the join of the projections X Z. where X, Y, Z projections of R.<\/p>\n

             <\/p>\n

            Closure of set of dependencies<\/strong><\/p>\n

             <\/p>\n

            Let a relation R<\/em> have some functional dependencies F<\/em> specified. The closure of F<\/em> (usually written as F<\/em>+) is the set of all functional dependencies that may be logically derived from F. <\/em>Often F <\/em>is the set of most obvious and important functional dependencies and. F<\/em>+, the closure, is the set of all the functional dependencies including F<\/em> and those that can be deduced from F.<\/em> The closure is important and may, for example, be needed in finding one or more candidate keys of the relation.<\/p>\n

             <\/p>\n

            For example, the student<\/em> relation has the following functional dependencies<\/p>\n

             <\/p>\n

            sno <\/em>\u00e0 Sname<\/em><\/p>\n

            cno <\/em>\u00e0 came<\/em><\/p>\n

            sno <\/em>\u00e0 address<\/em><\/p>\n

            cno <\/em>\u00e0 instructor<\/em><\/p>\n

            Instructor \u00e0 office<\/em><\/p>\n

             <\/p>\n

            \n

            Let these dependencies be denoted by F.<\/em> The closure of F,<\/em> denoted by F<\/em> +, includes F<\/em> and all functional- dependencies that are implied by F.<\/em><\/p>\n

             <\/p>\n

            To determine F<\/em>+, we need rules for deriving all functional dependencies that are implied: by F.<\/em> A set of rules that may be used to infer additional dependencies was proposed by Armstrong in 1974. These rules (or axioms) are a complete set of rules in\u00b7 that all possible functional dependencies may be derived from them. The rules are:<\/p>\n

             <\/p>\n

            1.\u00a0 <\/em>Reflexivity Rule – <\/em>If X <\/em>is a set of attributes and Y is a subset of X, <\/em>then X \u00e0Y <\/em>holds.<\/p>\n

             <\/p>\n

            The reflexivity rule is the simplest (almost trivial) rule. It states that each subset of X<\/em> is functionally dependent on X.<\/em> In other words trivial dependence is defined as follows:<\/p>\n

             <\/p>\n

            Trivial functional dependency<\/strong>: A trivial functional dependency is a functional dependency of an attribute on a superset of itself.<\/p>\n

             <\/p>\n

            For example: <\/strong>{Employee ID, Employee Address} \u00e0 {Employee Address} is trivial, here {Employee\u00a0Address} is a subset of {Employee ID, Employee Address}.<\/span><\/p>\n<\/div>\n

              \n
            1. Augmentation Rule – <\/em>If X \u00e0 Y <\/em>holds and W <\/em>is a set of attributes, and then WX \u00e0 WY <\/em>holds.<\/li>\n<\/ol>\n

              The argumentation (‘u rule is also quite simple. It states that if Y<\/em> is determined by <\/span>X<\/em> then a set of attributes <\/span>W<\/em> and <\/span>Y<\/em> together will be determined by <\/span>W<\/em> and <\/span>X<\/em> together. Note that we use the notation <\/span>WX<\/em> to mean the collection of all attributes in <\/span>W<\/em> and <\/span>X<\/em> and write <\/span>WX<\/em> rather than the more conventional <\/span>(W,<\/em><\/p>\n

                \n
              1. X) <\/em>for convenience.<\/li>\n<\/ol>\n

                 <\/p>\n

                For example<\/strong>: Rno – Name; Class and Marks is a set of attributes and act as<\/p>\n

                Then\u00b7 {Rno, Class, Marks} -> {Name, Class, Marks}<\/p>\n

                3. Transitivity Rule – <\/em>If X -> <\/em>Y and Y -> Z <\/em>hold, then X -> Z <\/em>holds.<\/p>\n

                The transitivity rule is perhaps the most important one. It states that if X<\/em> functionally determines Y and Y functionally determine Z<\/em> then X<\/em> functionally determines Z.<\/em><\/p>\n

                 <\/p>\n

                For example: <\/strong>Rno -> City and City -> Status, then Rno -> Status should be holding true.<\/p>\n

                 <\/p>\n

                These rules are called Armstrong’s Axioms.<\/em><\/p>\n

                 <\/p>\n

                Further axioms may be derived from the above although the above three axioms are sound and<\/em> complete <\/em>in that they do not generate any incorrect functional dependencies (soundness) and they do generate all possible functional dependencies that can be inferred from F<\/em> (completeness). The most important additional axioms are:<\/p>\n

                  \n
                1. Union Rule – <\/em>If X -> Y <\/em>and X -> Z <\/em>hold, then X -> YZ <\/em>holds.<\/li>\n
                2. Decomposition Rule – <\/em>If X \u00e0 YZ <\/em>holds, then so do X \u00e0 Y <\/em>and X \u00e0 <\/em>Z.<\/li>\n
                3. Pseudotransitivity Rule – <\/em>If X \u00e0 Y <\/em>and WY \u00e0 <\/em>Z hold then so does WX \u00e0Z.<\/em><\/li>\n<\/ol>\n

                  Based on the above axioms and the .functional dependencies specified for relation student,<\/em> we may write a large number of functional dependencies. Some of these are:<\/p>\n

                   <\/p>\n

                  ( sno, cno) \u00e0 sno <\/em>(Rule 1)<\/p>\n

                  (sno, cno) \u00e0 cno <\/em>(Rule 1)<\/p>\n

                  (sno, cno) \u00e0 (Sname, cname) <\/em>(Rule 2)<\/p>\n

                  cno \u00e0 office <\/em>(Rule 3)<\/p>\n

                  sno \u00e0 (Sname, address) <\/em>(Union Rule)<\/p>\n

                   <\/p>\n

                  Etc.<\/p>\n

                   <\/p>\n

                  Often a very large list of dependencies can be derived from a given set F<\/em> since Rule 1 itself will lead to a large number of dependencies. Since we have seven attributes (sno, Sname, address, cno, cname,<\/em> instructor, office), <\/em>there are 128 (that is, 2^7) subsets of these attributes. These 128 subsets could form 128 values of X<\/em> in functional dependencies of the type X ~ Y.<\/em> Of course, each value of X<\/em> will then be associated with a number of values for Y (Y<\/em> being a subset of x) Leading to several thousand dependencies. These large numbers of dependencies are not particularly helpful in achieving our aim of normalizing relations.<\/p>\n

                   <\/p>\n

                  Although we could follow the present procedure and compute the closure of F<\/em> to find all the functional dependencies, the computation requires exponential time and the list of dependencies is often very large and therefore not very useful. There are two possible approaches that can be taken to avoid dealing with the large number of dependencies in the closure. ‘One’ is to deal with one attribute or a set of attributes at a time and find its closure (i.e. all functional dependencies relating to them). The aim of this exercise is to find what attributes depend on a given set of attributes and therefore ought to be together. The other approach is to find the minimal\u00b7 covers.<\/em><\/p>\n

                   <\/p>\n

                  Minimal Functional Dependencies or Irreducible Set of Dependencies<\/strong><\/p>\n

                   <\/p>\n

                  In discussing the concept of equivalent FDs, it is useful to define the concept of minimal functional<\/em> dependencies <\/em>or minimal cover <\/em>which is useful in eliminating necessary functional dependencies so that only the minimal numbers of dependencies need to be enforced by the system. The concept of minimal cover of F<\/em> is sometimes called irreducible Set<\/em> of F.<\/em><\/p>\n

                   <\/p>\n

                  A functional depending set S is irreducible if the set has three following properties:<\/p>\n

                   <\/p>\n

                  Each right set of a functional dependency of S contains only one attribute.<\/p>\n

                  Each left set of a functional dependency of S is irreducible. It means that reducing anyone attribute from left set will change the content of S (S will lose some information).<\/p>\n

                  Reducing any functional dependency will change the content of S.<\/p>\n

                   <\/p>\n

                  Sets of functional dependencies with these properties are also called canonical<\/em> or minimal.<\/em><\/p>\n

                  If the value in a non-key attribute is determined by the value in another non-key attribute then that field has transitive dependency.<\/p>\n

                   <\/p>\n

                  For example, look at the relation below:<\/p>\n

                  \"\"<\/p>\n

                   <\/p>\n

                  The attribute teacher_name<\/strong> is determined by the non-key attribute teacher_id<\/strong>, and not the primary key of course_id<\/strong>. This means that teacher_name is transitively dependent on the primary key of course_id.<\/p>\n

                  In order to show a relation in 3NF, all transitive dependencies must be removed.<\/p>\n

                   <\/p>\n

                  Functional Dependency<\/strong><\/p>\n

                   <\/p>\n

                  Functional dependency (FD) is a set of constraints between two attributes in a relation. Functional dependency says that if two tuples have same values for attributes A1, A2,…, An, then those two tuples must have to have same values for attributes B1, B2, …, Bn.<\/p>\n

                   <\/p>\n

                  Functional dependency is represented by an arrow sign (\u2192) that is, X\u2192Y, where X functionally determines Y. The left-hand side attributes determine the values of attributes on the right-hand side.<\/p>\n

                   <\/p>\n

                  Armstrong’s Axioms<\/strong><\/p>\n

                   <\/p>\n

                  If F is a set of functional dependencies then the closure of F, denoted as F+, is the set of all functional dependencies logically implied by F. Armstrong’s Axioms are a set of rules, that when applied repeatedly, generates a closure of functional dependencies.<\/p>\n

                    \n
                  • Reflexive rule <\/strong>\u2212 If alpha is a set of attributes and beta is_subset_of alpha, then alpha holds beta.<\/li>\n
                  • Augmentation rule <\/strong>\u2212 If a \u2192 b holds and y is attribute set, then ay \u2192 by also holds. That is adding attributes in dependencies, does not change the basic dependencies.<\/li>\n
                  • Transitivity rule <\/strong>\u2212 Same as transitive rule in algebra, if a \u2192 b holds and b \u2192 c holds, then a \u2192 c also holds. a \u2192 b is called as a functionally that determines b.<\/li>\n<\/ul>\n

                    \u00a0 \u00a0 Trivial Functional Dependency<\/strong><\/p>\n

                      \n
                    • Trivial <\/strong>\u2212 If a functional dependency (FD) X \u2192 Y holds, where Y is a subset of X, then it is called a trivial FD. Trivial FDs always hold.<\/li>\n
                    • Non-trivial <\/strong>\u2212 If an FD X \u2192 Y holds, where Y is not a subset of X, then it is called a non-trivial FD.<\/li>\n
                    • Completely non-trivial <\/strong>\u2212 If an FD X \u2192 Y holds, where x intersect Y = \u03a6, it is said to be a completely non-trivial FD.<\/li>\n<\/ul>\n

                      \"\"<\/p>\n","protected":false},"author":4,"menu_order":9,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-79","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/79","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":4,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/79\/revisions"}],"predecessor-version":[{"id":323,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/79\/revisions\/323"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/79\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/media?parent=79"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapter-type?post=79"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/contributor?post=79"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/license?post=79"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}