Re: [sqlite] uuid generation in sqlite

[Duquette, William H (318K)]

On 1/24/11 8:36 AM, "Simon Slavin"  wrote:

> 
> On 24 Jan 2011, at 4:21pm, Duquette, William H (318K) wrote:
> 
>> A question on using randomblob(16) to generate UUIDs, as the SQLite docs
>> suggest: what assurance do you have that the UUID really is universally
>> unique?  It's a pseudo-random number, and you can replicate a stream of
>> pseudo-random numbers by setting the seed appropriately.  Is randomblob()
>> doing some kind of magic in its seeding of the random number stream?
> 
> Your assurance is only statistical.  Version 4 UUIDs have 30 4-bit higits and
> one 2-bit higit.  That gives you
> 
> (30 * 4) + 2 == 122
> 
> bits of randomness, which is about 5e36 different numbers.  You can work out
> yourself how fast people would have to choose random numbers to stand a chance
> of one duplication in ten years.

Provided that your starting seed is chosen in a
sufficiently random way, which evidently it is.
A bad choice of starting seed could bring the
whole thing crashing to the ground.


> 
> 
> Simon.
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

--
Will Duquette -- william.h.duque...@jpl.nasa.gov
Athena Development Lead -- Jet Propulsion Laboratory
"It's amazing what you can do with the right tools."


___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] uuid generation in sqlite

[Duquette, William H (318K)]

On 1/24/11 8:29 AM, "Richard Hipp" <d...@sqlite.org> wrote:

> On Mon, Jan 24, 2011 at 11:21 AM, Duquette, William H (318K) <
> william.h.duque...@jpl.nasa.gov> wrote:
> 
>> A question on using randomblob(16) to generate UUIDs, as the SQLite docs
>> suggest: what assurance do you have that the UUID really is universally
>> unique?  It's a pseudo-random number, and you can replicate a stream of
>> pseudo-random numbers by setting the seed appropriately.  Is randomblob()
>> doing some kind of magic in its seeding of the random number stream?
>> 
> 
> The SQLite PRNG is based on RC4 and is quite good.  On unix, it is seeded
> from /dev/random (where available - which is pretty much everywhere these
> days, except on windows).
> 
> So if you do the math, you'll see that the odds of getting duplicate
> randomblob(N) (for suitably large N, say 20) are far smaller than a giant
> meteor striking earth and ending all life here.  So while it is
> mathematically possible, we consider it sufficiently unlikely that it can be
> disregarded.

(Googling /dev/random.)

Aha.  randomblob() *IS* doing some kind of magic in its seeding of the
random number stream.  Very cool, I was not aware of /dev/random.


> 
> 
>> 
>> Will
>> 
>> 
>> On 1/24/11 3:49 AM, "Alexey Pechnikov" <pechni...@mobigroup.ru> wrote:
>> 
>> See
>> http://sqlite.mobigroup.ru/dir?name=ext/uuid
>> 
>> 2011/1/24 sqlite-us...@h-rd.org <sqlite-us...@h-rd.org>
>> 
>>> Hi,
>>> 
>>> I have put together a simple uuid generation method in sqlite:
>>> 
>>>  select '{' || hex( randomblob(4)) || '-' || hex( randomblob(2))
>>> || '-' || '4' || substr( hex( randomblob(2)), 2) || '-'
>>> || substr('AB89', 1 + (abs(random()) % 4) , 1)  ||
>>> substr(hex(randomblob(2)), 2) || '-' || hex(randomblob(6)) ||
>>> '}';
>>> 
>>> It's based on the description for v.4 uuid's in wikipedia
>>> https://secure.wikimedia.org/wikipedia/en/wiki/Uuid .
>>> 
>>> But I am thinking there may be a better (or another) method to do this
>>> in sqlite, without the need to use something external?
>>> 
>>> thanks
>>> 
>>> ___
>>> sqlite-users mailing list
>>> sqlite-users@sqlite.org
>>> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>>> 
>> 
>> 
>> 
>> --
>> Will Duquette -- william.h.duque...@jpl.nasa.gov
>> Athena Development Lead -- Jet Propulsion Laboratory
>> "It's amazing what you can do with the right tools."
>> 
>> ___
>> sqlite-users mailing list
>> sqlite-users@sqlite.org
>> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>> 
> 
> 

--
Will Duquette -- william.h.duque...@jpl.nasa.gov
Athena Development Lead -- Jet Propulsion Laboratory
"It's amazing what you can do with the right tools."


___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] uuid generation in sqlite

[Simon Slavin]

On 24 Jan 2011, at 4:21pm, Duquette, William H (318K) wrote:

