On Wed, 09 Feb 2011 18:51:45 -0500, Samuel Adam <a...@certifound.com>
wrote:
> On Wed, 09 Feb 2011 18:39:14 -0500, David Bicking <dbic...@yahoo.com>
> wrote:
>
>> 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.
>
> You are right, as xoring on my fingers would have verified. In polite
> terms, evidently I just demonstrated publicly math as not my forté ||
> today as not my day. Apologies for the noise.
At risk of worsening my today’s foot-in-mouth syndrome, I believe that the
following design would keep *some* of the advantages I outlined at cost of
the following:
(a) It would only work for 31-bit integers (or 32-bit integers with
additional tricks to store two 32-bit unsigneds in a 64-bit signed).
(b) Increased computational cost.
However, it adds one advantage (in addition to being correct!):
(c) It would collapse the full informational content of "x" and "y"
into
the same column "xk" (viz., the all-important INTEGER PRIMARY KEY). And
still, no additional indices are required.
In pseudo-C:
int32_t x, y;
int64_t xk; /* k lives in the low bits of xk */
if (x < 0 || y < 0) ; /* Return an error. */
xk = (int64_t)x<<32 | x^y;
/* Weird integer concatenation; yes, precedence is right. */
If you don’t mind living dangerously, use union or pointer tricks to
coerce uint32_t x, y into an sqlite3_int64.
Upon the foregoing, only one column ("xk" INTEGER PRIMARY KEY) is required
to actually store the data. With the foregoing pseudo-C placed in an SQL
user function, however, this is also possible:
CREATE TABLE "" (
"xk" INTEGER PRIMARY KEY, "x" INTEGER, "y" INTEGER,
CHECK ("xk" IS compose_xk("x", "y"))
);
I think Shannon bit me before, but he’s on my side now.
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
> 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
>
>
>> 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
