|
by Philip Lambert
Prime Number
In mathematics, a prime number is a natural
number which has exactly two distinct natural number divisors: 1 and
itself. The number 1 is by definition not a prime number.
Generating Prime Numbers
If you scan the Internet for example PL/SQL functions
for generating prime numbers and you will find many examples.
However, it is actually quite straight forward to generate them from
a single SQL statement.
A useful technique with SQL for generating data
is using the hierarchical join syntax CONNECT BY. The following
statement generates ten rows numbered 1 throught to 10:
SELECT
LEVEL
FROM dual
CONNECT BY LEVEL <= 10
So integrating this approach in the following
statement, it is possible to generate all of the prime numbers under
a thousand (excluding 1 which is technically not a prime number):
SELECT x.prime_no,
RANK() OVER(ORDER BY x.prime_no) rank
FROM
(
SELECT LEVEL prime_no
FROM dual
CONNECT BY LEVEL <= 1000
) x
WHERE
(
SELECT COUNT(DECODE(MOD(x.prime_no,ROWNUM),0,'X',NULL))
FROM dual
CONNECT BY LEVEL <= ROUND(SQRT(x.prime_no),0)
) = 1
AND x.prime_no > 1;
So we now have a useful means of generating
prime numbers with SQL and by adding the analytic rank function we
also have the ranking:
PRIME_NO RANK
-------- ----
2 1
3 2
5 3
7 4
11 5
13 6
17 7
19 8
23 9
29 10
...
Prime Number Product
A product of any number of prime numbers will
not result in a prime number. And this result will only have factors
that are prime numbers, and only the original prime numbers. So it
is possible to multiply two or more prime numbers and decode the
result back to the original prime numbers.
For example:
3 x 7 = 21
To decode, step through each prime number and
see if it is a factor of the result.
MOD(21,3) = 0 ... so 3 is a factor of the prime number product.
MOD(21,5) = 1 ... so not a factor
MOD(21,7) = 0 ... so 7 is a factor and a
component
Database Design
From a database design perspective, this gives
us the opportunity to hold a set of foreign key values in a single
column. This may not be too appealing to the purists amongst us, but
it can have huge benefits by eliminating very large child tables.
To make this work, the candidate child table needs to be a pure
intersect table between the parent table and a small reference table
with a finite set of values where each entry can be assigned a
unique prime number (an alternative key). The Oracle numeric
data type has a precision of 38 significant figures, so the prime
number product can represent a lot of numbers, but is not limitless.
The prime number product on the parent table
can be decoded to identify the child entries. Adding a new key value
is achieved by multiplying the existing prime number product with
the new prime number, and to remove a key is achieved by dividing
the product by the key's prime number.
Another benefit of using prime number product
is being able to easily identify whether a subset of values is
completely within a superset of values. A set of values can have a
prime number product calculated for it and if found to be a factor
of the superset prime number product, then it can be considered to
be a complete subset.
For example:
Set A consists of (5,11) product A
= 55
Set B consists of (3,5,11,17)
product B = 2805
To determine that set A is a subset of B, check
that product A is a factor of product B. In SQL we would use the MOD
function, MOD(2805,55) = 0, i.e.
it is a subset.
A SQL approach to decoding the prime number
product would be quite straight forward:
SELECT a.*,
b.ref_desc
FROM my_main_table a,
my_ref_table b
WHERE MOD(a.prime_number_product, b.prime_number) = 0
AND a.id = :p_id
Calculating a Product
No aggregate functions exist in Oracle that
allow you to calculate the product of a set of values, but there is a
simple work around using logarithms. To multiply two numbers using
log tables requires looking up the log for both numbers and adding
the two together and then look up its exponent (opposite to log) to
give the result. So using a base 10 logarithm, the prime number
product can be aggregated in a query as follows ...
SELECT POWER(10,SUM(LOG(10,b.prime_number)))
prime_no_prdct
FROM my_ref_table b
WHERE b.id IN (....
Alternative BITAND
Prime product is one approach, but an
alternative approach is using the BITAND function which has similar
benefits, but used where you may want to test whether any value in
set A was is in set B.
Each number would require a single bit set, so
only base 2 numbers with integer exponents, e.g. 2**1, 2**2, 2""3,
etc, i.e. 2, 4, 8, 16, 32, 64, etc.
For example:
Set A consists of (4, 16) so bit
value = 4 + 16 = 20
Set B consists of (2, 4, 8) so bit
value = 2 + 4 + 8 = 14
To determine that a value in set A is in set B,
then check BITAND(20, 14) = 4, so 4 is the intersect between the two
sets. A non-zero value means that at least one value matches.
Alternatively, to check a subset is contained
within a superset.
For example:
Set A consists of (2, 4) so bit
value = 2 + 4 = 6
Set B consists of (2, 4, 8) so bit
value = 2 + 4 + 8 = 14
To determine that set A is in set B, then check
BITAND(20,6) = 6, which is the bit setting for the subset, so this
confirms it is
a subset.
Again, the versatility of SQL allows you to
generate the bit values:
SELECT POWER(2,LEVEL), LEVEL rank
FROM dual
CONNECT BY LEVEL <= 400
Unfortunately, the possible numbers are far
more limited than prime numbers and limited to 400 values before the
number overflows the Oracle numeric data type. In fact Oracle's
numeric data type can only hold 38 significant figures, so beyond 64
values it is not able to hold the number to the full precision and
the bit settings get lost.
A SQL approach to decoding the bit set would be
straight forward too:
SELECT a.*,
b.ref_desc
FROM my_main_table a,
my_ref_table b
WHERE BITAND(a.bit_set, b.bit_value) > 0
AND a.id = :p_id
Conclusion Both approaches
have very similar benefits and only really differ in their
limitations. For an Oracle based solution, there are far more prime
numbers available than bit based numbers, so prime numbers would be
favoured for solutions where you have more than 64 values to
represent. However, multiplying many prime numbers together soon
become very large and can exceed the 38 significant figures, so
favoured for smaller set sizes.
|