> A question on using randomblob(16) to generate UUIDs, as the SQLite docs 
> suggest: what assurance do you have that the UUID really is universally 
> unique?  It's a pseudo-random number, and you can replicate a stream of 
> pseudo-random numbers by setting the seed appropriately.  Is randomblob() 
> doing some kind of magic in its seeding of the random number stream?

Your assurance is only statistical.  Version 4 UUIDs have 30 4-bit higits and 
one 2-bit higit.  That gives you

(30 * 4) + 2 == 122

bits of randomness, which is about 5e36 different numbers.  You can work out 
yourself how fast people would have to choose random numbers to stand a chance 
of one duplication in ten years.

Simon.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] uuid generation in sqlite

[Richard Hipp]

On Mon, Jan 24, 2011 at 11:21 AM, Duquette, William H (318K) <
william.h.duque...@jpl.nasa.gov> wrote:

> A question on using randomblob(16) to generate UUIDs, as the SQLite docs
> suggest: what assurance do you have that the UUID really is universally
> unique?  It's a pseudo-random number, and you can replicate a stream of
> pseudo-random numbers by setting the seed appropriately.  Is randomblob()
> doing some kind of magic in its seeding of the random number stream?
>

The SQLite PRNG is based on RC4 and is quite good.  On unix, it is seeded
from /dev/random (where available - which is pretty much everywhere these
days, except on windows).

So if you do the math, you'll see that the odds of getting duplicate
randomblob(N) (for suitably large N, say 20) are far smaller than a giant
meteor striking earth and ending all life here.  So while it is
mathematically possible, we consider it sufficiently unlikely that it can be
disregarded.



>
> Will
>
>
> On 1/24/11 3:49 AM, "Alexey Pechnikov" <pechni...@mobigroup.ru> wrote:
>
> See
> http://sqlite.mobigroup.ru/dir?name=ext/uuid
>
> 2011/1/24 sqlite-us...@h-rd.org <sqlite-us...@h-rd.org>
>
> > Hi,
> >
> > I have put together a simple uuid generation method in sqlite:
> >
> >  select '{' || hex( randomblob(4)) || '-' || hex( randomblob(2))
> > || '-' || '4' || substr( hex( randomblob(2)), 2) || '-'
> > || substr('AB89', 1 + (abs(random()) % 4) , 1)  ||
> > substr(hex(randomblob(2)), 2) || '-' || hex(randomblob(6)) ||
> > '}';
> >
> > It's based on the description for v.4 uuid's in wikipedia
> > https://secure.wikimedia.org/wikipedia/en/wiki/Uuid .
> >
> > But I am thinking there may be a better (or another) method to do this
> > in sqlite, without the need to use something external?
> >
> > thanks
> >
> > ___
> > sqlite-users mailing list
> > sqlite-users@sqlite.org
> > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
> >
>
>
>
> --
> Will Duquette -- william.h.duque...@jpl.nasa.gov
> Athena Development Lead -- Jet Propulsion Laboratory
> "It's amazing what you can do with the right tools."
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] uuid generation in sqlite

[Duquette, William H (318K)]

A question on using randomblob(16) to generate UUIDs, as the SQLite docs 
suggest: what assurance do you have that the UUID really is universally unique? 
 It's a pseudo-random number, and you can replicate a stream of pseudo-random 
numbers by setting the seed appropriately.  Is randomblob() doing some kind of 
magic in its seeding of the random number stream?

Will


On 1/24/11 3:49 AM, "Alexey Pechnikov" <pechni...@mobigroup.ru> wrote:

See
http://sqlite.mobigroup.ru/dir?name=ext/uuid

2011/1/24 sqlite-us...@h-rd.org <sqlite-us...@h-rd.org>

> Hi,
>
> I have put together a simple uuid generation method in sqlite:
>
>  select '{' || hex( randomblob(4)) || '-' || hex( randomblob(2))
> || '-' || '4' || substr( hex( randomblob(2)), 2) || '-'
> || substr('AB89', 1 + (abs(random()) % 4) , 1)  ||
> substr(hex(randomblob(2)), 2) || '-' || hex(randomblob(6)) ||
> '}';
>
> It's based on the description for v.4 uuid's in wikipedia
> https://secure.wikimedia.org/wikipedia/en/wiki/Uuid .
>
> But I am thinking there may be a better (or another) method to do this
> in sqlite, without the need to use something external?
>
> thanks
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



--
Will Duquette -- william.h.duque...@jpl.nasa.gov
Athena Development Lead -- Jet Propulsion Laboratory
"It's amazing what you can do with the right tools."

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] uuid generation in sqlite

[Alexey Pechnikov]

See
http://sqlite.mobigroup.ru/dir?name=ext/uuid

