I don't think this will work. xor(6,1) = 7 and xor(4,3) = 7, so you
would fail to insert proper pairs. Or am I missing something? (At least
I assume that the integers are not limited to just 1 2 or 3 as in the
examples.
David
On 02/09/2011 05:58 PM, Samuel Adam wrote:
> On Wed, 09 Feb 2011 13:12:32 -0500, Black, Michael (IS)
> <michael.bla...@ngc.com> wrote:
>
>
>> I have a need to create a unique bi-directional relationship.
>>
>> You can think of it as pairings of people who eat dinner together.
>>
> Two questions come to mind:
>
> (a) Do you trust app-level code to maintain data integrity, or do you
> need SQLite to do this?
>
> (b) How much relational rigor do you need? Will the values be used for
> some kind of relational algebra, or is SQLite simply serving as an ACID
> reliability layer?
>
> Since you’ve been considering the bit-math tricks suggested by Mr.
> Wilcoxson, the answers to these questions may let you consider some XOR
> cleverness. Unfortunately, I halfway wrote this up before I realized that
> SQLite lacks a ^ operator[1]; so you will need a trivial SQL user function
> and/or app-land code. Still, with the following, you can store any pairs
> of 63-bit integers>= 0. In pure SQL:
>
> CREATE TABLE "" ("k" INTEGER PRIMARY KEY, "x" INTEGER);
> -- WRONG: INSERT INTO "" ("k", "x") VALUES (:x ^ :y, :x);
> INSERT INTO "" ("k", "x") VALUES (xor(:x, :y), :x);
> -- Faster on the app level; you understand.
> SELECT "x", xor("k", "x") AS "y" FROM "";
>
> (Add NOT NULL or CHECK(typeof("x") IS 'integer') and salt to taste. N.b.,
> I *think* the above binding scenario will work but have not tested it.)
>
> [1] 2009·12·15 thread with reference to ^ patch by Will Clark:
> Message-ID:
> <off7402127.00e0cd73-onc125768d.0045dfc4-c125768d.0049d...@gfs-hofheim.de>
> http://www.mail-archive.com/sqlite-users@sqlite.org/msg49112.html
>
> Key points:
>
> * Pair uniqueness is enforced for free. At least, I think it’s really
> for free because SQLite always requires a unique rowid. Somebody please
> correct me if there is any penalty for user-selected rowids, which would
> make the performance impact nonzero.
>
> * Order of (x, y) versus (y, x) pairings is preserved. Sorts on y will
> be a pain, though.
>
> * No extra indices are required.
>
> * I don’t see a reasonable way to stop arbitrary data from being stuffed
> in from within SQLite, even with a user function; for although :y is being
> bound on INSERT, a CHECK constraint has no way to touch it. But see below
> for a modified table with a different set of tradeoffs.
>
> * Since two small integers XORed will be another small integer, you do
> not suffer the loss of variable-length integer storage as spoken of by
> Messrs. Vlasov and Tandetnik.
>
> * XOR is *fast*. And the number of integers is kept to a bare minimum
> (for keeping up to 63 bits for each), cutting cache pressure at all
> levels—from SQLite’s page-cache to the processor caches. I am no expert
> in optimization, but the foregoing practically begs to be benchmarked.
>
> * If for some reason you can’t use xor("k", "x") for all your SQL needs
> (foreign keys come to mind), add another explicit "y" column. You then
> lose some of the foregoing advantages. But then, a trivial (and probably
> quite fast) pure-SQL constraint could then be used to enforce some
> integrity:
>
> CREATE TABLE "" (
> "k" INTEGER PRIMARY KEY, "x" INTEGER, "y" INTEGER,
> CHECK ("k" IS xor("x", "y")) -- NOT NULL for free!
> );
> i
> * If you try to use negative integers, your database will trigger a HCF
> instruction. At the cost of some more performance, CHECK("x">= 0 AND
> xor("k", "x")>= 0) will *partially* solve that. I say “partially”
> because per the foregoing, SQLite cannot guarantee that "y" = "k"^"x"
> unless you use the modified table, anyway.
>
> Bear in mind, this suggestion stems from a personal bias toward clever XOR
> tricks; at that, I once wrote a set of endian-swab functions with no
> (explicit) temporary variables, purely using XOR-swap and shifts. I found
> it the most pleasant way to satisfy aliasing rules; yet I am to this day
> uncertain whether the result qualifies as abstract art.
>
> P.S.: Consider the foregoing a real-life use case in support of adding a
> bitwise ^ operator to SQLite.
>
> Very truly,
>
> Samuel Adam ◊<http://certifound.com/>
> 763 Montgomery Road ◊ Hillsborough, NJ 08844-1304 ◊ United States
> Legal advice from a non-lawyer: “If you are sued, don’t do what the
> Supreme Court of New Jersey, its agents, and its officers did.”
> http://www.youtube.com/watch?v=iT2hEwBfU1g
>
>
>
>> create table t(i int, j int);
>>
>> insert into t(1,2);
>>
>> insert into t(2,1);<< should give an error because the pairing of 1-2
>> already exists.
>>
>> insert into t(3,2);<< OK
>>
>> insert into t(3,1);<< OK
>>
>> insert into t(1,3);<< should be error
>>
>>
>>
>> You can't guarantee that one column is less than the other so there's no
>> win there.
>>
>>
>>
>> Speed is of the utmost concern here so fast is really important (how
>> many ways can I say that???).
>>
>>
>>
>> Is there anything clever here that can be done with indexes or such?
>>
>>
>>
>>
>>
>> Michael D. Black
>>
>> Senior Scientist
>>
>> NG Information Systems
>>
>> Advanced Analytics Directorate
>>
>>
> _______________________________________________
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
