As a software developer, I already have some experience in designing a more or less normalized database schema, but I haven't received any formal training in it before. This semester, I took a university class on databases. We are being taught the formal way of designing a schema based on relational algebra. First, we collect the attributes we want to store:


Then we find functional dependencies between the attributes:

fpublisher : { PUBLISHER } -> { PUBLISHER_ADDRESS }

After that we can normalize this schema. (For the sake of simplicity, I assumed that a book is defined by its title and author alone, no two editions or two copies of the same edition are stored.)

Now what happens when a book can have more than one category? How do I represent that relation with dependencies? The category can't be a secondary attribute any more, but if it's primary, how do I proceed?

What does this define?


We are told that the empty set cannot be on the right side of a dependency.

  • What did your teacher end up saying was the solution? Commented Nov 17, 2011 at 18:36

3 Answers 3


The question you raise has to do with the definition of first normal form (1NF). Whether the answer directly involves functional dependencies depends in part on the definitions you accept. Wikipedia has a fairly simple article about 1NF.

title                                author    year  category   
An Introduction to Database Systems  CJ Date   2003  databases, modeling, storage, retrieval

If you look at the column "category" one way, it contains a single value. Depending on your dbms and your design, that value might be the string "databases, modeling, storage, retrieval", or it might be the array "{databases, modeling, storage, retrieval}".

If you look at the column "category" another way, it contains four values. Those values are the four strings "databases", "modeling", "storage", and "retrieval".

In database design, the solution is to use two tables. But I don't think you can decompose the "bad" table by projection (which CJ Date identifies as the decomposition operator), because projection doesn't split the content of a column into multiple rows. (Projection doesn't give you four rows from the single value "databases, modeling, storage, retrieval", which is what you need to do. "Join", the recomposition operator, doesn't yield a single value like "databases, modeling, storage, retrieval", either.)

The inability to decompose by projection suggests that the solution to this problem doesn't have to do with functional dependencies. The resulting table would have three attributes, {title, author, category}, the only key would also be {title, author, category}, and that table would be in 5NF.


I don't know how to write this out in the above format but you are going to have a table for books, and a table for categories with a foreign key to the book. If there were more columns for the category, to normalise this you would need to add a third table to allow a many to many relationship with foreign keys to both book and category.

Following the example of what you have said above and the statement that the right hand side can not be empty, this can't be represented in that way!

Plus the reason it generally doesn't seem to make sense is that in the real world you would probably want to implement this using surrogate keys.

  • I think you're right but my teacher is a natural key zealot and he wouldn't accept any other solution. Commented Oct 6, 2011 at 16:37
  • If I were to implement this in a real-world system I would use surrogate keys and a third table with two foreign key columns. I'm going to ask him on Monday about this and accept your answer if there really is no solution. Commented Oct 6, 2011 at 16:44
  • 1
    Surrogate keys don't have anything to do with normalization. Commented Oct 8, 2011 at 10:52
  • They do because if you add a surrogate key you are changing what the row is dependant on and so the way you normalise the table. In fact this is the whole point of adding them. The reasons for using them are usually more of a technical practicality than a logical one but for example if you had two authors with the same name who each wrote a book with the same title then adding a surrogate key would allow that where it couldn't be represented.
    – JamesRyan
    Commented Oct 8, 2011 at 19:15

To associate one book with multiple categories via functional dependencies, you'd need to introduce an artificial property that tracks the number of category associations.

Thus, your functional dependencies would be:

f_book_category: { TITLE, AUTHOR, CATEGORY_INDEX } -> { CATEGORY }
f_publisher:     { PUBLISHER } -> { PUBLISHER_ADDRESS }

This atrocity is necessitated by the fact that, as functions, they can return only one output for a given input.

There is no way to directly associate a book with multiple categories unless you consider the list of categories applicable to a given book as a single value, as Catcall suggested.

  • But then there will be multiple titles and authors for a category. I think OP does not want that.
    – Lazer
    Commented Oct 6, 2011 at 15:16
  • @Lazer - Why not? Isn't it correct to have multiple books fall under the same category? Commented Oct 6, 2011 at 15:27
  • Yes, they can be categorized that way, in my opinion. I deduced that OP doesn't want that from "The category can't be a secondary attribute any more".
    – Lazer
    Commented Oct 6, 2011 at 16:11
  • That can't be right because then the category key would need to not be unique.
    – JamesRyan
    Commented Oct 6, 2011 at 16:33
  • Category is a primary attribute in your example, which must be unique. Commented Oct 6, 2011 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.