Normalization

When I wrote my web-based recipe management program, I added two features that can affect how it handles ingredient amounts:

• resizing a recipe for larger or smaller numbers of servings, and
• expressing a recipe ingredients in different measurement scale.

Both of these features change ingredient amounts, either in size, or in unit-of-measure, or both.

But, those changes come with a price; ingredient measures that made sense for the original recipe often do not make sense for the resized or rescaled recipe. A recipe that calls for "1 1/2 Cups" of flour (easily measured on most measuring cups) might now call for "1.166667 Cups" of flour (huh?). Or, a recipe that called for a "1.5 Kilogram" roast might now call for a "3.3069339328 Pound" roast.

A cook can have difficulty accurately measureing ingredients where the amounts, as a result from upsizing or downsizing a recipe, or changing the measurement units from one scale to another, become unmeasurable using the usual measuring tools (measuring cups, measuring spoons, scales, etc.). The recipe program could help by re-expressing those unusual measurements as the sum of the usual measurements. If, instead of "33.3333 Tbsp (Imperial)", the recipe program could (given the proper option) express the measurement as "1 Pint (Imperial) plus 1 Tablespoon (Imperial) plus 1 Teaspoon (Imperial)", the cook might have less difficulty portioning out the ingredient.

This idea sat with me for quite a while. I mulled over various ways to re-express ingredient amounts, and various algorithms to do so, and quietly set the problem aside for another day. Recently, I picked up the problem again, and I decided to play with it to see what I could accomplish. I do not claim that I have solved this "once and for all", nor do I claim that my solution will perfectly suit every recipe or every cook, but, at least, I have a solution.

Currently, that solution sits in a C program, and I soon will incorporate the algorithm into my recipe program. This solution will also take some unobtrusive changes to the database that supports my recipe program, specifically in the "conversion" table that provides conversion ratios between different measurement units. For now, though, I content myself with a simple commandline program that "normalizes" given amounts.

For example:

./normalize Volume 40.7 Imperial Tablespoon
40.700000	Imperial Tablespoon normalizes to
  1.000	Imperial Pint
  8.000	Imperial Tablespoon
  2.000	Imperial Teaspoon
  1.000	Imperial Pinch

./normalize Volume 42.75 Imperial Fluid Ounce
42.750000	Imperial Fluid Ounce normalizes to
  1.000	Imperial Quart
  4.000	Imperial Tablespoon
  1.000	Imperial Teaspoon
  2.000	Imperial Pinch

./normalize Volume 8 Imperial Tablespoon
8.000000	Imperial Tablespoon normalizes to
  8.000	Imperial Tablespoon

./normalize Volume 95.0625 Imperial Gallon
95.062500	Imperial Gallon normalizes to
  95.000	Imperial Gallon
   1.000	Imperial Cup

Note: the volume of an "Imperial Teaspoon" holds 8 "Imperial Pinches"

So, how did I do it? Well, it took a combination of two database tables (the "measure" and the "conversion" tables), and a fair bit of logic. Let me tell you about it...

The database tables

For normalization, I used two tables: the measure table, which names the various units-of-measure, and relates them into scales and dimensions, and the conversion table, which describes the conversion ratios between various units-of-measure.

The "measure" table

The "measure" table holds the specifics of each unique unit-of-measure. The ingredients list of each recipe will reference this table, to give consistancy to the measurement units used by the recipe program, and for the convenience of consistant recipe creation and display.

Each row of the table describes one unit-of-measure. It includes the "dimension" being measured ("Count" for a simple count of items, "Weight" for units-of-measure that describe weight, and "Volume" for units-of-measure that describe volume), the measurement "scale" used (for Volume and Weight, "Metric", "Imperial" and "US"), and both the name of the unit-of-measure, and its common abbreviation. Each unit-of-measure has a small, unique, numeric identifier, used to join the measure table to other tables (the "ingredient" table, for each recipe, and the "conversion" table for amount conversions and normalization).

CREATE TABLE measure		(
  measure_id		SMALLINT UNSIGNED NOT NULL PRIMARY KEY,
  measure_dimension	ENUM('Count', 'Weight', 'Volume') NOT NULL,
  measure_scale		ENUM('Metric', 'Imperial', 'US', 'Other') NOT NULL,
  measure_unit		VARCHAR(15) NOT NULL,
  measure_abbr		VARCHAR(6)
) COMMENT 'Holds values for preset measurement units',
  ENGINE InnoDB,
  DEFAULT CHARACTER SET ascii;

