pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Vasilis Samoladas <vsam@cs.utexas.edu>
To: pgsql-sql@postgresql.org
Subject: Re: Using Random Sequence as Key
Date: 24 Apr 2001 08:29:51 -0500
Message-ID: <9c3v4f$kus$1@crom.cs.utexas.edu> (raw)
References: <9bdjag$faj$1@news.tht.net>

Hello Bernardo,

there is a somewhat mathematical solution to your problem.
You can use a unique key, say 0<= k < MAX for each record,
and a second key which is computed from the first, say
f(k), which will give you a unique permutation of the
numbers 0,...,MAX-1. It will not be random, but it will
be hard for someone to figure out the original unique
key k, without knowning your method.

Here is one way to compute f(k): (math follows, beware!)

The Fibonacci numbers are a sequence defined as follows:
F(0) = 0, F(1) = 1,  F(n+2) = F(n+1)+F(n) (for n>=0).

Now, for every fixed number N>=2, you can define
a permutation f(k) of the numbers 0,...,F(N)-1
as follows:
f(k) =  (k*F(N-1)) mod F(N)

For example, if N=6, we have F(6)=8 and F(5)=5, so
for 0<= k <8,  f(k) = 5*k mod 8 is a permutation.
In particular,
k    =  0 1 2 3 4 5 6 7
f(k) =  0 5 2 7 4 1 6 3

So, since you need approximately 90000 numbers (10000 to 99999),
you can use N=25, which will give you F(25)=75025 and F(24)=46368.
Thus, you can have 75025 (slightly fewer than 90000) unique values,
by translating k into
f(k) = 46368*k mod 75025

Unless your users know number theory, this should work for you.

Vasilis


Bernardo de Barros Franco <electric_csf@hotmail.com> wrote:
: Hello, I was wondering if noone can help me maybe someone could at least
: give me some directions where to look for info or where to ask:
: I wanted to index a table by a random key. Exemplifying, when a insert is
: made, the id value is automatically filled with a random number between
: 10000 and 99999. I'm pretty new in pgsql so I could use a howto or
: something, and I repeat, if you don't know how, directions to where I can
: find info on that or where I can ask someone that might know would be
: enough.

: Thank you






view thread (12+ messages)  latest in thread

Message-ID: <9c3v4f$kus$1@crom.cs.utexas.edu>
Permalink:  ../9c3v4f$kus$1@crom.cs.utexas.edu/
Also on:    postgresql.org/message-id/9c3v4f$kus$1@crom.cs.utexas.edu

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-sql@postgresql.org
  Cc: vsam@cs.utexas.edu
  Subject: Re: Using Random Sequence as Key
  In-Reply-To: <9c3v4f$kus$1@crom.cs.utexas.edu>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox