Normalisation is the term used to describe how you break a file down into tables to create a database. There are 3 or 4 major steps involved known as 1NF (First Normal Form), 2NF (Second Normal Form), 3NF (Third Normal Form) and BCNF (Boyce-Codd Normal Form). There are others but they are rarely if ever used. A database is said to be Normalised if it is in 3NF (or ideally in BCNF). These steps are descibed as follows:

Note: When attribute is used we are speaking of a field in the table

1NF
To put a database in 1N

• ensure that all attributes (columns) are atomic (which means that any single field should only have a value for ONE thing).

Examples:

In a database a table on Customers would have an address attribute. The address is made up of Company Name, Address Line1, Address Line2, Address Line3, City, Postcode. There are 6 values to this address and as such each should have it’s own field (column).

If your company sold furniture a table on products could have a description attribute. If for example that attribute was ‘Beech Desk 120w x 75h x 50d’. Ideally this would be broken down into a number attributes like ‘Colour’, ‘Type’, ‘Width’, ‘Height’ and ‘Depth’. The reason for this is it would allow you to seach the database for all Desks, for all pieces of Beech furniture, for all desks with a width of 120 etc.

• Create a separate table for each set of related data and Identify each set of related data with a primary key

Example:

In a general Invoicing table you would have a separate table for Customers, Orders, Products, Invoices and you would probably need tables for OrderDetails and InvoiceDetails as well. Each of these tables must have their own primary key. Each of these tables except for customers would have a foreign key reference to the primary key of another table. (See Relationships below)

• Do not use multiple fields in a single table to store similar data

Example:
(Underlined fields are Primary Keys and Italicised fields are Foreign Keys)

In a customer order you could have more than one product. That is the customer has ordered more than one item. If you tried to put all of this in one table as {OrderID, CustomerID, OrderDate, Product1, Product2, Product3} what would happen if the customer ordered more than 3 products. There would also be implications for querying the kind or quantiy of products ordered by a customer. Therefore these product fields don’t belong in the order table which is why we would have an OrderDetails table which would have a foreign key refernce to the Orders table {OrderDetailsID, OrderID, ProductID, Quantity}. Using productID as a foreign key to the product table means you don’t have to identify the product attributes here. This also allows you to enter a quantity figure for the product ordered.

Relationships:

All tables should have a 1 to 1 or 1 to many relationship. This means for example that 1 customer can have 1 or many orders and 1 order can have 1 or many details.

Therefore Orders table would have a foreign key reference to the Customer table primary key {OrderID, CustomerID, OrderDate} and the OrderDetails table would have a foreign key reference to the Order table primary key {OrderDetailsID, OrderID, ProductID, Quantity}. This table also contains a foreign key reference to the Products table. As a product is likely to be ordered more than once there is a many to 1 relationship between the OrderDetails and the Products table.

If any tables have a many to many relationship this must be broken out using a JOIN table. For example, Customers can have many Suppliers and Suppliers can supply to many Customers. This is known as a many to many relationship. You would need to create a JOIN table that would have a primary key made up of a foreign key reference to the Customers table and a foreign key reference to the suppliers table. Therefore the SuppliersPerCustomer table would be {SupplierID,CustomerID}. Now the Suppliers table will have a 1 to many relationship with the SuppliersPerCustomer table and the Customers table will also have a 1 to many relationship with the SuppliersPerCustomer table.

2NF

The database must meet all the requirements of the 1NF.

In addition, records should not depend on anything other than a table’s primary key (a primary key can be made up of more than one field, only if absolutely necessary like in a JOIN table).

Example:

A customers address is needed by the Customers table, but also by the Orders, and Invoices tables. Instead of storing the customer’s address as a separate entry in each of these tables, store it in one place, either in the Customers table or in a separate Addresses table.

3NF

The database must meet all the requirements of the 1NF and 2NF.

The third normal form requires that all columns in a relational table are dependent only upon the primary key. A more formal definition is:

• A relational table is in third normal form (3NF) if it is already in 2NF and every non-key column is non transitively dependent upon its primary key.