This table contains the following values:

+------------+-------------------+---------------+--------------+--------------+
| measure_id | measure_dimension | measure_scale | measure_unit | measure_abbr |
+------------+-------------------+---------------+--------------+--------------+
|          1 | Weight            | Metric        | Gram         | g            |
|          2 | Weight            | Metric        | Kilogram     | kg           |
|          3 | Volume            | Metric        | Millilitre   | ml           |
|          4 | Volume            | Metric        | Litre        | l            |
|          5 | Weight            | Imperial      | Ounce        | oz           |
|          6 | Weight            | Imperial      | Pound        | lb           |
|          7 | Volume            | Imperial      | Pinch        | pn           |
|          8 | Volume            | Imperial      | Teaspoon     | tsp          |
|          9 | Volume            | Imperial      | Tablespoon   | tbsp         |
|         10 | Volume            | Imperial      | Fluid Ounce  | fl oz        |
|         11 | Volume            | Imperial      | Cup          | c            |
|         12 | Volume            | Imperial      | Pint         | pt           |
|         13 | Volume            | Imperial      | Quart        | qt           |
|         14 | Volume            | Imperial      | Gallon       | gal          |
|         15 | Weight            | US            | Ounce        | oz           |
|         16 | Weight            | US            | Pound        | lb           |
|         17 | Volume            | US            | Pinch        | pn           |
|         18 | Volume            | US            | Teaspoon     | tsp          |
|         19 | Volume            | US            | Tablespoon   | tbsp         |
|         20 | Volume            | US            | Fluid Ounce  | fl oz        |
|         21 | Volume            | US            | Cup          | c            |
|         22 | Volume            | US            | Pint         | pt           |
|         23 | Volume            | US            | Quart        | qt           |
|         24 | Volume            | US            | Gallon       | gal          |
|         25 | Count             | Other         | Slice        | slice        |
|         26 | Count             | Other         | Clove        | clove        |
|         27 | Count             | Other         | Serving      | svg          |
+------------+-------------------+---------------+--------------+--------------+

While this organization facilitates the current program design, I can conceive of a time where some of the "fixed" values (dimension and scale in particular) will have to change, for additional dimensions and/or additional scales. But, that's a problem for future me.

The "conversion" table

The "conversion" table expresses the relationships between various units-of-measure. Rows either describe the ratio between one unit within a single dimension/scale to another unit in the same dimension/scale, or they describe the ratio between one unit within a dimension/scale to a single unit within another scale within the same dimension.

From the first type of row, we can derive the size of any one unit as compared to any other unit within that specific scale. The relationships expressed in this type of row are something like "1 Imperial Cup contains 16 Imperial Tablespoons", or "1 Metric Kilogram contains 1000 Metric Grams". From the second type, we can derive the conversion factor between two different scales. The relationships expressed in this type of row are something like "1 Imperial Ounce contains 28.349523125 Metric Grams" or "1 Imperial Pinch contains 1.2009504226 US Pinches".

I made the concious decision not to express all conversions relative to a common unit-of-measure. While each scale standardizes the size of units within a scale relative to each other, there are a variety of (loosly defined) conversions between scales, and depending on where you get your information from, these ratios can vary widely. Had I chose a common unit-of-measure, and an incorrect or inaccurate conversion, all of the rows of the table would need later correcting. With the chosen approach, only the cross-scale ratios need to change if found inaccurate.

So, I define the "conversion" table as

CREATE TABLE conversion	(
  conv_f_measure	SMALLINT UNSIGNED NOT NULL,
  conv_t_measure	SMALLINT UNSIGNED NOT NULL,
  conv_factor		FLOAT NOT NULL,
  FOREIGN KEY (conv_f_measure) REFERENCES measure(measure_id),
  FOREIGN KEY (conv_t_measure) REFERENCES measure(measure_id),
  PRIMARY KEY (conv_f_measure, conv_t_measure)
) COMMENT 'Convert one unit of measure to another',
  ENGINE InnoDB,
  DEFAULT CHARACTER SET ascii;

and populate it with

