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