In other words, all nonkey attributes are functionally dependent only upon the primary key. All 3NF really means is that all fields (attributes) should be dependent on the tables primary key. If they are not they should be put in their own table. This means that every attribute unless it is a primary or foreign key must be DIRECTLY dependent on the Primary Key of this table and not on some other column.

Example:

The Customer table contains information such as address, city, postcode imagine it also contained a column called shipping cost. The value of shipping cost changes in relation to which city the products are being delivered to, and therefore is not directly dependent on the customer even though the cost might not change per customer, but it is dependent on the city that the customer is in. Therefore we would need to create another separate table to hold the information about cities and shipping costs.

BCNF

A relation is in Boyce-Codd Normal Form (BCNF) if every determinant is a candidate key. BCNF is very similar to 3NF but deals with dependencies within the primary keys. BCNF in it’s simplist terms just says don’t have a primary key made up of more than one field unless it is a join table to disperse a many to many relationship and only contains the two primary keys of the tables it is joining.

Most relations that are in 3NF are also in BCNF. It only happens that a relation which is in 3NF is not in BCNF when the primary key in a table is made up of more than one field and the other columns are not dependent on both fields but only on one or the other.

Identity theft may be on the rise, but you don’t have to make it easy for thieves — take steps to protect the personally identifiable information (PII) of your employees and clients.

Is your organization part of the solution or part of the problem? PII is pouring through the security floodgates and ending up in the wrong hands at an alarming rate.

To protect your organization’s employees and clients, you need to evaluate how well your company protects its PII. Here are seven common mistakes to avoid.

Keep users in the dark

Users will always be the weakest link in any enterprise network — and all of the gadgets and controls in the world won’t change that. If your users don’t know how to identify and handle PII, it’s only a matter of time before one of them discloses this data to the wrong source.

The solution is simple: Educate your users on your company’s policies and mechanisms to process PII. And don’t forget to include regularly scheduled refresher courses.

Partner with the wrong businesses

You’ve made sure your security is rock solid, and you’ve trained your users. But can your business partners say the same? Do you collect or share information with businesses that have little or no security?

If your company collects and shares PII with insecure partners, who do you think will end up in the paper and explaining to law enforcement about how a breach occurred? Your company will.

The solution is just as simple as the last dilemma: Educate and train your business partners on how to protect this sensitive information.Charge them for your expertise if you want, but get the job done.

Keep data around past its prime

What do you do with data once it’s served its purpose? If you aren’t destroying PII when it’s no longer required, then you’re not doing your job. That doesn’t mean throwing it away either — that means destroying it.

Dumpster divers make a living off of old bank statements and credit card receipts. That’s why you need to wipe out PII when it’s no longer necessary.If your organization doesn’t have a shredder, you need to get one today.

Don’t worry about physical security

It’s imperative that you implement physical access controls to prevent unauthorized people — including employees — from gaining access to PII. Get a door lock and a badge reader, and start controlling access.

Don’t lock up your records

If you don’t have specific storage areas on your network (as well as file cabinets) for PII, then how can your properly protect it? Take inventory of your network — and your paper copies — and develop a plan to protect that data. This would be a good time to research encrypting data-at-rest and locking some file cabinets.

Ignore activity on your network

I’ve said this before in columns, but it’s worth repeating: If you’re not going to actively monitor your network for suspicious activity or incidents, then stop collecting the data. Develop a method that’s within your capabilities and budget to monitor your network for suspicious activity or incidents. And while you’re at it, develop a response and mitigation strategy for security incidents.

Audits? Who needs audits?

A lot of businesses either don’t know what security events to audit or don’t read their security logs — or both. If you’re not sure which events to audit, find out. Set up security auditing, and start reviewing your logs today.

Final thoughts

Identity theft may be on the rise, but you don’t have to make it easy for thieves. You can help prevent identity theft both at home and at the office — you just need to take a few extra steps.

When you’re designing or writing software, one issue that can often be glossed over is the matter of efficiency. It’s so easy at the beginning of a project to just concentrate on getting something working, so you can demonstrate progress, and then worry about making it fast later on. The unfortunate fact is though optimisation can only take you so far, the true efficiency issues are going to lie in your algorithm design. Most IT professionals have learned the basics at some point in their career, but in case you’re a little rusty read on and we’ll refresh your memory.