+----------------+----------------+--------------+
| conv_f_measure | conv_t_measure | conv_factor  |
+----------------+----------------+--------------+
|              2 |              1 |         1000 |
|              3 |              7 | 1.3514905027 |
|              3 |             17 | 1.6230730897 |
|              4 |              3 |         1000 |
|              5 |              1 | 28.349523125 |
|              6 |              5 |           16 |
|              7 |             17 | 1.2009504226 |
|              8 |              7 |            8 |
|              9 |              8 |            3 |
|             10 |             11 |          0.1 |
|             11 |              9 |           16 |
|             12 |             11 |            2 |
|             13 |             12 |            2 |
|             14 |             13 |            4 |
|             15 |              1 | 28.349523125 |
|             15 |              5 |            1 |
|             16 |             15 |           16 |
|             18 |             17 |            8 |
|             19 |             18 |            3 |
|             20 |             21 |        0.125 |
|             21 |             19 |           16 |
|             22 |             21 |            2 |
|             23 |             22 |            2 |
|             24 |             23 |            4 |
+----------------+----------------+--------------+

where conv_f_measure and conv_t_measure are both values of measure.measure_id

To make the table contents clearer, let's look at it again, using measure scale and measure unit instead of measure_id

  SELECT f.measure_dimension AS Dimension,
         f.measure_scale AS From_scale,
         f.measure_unit AS From_unit,
         conv_factor,
         t.measure_scale AS To_scale,
         t.measure_unit AS To_unit
    FROM conversion, measure f, measure t
   WHERE f.measure_id = conv_f_measure
     AND t.measure_id = conv_t_measure
ORDER BY Dimension, From_scale;
+-----------+------------+-------------+--------------+----------+------------+
| Dimension | From_scale | From_unit   | conv_factor  | To_scale | To_unit    |
+-----------+------------+-------------+--------------+----------+------------+
| Weight    | Metric     | Kilogram    |         1000 | Metric   | Gram       |
| Weight    | Imperial   | Ounce       | 28.349523125 | Metric   | Gram       |
| Weight    | Imperial   | Pound       |           16 | Imperial | Ounce      |
| Weight    | US         | Pound       |           16 | US       | Ounce      |
| Weight    | US         | Ounce       | 28.349523125 | Metric   | Gram       |
| Weight    | US         | Ounce       |            1 | Imperial | Ounce      |
| Volume    | Metric     | Millilitre  | 1.3514905027 | Imperial | Pinch      |
| Volume    | Metric     | Millilitre  | 1.6230730897 | US       | Pinch      |
| Volume    | Metric     | Litre       |         1000 | Metric   | Millilitre |
| Volume    | Imperial   | Pint        |            2 | Imperial | Cup        |
| Volume    | Imperial   | Pinch       | 1.2009504226 | US       | Pinch      |
| Volume    | Imperial   | Quart       |            2 | Imperial | Pint       |
| Volume    | Imperial   | Teaspoon    |            8 | Imperial | Pinch      |
| Volume    | Imperial   | Gallon      |            4 | Imperial | Quart      |
| Volume    | Imperial   | Tablespoon  |            3 | Imperial | Teaspoon   |
| Volume    | Imperial   | Fluid Ounce |          0.1 | Imperial | Cup        |
| Volume    | Imperial   | Cup         |           16 | Imperial | Tablespoon |
| Volume    | US         | Quart       |            2 | US       | Pint       |
| Volume    | US         | Teaspoon    |            8 | US       | Pinch      |
| Volume    | US         | Gallon      |            4 | US       | Quart      |
| Volume    | US         | Tablespoon  |            3 | US       | Teaspoon   |
| Volume    | US         | Fluid Ounce |        0.125 | US       | Cup        |
| Volume    | US         | Cup         |           16 | US       | Tablespoon |
| Volume    | US         | Pint        |            2 | US       | Cup        |
+-----------+------------+-------------+--------------+----------+------------+

When we view the contents of the conversion table this way, four details stand out:

1. I have expressed the conversion factors between scales to more decimal places than I express other conversion factors,
2. I express Scale-to-scale conversions in the finest (smallest) units of each scale
3. In-scale conversion factors bridge from grosser units to finer units (the conv_factor is >= 1.0), and
4. Two in-scale conversions violate this by moving from a finer unit to a grosser unit

Because scales may not have comparable units, I want scale-to-scale conversions to start off with as many significant digits as possible. Later computations will reduce the significant digits, and I do not wish to lose too much accuracy with that reduction. Thus I make scale-to-scale conversions with as many significant digits as I can.

Additionally, I make scale-to-scale conversions only at the finest (smallest) unit, so that the amounts in question, for the most part, remain greater than, or equal to, 1.0. Because of the accuracy of the tools the cook will use, at the finest measure, fractional values will have only an insignificant affect on most recipes. With this decision, I can reduce the side-effects of floating-point mathematics to a level that will not affect the recipe.