2011/1/24 sqlite-us...@h-rd.org <sqlite-us...@h-rd.org>

> Hi,
>
> I have put together a simple uuid generation method in sqlite:
>
>  select '{' || hex( randomblob(4)) || '-' || hex( randomblob(2))
> || '-' || '4' || substr( hex( randomblob(2)), 2) || '-'
> || substr('AB89', 1 + (abs(random()) % 4) , 1)  ||
> substr(hex(randomblob(2)), 2) || '-' || hex(randomblob(6)) ||
> '}';
>
> It's based on the description for v.4 uuid's in wikipedia
> https://secure.wikimedia.org/wikipedia/en/wiki/Uuid .
>
> But I am thinking there may be a better (or another) method to do this
> in sqlite, without the need to use something external?
>
> thanks
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
Best regards, Alexey Pechnikov.
http://pechnikov.tel/
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] uuid generation in sqlite

[Andy Gibbs]

On Monday, January 24, 2011 11:11 AM, Artur Reilin wrote:

>> Hi,
>>
>> I have put together a simple uuid generation method in sqlite:
>>
>>   select '{' || hex( randomblob(4)) || '-' || hex( randomblob(2))
>>  || '-' || '4' || substr( hex( randomblob(2)), 2) || '-'
>>  || substr('AB89', 1 + (abs(random()) % 4) , 1)  ||
>>  substr(hex(randomblob(2)), 2) || '-' || hex(randomblob(6)) 
>> ||
>> '}';
>>
>> It's based on the description for v.4 uuid's in wikipedia
>> https://secure.wikimedia.org/wikipedia/en/wiki/Uuid .
>>
>> But I am thinking there may be a better (or another) method to do this
>> in sqlite, without the need to use something external?
>>
>> thanks
>
> http://sqlite.org/lang_corefunc.html
>
> randomblob(N)
> The randomblob(N) function return an N-byte blob containing pseudo-random
> bytes. If N is less than 1 then a 1-byte random blob is returned.
>
> Hint: applications can generate globally unique identifiers using this
> function together with hex() and/or lower() like this:
> hex(randomblob(16))
>
> lower(hex(randomblob(16)))
>

And since this doesn't give the UUID in the form you wish, and failing that 
any other suitable way to do it presents itself to you, you could do worse 
than create a custom function (see 
http://www.sqlite.org/c3ref/create_function.html and 
http://www.sqlite.org/c_interface.html#cfunc) which takes the randomblob 
data and formats it according to the UUID v4 structure.

If you do take this route, then you can create the randomblob data within 
your custom function (hint: have a look at how the randomblob function is 
implemented in the sqlite source code), rather than passing it in as a 
parameter -- the advantage being that you can ensure that you create the 
correct size blob in one go and then split it up appropriately into the 
structure required.

Cheers
Andy



___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] uuid generation in sqlite

[Artur Reilin]

> Hi,
>
> I have put together a simple uuid generation method in sqlite:
>
>   select '{' || hex( randomblob(4)) || '-' || hex( randomblob(2))
>  || '-' || '4' || substr( hex( randomblob(2)), 2) || '-'
>  || substr('AB89', 1 + (abs(random()) % 4) , 1)  ||
>  substr(hex(randomblob(2)), 2) || '-' || hex(randomblob(6)) ||
> '}';
>
> It's based on the description for v.4 uuid's in wikipedia
> https://secure.wikimedia.org/wikipedia/en/wiki/Uuid .
>
> But I am thinking there may be a better (or another) method to do this
> in sqlite, without the need to use something external?
>
> thanks

http://sqlite.org/lang_corefunc.html

randomblob(N)
The randomblob(N) function return an N-byte blob containing pseudo-random
bytes. If N is less than 1 then a 1-byte random blob is returned.

Hint: applications can generate globally unique identifiers using this
function together with hex() and/or lower() like this:
hex(randomblob(16))

lower(hex(randomblob(16)))


Artur Reilin
sqlite.yuedream.de
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] uuid generation in sqlite

[sqlite-us...@h-rd.org]

Hi,

I have put together a simple uuid generation method in sqlite:

  select '{' || hex( randomblob(4)) || '-' || hex( randomblob(2))
 || '-' || '4' || substr( hex( randomblob(2)), 2) || '-'
 || substr('AB89', 1 + (abs(random()) % 4) , 1)  ||
 substr(hex(randomblob(2)), 2) || '-' || hex(randomblob(6)) || '}';

It's based on the description for v.4 uuid's in wikipedia
https://secure.wikimedia.org/wikipedia/en/wiki/Uuid .

But I am thinking there may be a better (or another) method to do this  
in sqlite, without the need to use something external?

thanks

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users