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. 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 >> > > _______________________________________________ > 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
