On Wed, 09 Feb 2011 13:12:32 -0500, Black, Michael (IS)
<[email protected]> 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/[email protected]/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
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