In-scale conversions progress from grosser to finer units. This serves two purposes; the first is to standardize the navigation between units (navigating "upward" to a coarser unit will always reduce the amount, while navigating "downward" will always increase the amount), and it facilitates navigation to the scale-to-scale "bridge" conversion.

But, two units stand out: "Imperial Fluid Ounce" and "US Fluid Ounce". These two in-scale conversions violate the "coarser to finer" approach that the other units in their scales use. I deliberately made these units go "against the grain" here, to keep them out of the mainline of normalization. In "homemade" recipes, you often find recipe ingredients based on commercially available products ("19 Fluid Ounce can of Crushed Pineapple", or "20 Fluid Ounce can of Cream of Tomato soup"), but you rarely use these measures otherwise. And, in resizing these recipes, these sorts of units-of-measure can cause more confusion than necessary. So, while I allow such measures in recipes (you can hardly say no to them), I don't scale to these measure units. The way my logic detects these odd-ball (or, as I call them, "spur") measure units is to note that the conversion factor is less than 1.0. But, that's getting ahead of the story.

The algorithm

Given an AMOUNT and a MEASURE (dimension/scale/unit or measure_id)

1: convert "spur" measurement into mainline measurement

   WHILE we can retrieve a conversion
   WHERE both the source and target measure are in the same scale in the same dimension
   AND the "source" (grosser) measure identifies the current MEASURE
   AND the conversion factor < 1.0
   DO
     multiply the AMOUNT by the conversion factor, and
     set the MEASURE to the "target" (finer) measure
   DONE

The associated SQL for this "coarse-to-fine" spur conversion retrieval looks like:

  SELECT conv_t_measure, conv_factor
    FROM conversion, measure f, measure t 
   WHERE conv_f_measure = @MEASURE
     AND conv_factor < 1.0
     AND f.measure_id = conv_f_measure 
     AND t.measure_id = conv_t_measure 
     AND t.measure_dimension = f.measure_dimension 
     AND t.measure_scale = f.measure_scale;

2: convert this mainline measurement to the finest unit in the scale

   WHILE we can retrieve a conversion
   WHERE both the source and target measure are in the same scale in the same dimension
   AND the "source" (grosser) measure identifies the current MEASURE
   AND the conversion factor >= 1.0
   DO
     multiply the AMOUNT by the conversion factor, and
     set the MEASURE to the "target" (finer) measure
   DONE

The associated SQL for this "coarse-to-fine" mainline conversion retrieval looks like:

  SELECT conv_t_measure, conv_factor
    FROM conversion, measure f, measure t 
   WHERE conv_f_measure = @MEASURE
     AND conv_factor >= 1.0
     AND f.measure_id = conv_f_measure 
     AND t.measure_id = conv_t_measure 
     AND t.measure_dimension = f.measure_dimension 
     AND t.measure_scale = f.measure_scale;

3: progressively adjust the measure to coarser units, saving the remainder and adjusting the amount until we get to a zero amount, or have reached the coarsest unit within the scale

   round AMOUNT to nearist whole number

   WHILE AMOUNT > 0.0
   AND we can retrieve a fine-to-coarse conversion for the current MEASURE
       WHERE both the source and target measure are in the same scale in the same dimension
       AND the "target" (finer) measure identifies the current MEASURE
       AND the conversion factor >= 1.0
   DO
     take a REMAINDER of AMOUNT modulo the conversion factor
     IF the REMAINDER > 0.0
     THEN
        emit the combination of MEASURE and REMAINDER as a partial measure
     FI
     subtract the REMAINDER from the AMOUNT
     divide the AMOUNT by the conversion factor
     round AMOUNT to nearist whole number
     set the MEASURE to the "source" (coarser) measure
   DONE

   IF we still have an AMOUNT > 0.0
   THEN
     emit the combination of MEASURE and AMOUNT as a partial measure
   FI

The associated SQL for this "fine-to-coarse" conversion retrieval looks like:

  SELECT conv_f_measure, conv_factor
    FROM conversion, measure f, measure t
   WHERE conv_t_measure = @MEASURE
     AND conv_factor >= 1.0
     AND f.measure_id = conv_f_measure
     AND t.measure_id = conv_t_measure
     AND t.measure_dimension = f.measure_dimension
     AND t.measure_scale = f.measure_scale;

4: At this point, we have emitted a list of measurements, starting at the finest unit-of-measure and ending at the coursest unit-of-measure, that when summed together give our original amount and measure, which we can then express as part of our recipe.