[REBOL] Re: Temporal data [was is REBOL OO]
From: SunandaDH:aol at: 14-Jan-2004 5:15
Hi Gerard:
For those of you reading this with no interest in the issues involved in
designing realtime reservations systems, here's a couple of related REBOL puzzles
-- and I really would like the answers to these; they'd make building such a
system in REBOL so much easier -- see last couple of paragraphs of this email.
Puzzle 1
We have a bitmap, where each 1-bit represents the availability of a resource
on a given day, eg
random/seed: 100
data: copy []
loop 200 [
append data to char! random 255
]
bit-map: charset data
What we need is the location of the first occurrence of n consecutive 1-bits:
available? bit-map 5
available? bit-map 12
Puzzle 2:
256 bits isn't enough for a bit-per-day for a whole year. We need two
bitmaps.
Extend available? to find n consecutive bits within a bitset, or across a
bitset boundaries:
bit-map1: charset data
bit-map2: charset skip data random 50
available? [bit-map1 bit-map2] 5
available? [bit-map1 bit-map2] 12
> I really appreciate your comment and if you feel like you could let me see
> the state of your work
> I would be grateful for too. But I will not either be furious against you
if
> you don't because I know what sum of work it
> represents.
The state of my work is an in-brain design for a system way larger than the
one you want.
But here are some ideas, some of which may be relevant....
SEE IF IT WORKS ANYWAY
You may well find that you can do what you want with standard software -- in
which case you don't have a problem except for scaling as your client grows
into a premier nation-wide business.
MACHINES, LOTS OF THEM
You might just be able to throw hardware at the problem. A dozen USD300 Linux
boxes from Walmart each running part of the availability search may solve the
problem.
STANDARD DATA WAREHOUSE
An off-the-shelf data warehouse package may work for you.
Data warehousing is designed to take large lumps of data, reduce it down in
ways that make it extremely easy to sort and sift and analyse, but a total pig
if you ever needed to update it. Most data warehousing users throw all their
historical data into the warehouse every few months or so, so dating happens
rarely.
A reservations system, in effect, uses data warehouse techniques for fast
searching, but on an availability database that gets rebuilt every day. That
means most queries are in two parts:
1. Query the availability database for a list of alternatives
2. Check those against the actual inventory to see if they are still
available.
You can probably see one obvious flaw in that -- if a booking is cancelled,
the stock won't show up in the availability database until it is rebuilt. So,
for the rest of that day (or until the availability database is rebuilt) that
item can't be found in searches, and so a sale may be lost.
That may not matter too much for a flight that happens in three months --
there is still plenty of time to sell it before departure time. But it could be
lost revenue if the flight goes today. That's why:
1. cancellation charges are so high close to departure date
2. Look at most holiday/reservations systems on the web. They almost all have
a "Last minute" or "late bargains" or some such search feature. Why? Because
those searches run in a completely different way -- either against the live
inventory data, or against another specialised search database.
BUILD YOUR OWN SEARCH DATABASE
If off-the-shelf warehousing is too slow for real-time queries (or it takes
too long to rebuild the database each day), then think about building your own.
The main things to do are to reduce data down as small as possible into data
structures that you can search very fast. And are carefully constructed to
handle the typical queries the system expects.
One method is to use bit-maps -- hence the opening puzzle.
If, say, you have one bit-map for "10pm-11pm Singles Special" with a bit set
for each day of the year that is available, and another bit-map for "Senior
discount days" for the days when you offer reduced entry to seniors, then
answering the question...
I'm a senior: do you have any weekend singles specials at a discount for me?
...is pretty trivial -- assuming, of course, you are using a language that
can dice and slice and rifflle shuffle long strings of bits.
Which is why I wrote:
<<But I'm still fairly agnostic about whether REBOL is a great tool for
this.>>
Sunanda.<
