33.2.1 English Auctions

English Auctions are also known as increasing or ascending price auctions. The auctioneer asks for starting price and the bidders increase the price until the item sells or the price offered is not high enough and the auction fails. This is the form that most of us know. It is how eBay works. Sort of eBay is more complicated.

33.2.2 Japanese Auctions

The Japanese auction is an ascending price auction with levels or tiers. Once you drop out, you cannot re-enter the bidding. For example, if the starting bid is $10, every interested bidder agrees to meet it. We then go up a level or $15; anyone who fails to meet the new level is out and cannot re-enter the bidding, even if they are willing to pay a higher price later. You have a lot of information—the number of other bidders at every level and their exit prices. The auction continues until only one bidder remains.

33.2.3 Dutch Auctions

Dutch Auctions are also known as decreasing or descending price auctions. The auctioneer asks for high starting price, and then drops the price lower and lower in steps until the item clears or auction fails. This form of auction used to be popular with small retail stores decades ago. The items would be put in the store window with a flip-chart price tag and an announcement that the price would decrease $x per day until sold.

Today, the Dutch auction is hidden in online clearance sales. Instead of looking at the store window on Main Street, you get a series of email advertisements at lower and lower prices.

33.2.4 Vickrey Auctions

Obviously, a winner can have “buyer’s remorse”—the feeling that they paid too much for the item. If you have seen bidding wars on eBay or real life, you understand how emotions can get mixed up in the heat of the moment.

The solution is Vickrey or second price auctions. The highest bidder wins, but the price paid is between the highest and second highest bids. The winner cannot be unhappy; he paid less than his bid and won. The losers cannot be unhappy; they all bid less than the winner.

The eBay proxy bid system is a form of second price auction. A variant of a Vickrey auction, named generalized second-price auction, is used in Google’s and Yahoo!’s online advertisement programs. The computer runs hundreds or thousands of auctions for the on-line adverting slots they sell.

33.2.5 Auction Schema

What would the basic tables be? Let’s start with the bidders and a simple skeleton.

CREATE TABLE Bidders
(bidder_id INTEGER NOT NULL PRIMARY KEY,
..)

When we log in an item for an auction, we need to identify the item, get a starting bid amount. The minimum bid is also called the reserve amount. If there is no bid, equal or greater than that amount, the auction is void.

Initially we do not have

CREATE TABLE Items
(item_id INTEGER NOT NULL PRIMARY KEY,
item_name VARCHAR(25) NOT NULL,
initial_bid_amt DECIMAL (12,2) NOT NULL
 CHECK(initial_bid_amt >= 0.00),
minimum_bid_amt DECIMAL (12,2) NOT NULL
 CHECK(initial_bid_amt >= 0.00));

A bid has to be timestamped and the bid amounts have to increase over time.

CREATE TABLE Bids
(item_id INTEGER NOT NULL
REFERENCES Items (item_id),
bidder_id INTEGER NOT NULL
REFERENCES Bidders (bidder_id),
bid_timestamp TIMESTAMP(0) DEFAULT CURRENT_TIMESTAMP NOT NULL,
bid_amt DECIMAL (12,2) NOT NULL
 CHECK(bid_amt >= 0.00),
PRIMARY KEY (item_id, bidder_id, bid_timestamp)
);

I recommend using a bid insertion procedure to ensure that bids are always increasing (or decreasing in the case of a Dutch auction) rather than in the DDL. The reason is that a bid can be pulled from the bids table.

33.3.1 LIFO Cost as a VIEW

Consider this VIEW:

CREATE VIEW LIFO (stock_date, unit_price, tot_qty_on_hand, tot_cost)
AS
SELECT W1.purchase_date, W1.unit_price, SUM(W2.qty_on_hand), SUM(W2.qty_on_hand *
W2.unit_price)
FROM WidgetInventory AS W1,
 WidgetInventory AS W2
WHERE W2.purchase_date <= W1.purchase_date
GROUP BY W1.purchase_date, W1.unit_price;

A row in this VIEW tells us the total quantity on hand, the total cost of the goods in inventory, and what we were paying for items on each date. The quantity on hand is a running total. We can get the LIFO cost with this query:

SELECT (tot_cost - ((tot_qty_on_hand - :order_qty) * unit_price))
AS cost
FROM LIFO AS L1
WHERE stock_date
 = (SELECT MIN(stock_date)
FROM LIFO AS L2
 WHERE tot_qty_on_hand >= :order_qty);

This is straight algebra and a little logic. You need to find the most recent date when we had enough (or more) quantity on hand to meet the order. If, by dumb blind luck, there is a day when the quantity on hand exactly matched the order, return the total cost as the answer. If the order was for more than we have in stock, then return nothing. If we go back to a day when we had more in stock than the order was for, look at the unit price on that day, multiply by the overage, and subtract it.

