NAME
DBSchema::Normalizer - database normalization. - Convert a table from 1st to 2nd normal form
SYNOPSIS
# the easy way is to give all parameters to the constructor
# and then call do()
#
my
$norm
= DBSchema::Normalizer->new (
{
DSN
=>
$DSN
,
username
=>
$username
,
password
=>
$password
,
src_table
=>
$sourcetable
,
index_field
=>
$indexfield
,
lookup_fields
=>
$lookupfields
,
# comma separated list
lookup_table
=>
$lookuptable
,
dest_table
=>
$dest_table
,
copy_indexes
=>
"yes"
,
});
$norm
->
do
();
# Just Do It!
# Alternatively, you can have some more control, by
# creating the lookup table and normalized table separately,
# especially useful if one of them is an intermediate step.
#
my
$norm
= DBSchema::Normalizer->new(
{
DSN
=>
$DSN
,
username
=>
$username
,
password
=>
$password
});
$norm
->create_lookup_table (
{
src_table
=>
$tablename
,
index_field
=>
$indexfield
,
lookup_fields
=>
$lookupfields
,
lookup_table
=>
$lookuptable
});
$norm
->create_normalized_table (
{
src_table
=>
$tablename
,
index_field
=>
$indexfield
,
lookup_fields
=>
$lookupfields
,
lookup_table
=>
$lookuptable
,
dest_table
=>
$dest_table
,
copy_indexes
=>
"yes"
,
});
DESCRIPTION
DBSchema::Normalizer is a module to help transforming MySQL database tables from 1st to 2nd normal form. Simply put, it will create a lookup table out of a set of repeating fields from a source table, and replace such fields by a foreign key that points to the corresponding fields in the newly created table. All information is taken from the database itself. There is no need to specify existing details. The module is capable of re-creating existing indexes, and should deal with complex cases where the replaced fields are part of a primary key.
Algorithm
The concept behind DBSchema::Normalizer is based upon some DBMS properties. To replace repeating fields with a foreign key pointing to a lookup table, you must be sure that for each distinct set of values you have a distinct foreign key. You might be tempted to solve the problem with something like this:
I. Read all records into memory
II.
for
each
record, identify the unique value
for
the fields to be
moved into a lookup table and store it in a hash
II. again,
for
each
record, find the corresponding value in the
previously saved hash and save the non-lookup fields plus the
unique key into a new table
IV.
for
each
key in the hash,
write
the
values
to a lookup table
I can find four objections against such attempt:
1. Memory problems. The source table can be very large (and some of the table I had to normalize were indeed huge. This kind of solution would have crashed any program trying to load them into memory.) Instead of reading the source table into memory, we could just read the records twice from the database and deal with them one at the time. However, even the size of the hash could prove to be too much for our computer memory. A hash of 2_000_000 items is unlikely to handle memory efficiently in most nowadays desktops.
2. Data specific solution. To implement this algorithm, we need to include details specific to our particular records in our code. It is not a good first step toward re-utilization.
3. Data conversion. We need to fetch data from the database, eventually transform it into suitable formats for our calculation and then send it back, re-packed in database format. Not always an issue, but think about the handling of floating point fields and timestamp fields with reduced view. Everything can be solved, but it could be a heavy overhead for your sub.
4. Finally, I would say that this kind of task is not your job. Nor is Perl's. It belongs in the database engine, which can easily, within its boundaries, identify unique values and make a lookup table out of them. And it can also easily make a join between source and lookup table.
That said, the solution springs to mind. Let the database engine do its job, and have Perl drive it towards the solution we need to achieve. The algorithm is based upon the fact that a table created from a SELECT DISTINCT statement is guaranteed to have a direct relationship with each record of the source table, when compared using the same elements we considered in the SELECT DISTINCT.
The algorithm takes four steps:
I. create the lookup table
CREATE TABLE lookup ({lookupID} INT NOT NULL auto_increment
primary key, {LOOKUP FIELDS});
#(and add a key for each {LOOKUP FIELDS})
II. fill in the lookup table
INSERT INTO lookup
SELECT DISTINCT NULL {LOOKUP FIELDS} FROM source_table;
#(the {lookupID} is automatically created, being auto_increment)
III. create the normalized table
CREATE TABLE norm_table ({source_table FIELDS} -
{LOOKUP FIELDS} + {lookupID})
IV. fill in the normalized table
INSERT INTO normalized table
SELECT {source_table FIELDS} - {LOOKUP FIELDS} + {lookupID}
FROM source_table
INNER JOIN lookup
on (source_table.{LOOKUP FIELDS}= lookup.{LOOKUP FIELDS})
As you can see, the entire operation is run in the server workspace, thus avoiding problems of (a) fetching records (less network traffic), (b) handling data conversion, (c) memory occupation and (d) efficiency.
Let's see an example.
Having a table MP3 with these fields
mysql> describe MP3;
+----------+-------------+------+-----+----------+----------------+
| Field | Type | Null | Key | Default | Extra |
+----------+-------------+------+-----+----------+----------------+
| ID |
int
(11) | | PRI | NULL | auto_increment |
| title | varchar(40) | | MUL | | |
| artist | varchar(20) | | MUL | | |
| album | varchar(30) | | MUL | | |
| duration |
time
| | | 00:00:00 | |
| size |
int
(11) | | | 0 | |
| genre | varchar(10) | | MUL | | |
+----------+-------------+------+-----+----------+----------------+
7 rows in set (0.00 sec)
We want to produce two tables, the first one having only [ID, title, duration, size], while the second one should get [artist, album, genre]. (The second one will also needed to be further split into [artist] and [album, genre] but we can deal with that later).
Here are the instructions to normalize this table:
DROP TABLE IF EXISTS tmp_albums;
CREATE TABLE tmp_albums (album_id INT NOT NULL AUTO_INCREMENT
PRIMARY KEY,
artist varchar(20) not null,
album varchar(30) not null,
genre varchar(10) not null,
KEY artist (artist), KEY album (album), KEY genre (genre));
INSERT INTO tmp_albums
SELECT DISTINCT NULL, artist,album,genre FROM MP3;
DROP TABLE IF EXISTS songs;
CREATE TABLE songs (ID
int
(11) not null auto_increment,
title varchar(40) not null,
duration
time
not null
default
'00:00:00'
,
size
int
(11) not null,
album_id INT(11) NOT NULL,
PRIMARY KEY (ID), KEY title (title), KEY album_id (album_id));
INSERT INTO songs SELECT src.ID, src.title, src.duration,
src.size, album_id
FROM MP3 src INNER JOIN tmp_albums lkp
ON (src.artist =lkp.artist and src.album =lkp.album
and src.genre =lkp.genre);
Eventually, we can use the same technique to normalize the albums into a proper table.
DROP TABLE IF EXISTS artists;
CREATE TABLE artists (artist_id INT NOT NULL AUTO_INCREMENT
PRIMARY KEY,
artist varchar(20) not null,
KEY artist (artist)) ;
INSERT INTO artists
SELECT DISTINCT NULL, artist FROM tmp_albums;
DROP TABLE IF EXISTS albums;
CREATE TABLE albums (album_id
int
(11) not null auto_increment,
album varchar(30) not null,
genre varchar(10) not null,
artist_id INT(11) NOT NULL,
PRIMARY KEY (album_id),
KEY genre (genre), KEY album (album), KEY artist_id (artist_id));
INSERT INTO albums
SELECT src.album_id, src.album, src.genre, artist_id
FROM tmp_albums src
INNER JOIN artists lkp ON (src.artist =lkp.artist);
mysql> describe artists;
+-----------+-------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+-----------+-------------+------+-----+---------+----------------+
| artist_id |
int
(11) | | PRI | NULL | auto_increment |
| artist | varchar(20) | | MUL | | |
+-----------+-------------+------+-----+---------+----------------+
2 rows in set (0.00 sec)
mysql> describe albums;
+-----------+-------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+-----------+-------------+------+-----+---------+----------------+
| album_id |
int
(11) | | PRI | NULL | auto_increment |
| album | varchar(30) | | MUL | | |
| genre | varchar(10) | | MUL | | |
| artist_id |
int
(11) | | MUL | 0 | |
+-----------+-------------+------+-----+---------+----------------+
4 rows in set (0.00 sec)
mysql> describe songs;
+----------+-------------+------+-----+----------+----------------+
| Field | Type | Null | Key | Default | Extra |
+----------+-------------+------+-----+----------+----------------+
| ID |
int
(11) | | PRI | NULL | auto_increment |
| title | varchar(40) | | MUL | | |
| duration |
time
| | | 00:00:00 | |
| size |
int
(11) | | | 0 | |
| album_id |
int
(11) | | MUL | 0 | |
+----------+-------------+------+-----+----------+----------------+
5 rows in set (0.00 sec)
It should be clear now WHAT we have to do. Less clear is HOW. The above instructions seem to imply that we manually copy the field structure from the source table to the lookup and normalized tables.
Actually, that SQL code (except the DESCRIBEs) was produced by this very module and printed to the STDOUT, so that all I had to do was some cut-and-paste. And then we are back to the question of the algorithm. If this is all SQL, where is Perl involved? The answer is that Perl will reduce the amount of information we need to give to the database engine. The information about the field structure and indexes is already in the database. Our Perl module (with a [not so] little help from the DBI) can extract the structure from the database and create the appropriate SQL statements. On the practical side, this means that, before producing SQL code, this module will gather information about the source table. It will issue a "SHOW FIELDS FROM tablename" and a "SHOW INDEX FROM tablename" statements, and parse their results to prepare the operational code.
That's it. It seems a rather small contribution to your average workload, but if you ever have to deal with a project involving several large tables, with many fields, to be transformed into many normalized tables, I am sure you will appreciate the GPL (Golden Perl Laziness) behind this module.
BTW, this is the code used to produce the above SQL statements:
#!/usr/bin/perl -w
use
strict;
use
DBSchema::Normalizer;
my
$norm
= DBSchema::Normalizer->new ({
DSN
=>
"DBI:mysql:music;host=localhost;"
.
"mysql_read_default_file=$ENV{HOME}/.my.cnf"
,
src_table
=>
"MP3"
,
index_field
=>
"album_id"
,
lookup_fields
=>
"artist,album,genre"
,
lookup_table
=>
"tmp_albums"
,
dest_table
=>
"songs"
,
copy_indexes
=> 1,
simulate
=> 1
});
$norm
->
do
();
$norm
->create_lookup_table ({
src_table
=>
"tmp_albums"
,
index_field
=>
"artist_id"
,
lookup_fields
=>
"artist"
,
lookup_table
=>
"artists"
});
$norm
->create_normalized_table ({
src_table
=>
"tmp_albums"
,
lookup_table
=>
"artists"
,
index_field
=>
"artist_id"
,
lookup_fields
=>
"artist"
,
dest_table
=>
"albums"
});
Twenty-five lines of code. Not bad for such a complicated task. But even that could have been replaced by these two one-liners:
album_id album,artist,genre tmp_albums songs 1 1 1)
)->
do
()'
tmp_albums artist_id artist artists albums 1 1 1)
)->
do
()'
(See below item "snew" for more details.)
One thing that this module won't do for you, though, is to decide which columns should stay with the source table and which ones should go to the lookup table. This is something for which you need to apply some database theory, and I don't expect you to know it unless you have studied it (unless you happen to be J.F. Codd) either at school or independently. I am planning (in a very idle and distant way) another module that will analyze a database table and decide if it is a good design or not. The examples from commercial software I have seen so far did not impress me a lot. I am still convinced that humans are better than machines at this task. But, hey! Ten years ago I was convinced that humans were much better than machines at chess, and instead, not long ago, I had to see an IBM box doing very nasty things to Gary Kasparov. So maybe I'll change my mind. In the meantime, I am enjoying my present intellectual superiority and I keep analyzing databases with the same pleasure that I once felt when solving a chess problem.
Simulation mode
This module can do the data transfer for you, or you may want to run it in "simulation mode", by adding simulate => "1" to the constructor parameters. When in simulation mode, the DBSchema::Normalizer will just print the necessary SQL statements to STDOUT, without passing them to the database engine. You can thus check the queries and eventually change them and use them within some other application.
EXPORT
new, snew, create_lookup_table, create_normalized_table
DEPENDENCIES
DBI, DBD::mysql
Architecture
The Normalizer doesn't enforce private data protection. You are only supposed to call the methods which are documented here as public. In the spirit of Perl OO philosophy, nobody will prevent you from calling private methods (the ones beginning with "_") or fiddling with internal hash fields. However, be aware that such behaviour is highly reprehensible, could lead to unpredictable side effects, of which You are entirely, utterly an irrimediably responsible (not to mention that your reputation will be perpetually tarnished, your nephews will call you "Cheating Joe" and you won't be ever - EVER - invited as dinner speaker to any Perl OO conference and even if you manage to sneak in you will find a hair in your soup.)
PORTABILITY
The algorithm used here is general. It was initially developed in C for an embedded RDBMS and there is no reason to assume that it won't work in any other database engine. However, the information about field types and indexes is, in this module, MySQL dependent. At the moment, I haven't found a clean method to get such information in a database-independent way. To adapt this module for a different database, corresponding SQL statements for the MYSQL specific SHOW INDEX and SHOW FIELDS should be provided. Also the syntax for INNER JOIN might not be portable across databases.
CAVEAT
As always, when dealing with databases, some caution is needed. The create_lookup_table() method will drop the lookup table, if exists. Be careful about the name you supply for this purpose. If you want to use an existing lookup table (whose data integrity and relational correspondence you can swear upon), then skip the create_lookup_table() and ask only for create_normalized_table(). Also for this one, a DROP TABLE statement is issued before the creation. Exercise double care on the names you pass to the module.
Be also aware that the tables created by this module are of default type. You may either choose to convert them after the data transfer or run the Normalizer in "simulation mode" and then manually modify the SQL statements.
The Normalizer will usually warn you (and exit with flags and bells) if one or more designated lookup fields in the source table are not indexed. This fact could result in VERY SLOW PERFORMANCE, even for a reasonably low number of records involved. You can choose to ignore this warning, by setting the appropriate parameter, but it is not advisable.
If the source table does not have a primary key (don't laugh, I have seen some of them) then a fatal error is issued, without any possible remedy. The reason is simple. If there is no primary key, the engine doesn't have a way of identifying which rows should go in a JOIN and then your result may have duplicates (and in addition you will be waiting a lot to get it.)
TO DO
1. Parametrizing the statements for fields and indexes information should improve the chances for portability.
# e.g.: MySQL index information comes in this flavor
$mysql_index_info
= {
function_name
=>
"SHOW INDEX FROM $table"
,
info_names
=>
"Table,Non_unique,Key_name,Index_seq,Col_name"
#etc
};
# but it is hard to generalize, especially if another database
# engine defines
# as positive (Unique) what here is negative (Non_unique)
Maybe a more effective way would be to have a polymorphic version of DBSchema::Normalizer, with the base class calling abstract subs, which the descendant classes are supposed to implement. Sounds interesting, even though I feel that I might have some clashes with the DBI.
2. Adding support for intermediate steps in converting should also speed up some ugly cases with nested normalization problems, when the lookup table needs to be further normalized.
3. Adding support for conversion from Zero normal form to First is not straightforward. Some cases are easy to identify and to deal with (e.g. columns Student1, Student2, Student3, StudentN can be converted to column Student_id pointing at a Students table), but others are more subtle and difficult to generalize (e.g. having two column for Male and Female, with yes/no content).
DISCLAIMER
This software can alter data in your database. If used improperly, it can also damage existing data. (And so can any most powerful software on your machine, such as Perl itself. Sorry to scare you, but I have to warn users about potential misuse.) There is NO WARRANTY of any sort on this software. This software is provided "AS IS". Please refer to the GPL, GNU General Public License, Version 2, paragraphs 11 and 12, for more details.
SEE ALSO
DBI, DBD::mysql
Class methods
- new
-
DBSchema::Normalizer->new ({
DSN
=>
$DSN
,
username
=>
$username
,
password
=>
$password
});
new() - object constructor. Requires a hash reference with at least the following keys
DSN
username
password
Alternatively, you may pass one already initialized database handler
dbh
=>
$dbh
Optional fields (in the sense that if you omit them here, you must declare them when calling create_lookup_table or create_normalized_table)
src_table The table in 1st normal form
index_field the
index
field that we need to create
will become foreign key in the source table
and primary key in the lookup table
lookup_fields the fields depending on the
index
,
in a comma-separated list
lookup_table the lookup table
dest_table the Normalized (2nd form) table
Really optional fields. You may not mention them at all. Their default is 0.
copy_indexes three
values
:
"no"
or
"0"
:
no
indexes are copied
"yes"
or
"1"
: indexes from the source table will
be immediately replicated to the
destination table
"later"
or
"2"
: indexes will be created
after
the
data transfer,
as an ALTER TABLE statement.
It may speed up the insertion
for
large tables.
verbose
if
"1"
, messages indicating what is going on
will be sent to STDOUT.
Using
"2"
, even more verbose information is
given
(all queries printed
before
execution);
Level
"3"
will also show details about src_table
fields and indexes;
ignore_warning
if
"1"
, warning on missing indexes on lookup fields
are ignored, and the requested operation carried
out even at a price of long waiting. Default
"0"
simulate
if
"1"
,
no
operation is carried out
but the queries are printed to STDOUT (as in
verbose
=> 2)
note: src_table, dest_table and lookup_table cannot be called src or lkp, which are used internally by the Normalizer. If such names are given, a fatal error is issued.
If the keys for src_table, index_field, lookup table and fields are missing, they can (actually they MUST) be later provided by calls to create_lookup_table() and create_normalized_table().
- snew
-
snew is a shortcut for new(). It is called with parameters passed by position instead of using a hash reference. It is a "quick-and-dirty" ("dirty" being the operational word) method intended for the impatient who does not want to write a script. Assumes that you have a configuration file for MySQL with username and password. Parameters are passed in this order:
host
database
source table
index
field
lookup fields
lookup table
destination table
copy indexes
verbose
simulate
Here is an example of one-liner normalization call:
album_id album,artist,genre tmp_albums songs 1 1 1)
)->
do
()'
Note: ALL 11 parameters must be passed, or an "use of uninitialized value" error is issued.
This one-liner is equivalent to the following script:
#!/usr/bin/perl
no
warnings;
# Yeah. No warnings. I said it is equivalent,
# not recommended.
no
strict;
# Yup. No strict either.
use
DBSchema::Normalizer;
$norm
= DBSchema::Normalizer->new (
{
DSN
=>
"DBI:mysql:music;host=localhost;"
.
"mysql_read_default_file=$ENV{HOME}/.my.cnf"
,
src_table
=>
"MP3"
,
index_field
=>
"album_id"
,
lookup_fields
=>
"artist,album,genre"
,
lookup_table
=>
"tmp_albums"
,
dest_table
=>
"songs"
,
copy_indexes
=> 1,
verbose
=> 1,
simulate
=> 1,
});
$norm
->
do
();
It is definitely not as safe as the normal call. However, TMTOWTDI, and it's your call. I am using it, but I don't recommend it. Read my lips: I DON'T RECOMMEND IT.
- do
-
do();
do() performs the Normalization according to the parameters already received. Internally calls create_lookup_table() and create_normalized_table()
Will fail if not enough parameters have been supplied to new()
- create_normalized_table()
-
create_normalized_table() will create a 2nd normal form table, getting data from a source table and a lookup table. Lookup fields in the source table will be replaced by the corresponding index field in the lookup table.
If called without parameters, assumes the parameters passed to the object constructor.
Parameters are passed as a hash reference, and are the same given to new() except DSN, username and password. None are compulsory here. The missing ones are taken from the constructor. However, a check is done to ensure that all parameters are passed from either sub.
- create_lookup_table
-
create_lookup_table() will create a lookup table, extracting repeating fields from a 1st normal form table. A numeric primary key is created.
When called without parameters, assumes the values passed to the object constructor (new).
Parameters are passed as a hash reference, and should include the following
src_table table where to take the
values
from
lookup_fields which fields to take
lookup_table table to create
index_field primary key (will be foreign key in src_table)
to be created
AUTHOR
Giuseppe Maxia, giuseppe@gmaxia.it
COPYRIGHT
The DBSchema::Normalizer module is Copyright (c) 2001 Giuseppe Maxia, Sardinia, Italy. All rights reserved.
You may distribute this software under the terms of either the GNU General Public License version 2 or the Artistic License, as specified in the Perl README file.
The embedded and encosed documentation is released under the GNU FDL Free Documentation License 1.1