The first thing to consider is what kind of complexity you’re looking to reduce. The two major complexity areas are time — that is, how long an operation will take to complete — and space, or how much memory is needed. When talking complexity, we tend to rate speed in terms of how many steps (or blocks of memory for space complexity) are taken per input variable, rather than in absolutes, since they are so dependent on the specifics of the hardware. Likewise, the length of time an individual step will take is largely disregarded since for large inputs this time will be dominated by the complexity class.

To make comparing two algorithms easier we group them into classes by using a special kind of notation. There are a number of different ways to do this, based upon the best case, average case and worst case input scenario. I like to use the worst case most of the time, since that’s the time it’s going to make the most difference to how you perceive performance. To express this we use what’s called big O notation, which expresses the number of steps an algorithm will take for an input of size “n” in the worst case. So, take the following example, which simply sums the numbers in a list.

sum(a) {
final_sum = 0
n = length(a)
for (i = 0; i < n; i++) {
sum += a[i]
}
return final_sum
}

Treating each line as a single step, we can see that calling sum on a list of size n will take n+4 steps to complete, two for the initialisation of final_sum and n, one to set up the for loop, one for the return statement and then n times one for the loop body.

The problem has changed, and now you need to multiply each number by how many times it occurs in the list before adding it to the running total. Take the following implementation:

sum_multiple(a) {
final_sum = 0
n = length(a)
for (i = 0; i < n; i++) {
num = 0
for (j = 0; j < n; j++) {
if (a[j] == a[i]) {
num++
}
}
final_sum += a[i] * num
}
return final_sum
}

This does similarly to the last function, with the exception that before adding the current value to the running total, it goes through the list and counts the number of occurrences of each value. Calling this function of a list of size n means that 4 + n * (1 + n * 2) steps are carried out since the outer loop now contains 2n + 1 steps. In total this means that calling this function “costs” 2n2 + n + 4 steps. For a list of 10 numbers it takes 214 steps, but for a list of 100 numbers it will need more than 20,000 steps to complete. That’s quite an increase. When we rewrite it in another way, however, this changes:

sum_multiple2(a) {
final_sum = 0
n = length(a)
numbers = dict()
for (i = 0; i < n; i++) {
if (numbers.has(a[i])) {
numbers[a[i]]++
} else {
numbers[a[i]] = 1
}
}
for (j = 0; j < n; j++) {
final_sum += a[j] * numbers[a[j]]
}
return final_sum
}

In this example we precompute the number of times each value occurs in the list. To do this we use a new data type which can store these values. It’s not particularly important how this is implemented so long as we can be sure that we can insert and retrieve values in constant time. In languages that support them as standard this could be a hash or a dictionary, or if you’re not that lucky (say you’re using C) then you can think of it as an integer array of size max(a). The method simply returns true if this type contains a the given value.

Anyhow, you can see how rather than work out how many times each number occurs as we reach it we can do it all at the beginning and store it. Let’s look at how this helps — sum_multiple2 takes 3n + 6 steps: the usual initialisation steps, plus two for each input to build the dictionary of number occurrences, and then one for each input to sum them. For 10 inputs this will take 36 steps, for one hundred: 306. That’s more than 65 times faster for the second version when dealing with 100 inputs. If say, we had one million inputs it becomes two trillion vs three million and the second version is more than 650,000 times faster.

Now we’ve been taking a fairly casual view of the number of steps in each algorithm, treating each line as one step, when a statement like “sum += a[j] * numbers[a[j]]” contains multiple lookups and could be compiled into as many as 10 individual instructions on a hardware level. This is not really that important though, when you think about it, even if we assume that every step we’ve counted in the second example really takes 10, and the first program is unchanged then it still represents more than a 60,000 times improvement.

Really what we’re interested in is the order of the algorithm, for convenience, we reduce it to the size of the largest part. For example, sum_multiples we say is O(n2) whereas sum_multiples2 is O(n). This is often all you really need to know, for large enough values of n, O(n) algorithms will always beat O(n2) algorithms, regardless of the details.