33.3.2 CASE Expressions

Alternatively, you can use a derived table and a CASE expression. The CASE expression computes the cost of units that have a running total quantity less than the :order_qty and then performs algebra on the final block of inventory, which would put the running total over the limit. The outer query does a sum on these blocks:

SELECT SUM(W3.v) AS cost
FROM (SELECT W1.unit_price
* CASE WHEN SUM(W2.qty_on_hand) <= :order_qty
 THEN W1.qty_on_hand
 ELSE :order_qty
 - (SUM(W2.qty_on_hand) - W1.qty_on_hand)
 END
FROM WidgetInventory AS W1,
 WidgetInventory AS W2
 WHERE W1.purchase_date <= W2.purchase_date
 GROUP BY W1.purchase_date, W1.qty_on_hand, W1.unit_price
HAVING (SUM(W2.qty_on_hand) - W1.qty_on_hand) <= :order_qty)
 AS W3(v);

FIFO can be found with a similar VIEW or derived table:

CREATE VIEW FIFO (stock_date, unit_price, tot_qty_on_hand, tot_cost)
AS
SELECT W1.purchase_date, W1.unit_price,
 SUM(W2.qty_on_hand), SUM(W2.qty_on_hand *
W2.unit_price)
FROM WidgetInventory AS W1,
 WidgetInventory AS W2
WHERE W2.purchase_date >= W1.purchase_date
GROUP BY W1.purchase_date, W1.unit_price;

With the corresponding query:

SELECT (tot_cost - ((tot_qty_on_hand - :order_qty) * unit_price)) AS cost
FROM FIFO AS F1
WHERE stock_date
  = (SELECT MAX (stock_date)
FROM FIFO AS F2
 WHERE tot_qty_on_hand >= :order_qty);

These queries and VIEWs only told us the value of the Widget inventory. Notice that we never actually shipped anything from the inventory.

33.3.3 Updating Inventory

How to write the UPDATE statements that let us change this simple inventory.

What we did not do in part 1 was to actually update the inventory when the Widgets were shipped out. Let’s build another VIEW that will make life easier.

CREATE VIEW StockLevels (purchase_date, previous_qty, current_qty)
AS
SELECT W1.purchase_date,
 SUM(CASE WHEN W2.purchase_date < W1.purchase_date
THEN W2.qty_on_hand ELSE 0 END),
 SUM(CASE WHEN W2.purchase_date <= W1.purchase_date
THEN W2.qty_on_hand ELSE 0 END)
FROM WidgetInventory AS W1,
 WidgetInventory AS W2
WHERE W2.purchase_date <= W1.purchase_date
GROUP BY W1.purchase_date, W1.unit_price;
StockLevels

Using CASE expressions will save you a self-join.

CREATE PROCEDURE RemoveQty (IN my_order_qty INTEGER)
LANGUAGE SQL
BEGIN
IF my_order_qty > 0
THEN
UPDATE WidgetInventory
SET qty_on_hand
= CASE
WHEN my_order_qty
 >= (SELECT current_qty
 FROM StockLevels AS L
WHERE L.purchase_date
 = WidgetInventory.purchase_date)
THEN 0
WHEN my_order_qty
 < (SELECT previous_qty
FROM StockLevels AS L
 WHERE L.purchase_date
 = WidgetInventory.purchase_date)
THEN WidgetInventory.qty_on_hand
ELSE (SELECT current_qty
FROM StockLevels AS L
 WHERE L.purchase_date = WidgetInventory.purchase_date)
- my_order_qty END;
END IF;
-- remove empty bins
DELETE FROM WidgetInventory
WHERE qty_on_hand = 0;
END;

Another inventory problem is how to fill an order with the smallest or greatest number of bins. This assumes that the bins are not in order, so you are free to fill the order as you wish. Using the fewest bins would make less work for the order pickers. Using the greatest number of bins would clean out more storage in the warehouse.

For example, with this data, you could fill an order for 80 widgets by shipping out bins (1, 2, 3) or bins (4, 5). These bins happen to be in date and bin number order in the sample data, but that is not required.

Mathematicians call it (logically enough) a bin-packing problem and it belongs to the NP-complete family of problems. This kind of problem is too hard to solve for the general case because the work requires trying all the combinations, and this increases too fast for a computer to do it.

However, there are “greedy algorithms” that are often nearly optimal. The idea is to begin by taking the “biggest bite” you can until you have met or passed your goal. In procedural languages, you can back-track when you go over the target amount and try to find an exact match or apply a rule that dictates from which bin to take a partial pick.