Computer Science

Share this article:

Computer Science

  • Join our comunity:

Loose Ends

By: , Posted on: July 24, 2017

I don’t like loose ends

There are at least two loose ends in my book: one is the relationship between FD graphs (Chapter 4) and normalisation (Appendix B); the other is footnote 25 on page 133.  These two loose ends turn out to be related, and will be addressed in an article I am preparing with Dave Voorhis, who also has previously written on graphical database design.  Its working title is A Graphical Approach to Database Normalisation, and we hope to see it published in the next few months.

Access chapter 4, Data-structure analysis and Appendix B, Normalisation for free.

At first, I found it hard to dream up any plausible scenario to which the footnote on page 133 could apply, but I think this is plausible enough:

We have a situation where each subject is identified by a code or a name, but unlike the case study in the book, a subject’s name is unique only within a department.  For example, both the Computer Science and the Information Technology departments teach a subject called Operating Systems I, but one is focussed on Unix and the other is focussed on Windows.  So only the full combination {Department, Subject Name} defines a {Subject Code}.

We are given the FDs, {Department, Subject Name}→{Subject Code}, {Subject Code}→{Department}, and {Subject Code}→{Subject Name}.  We also have the trivial FDs, {Department, Subject Name}→{Department} and {Department, Subject Name}→{Subject Name}.

Here is the FD graph:

Since {Department, Subject Name} and {Subject Code} are both candidate keys for subjects, we would like to see them linked by a cycle.  Unfortunately, although the graph contains the edge {Department, Subject Name}→{Subject Code}, it doesn’t contain an edge {Subject Code}→{Department, Subject Name}.

We need to show that {Department, Subject Name} can be derived from {Subject Code}.  This seems to need a creative use of the addition rule, but the smart solution is to work backwards along the edges of the FD-graph from {Department} and {Subject Name} (the components of {Department, Subject Name}) until we reach a common point, which quickly turns out to be {Subject Code}.  The smart way doesn’t need us to be creative!  Once we have proved that {Department} and {Subject Name} can both be derived from {Subject Code}, we may confidently add the edge {Subject Code}→{Department, Subject Name} to complete the cycle.

The other loose end is to properly relate FD graphs to normalisation theory.  This means adopting the unique name assumption, referred to on page 429 of my book.  The unique name assumption is, “There is at most one FD XY from any set of attributes, X, to any other set, Y.”  For example, Figure 4.5 of the book has two FDs from Subjects to Integers: Filled and Quota.  According to the unique name assumption, they must be identical.  If we didn’t want that to be true, we ought to have specified Filled: SubjectsBums, and Quota: SubjectsSeats.  The unique name assumption therefore ignores the fact that Bums and Seats are both integers that count places in a subject—which is of interest during systems analysis, but is best forgotten in normalisation.

The advantage of the unique name assumption is that, given FDs fXY, gYZ, and hXZ, it must be the case that g, so normalisation becomes a purely mathematical exercise in which we can forget what the names actually mean.  By adopting this assumption, Dave Voorhis and I have been able to develop algorithms that will correctly normalise a given set of FDs to either 3NF or BCNF.  They are efficiently based on the depth-first search of a ‘cover graph’ (page 71 of my book).  The construction of the cover graph is a bit tricky to explain, and this is not the place to do it.  You will just have to wait for the article!  I will let you know as soon as it is published.

About the Book:

systems analysis and synthesis

Systems Analysis and Synthesis presents several new graph-theoretical methods that relate system design to core computer science concepts, and enable correct systems to be synthesized from specifications. Based on material refined in the author’s university courses, the book has immediate applicability for working system engineers or recent graduates who understand computer technology, but have the unfamiliar task of applying their knowledge to a real business problem.

About the Author:

barry dwyerBarry Dwyer served as a senior lecturer in computer science at the University of Adelaide, Australia, from 1982 – 2004, teaching courses on database and information systems, systems analysis, artificial intelligence, and knowledge representation. Prior to that he was a software engineer working in operating systems, database systems, decision-table translators and automated system construction; and a management services officer and senior computer science lecturer at the University of South Australia.

Barry began his career as an electronics engineer in the aviation industry, where he designed analogue flight simulator and radar equipment, and co-designed a digital head-up display system. Since retiring from teaching, Barry has written proof of concept software frameworks that led to the development of this book, and has spoken regularly on these and related topics.

Barry’s book is available to order on the Use discount code STC317 at checkout and save up to 30% on your very own copy!

Connect with us on social media and stay up to date on new articles

Computer Science

Computing functionality is ubiquitous. Today this logic is built into almost any machine you can think of, from home electronics and appliances to motor vehicles, and it governs the infrastructures we depend on daily — telecommunication, public utilities, transportation. Maintaining it all and driving it forward are professionals and researchers in computer science, across disciplines including:

  • Computer Architecture and Computer Organization and Design
  • Data Management, Big Data, Data Warehousing, Data Mining, and Business Intelligence (BI)
  • Human Computer Interaction (HCI), User Experience (UX), User Interface (UI), Interaction Design and Usability
  • Artificial intelligence (AI)
Morgan Kaufmann companion resources can be found here You can also access companion materials and instructor’s resources for all our new books on the Elsevier Store. Search by author, title or ISBN, then look for the “Resources” tab on any book page. Looking for companion materials or instructor’s resources for these titles? Connect below: