-- The SQL queries runs on sqlite3 with version >= 3.8.3
-- (the with clause was not supported before 3.8.3).


-- This file implements 8-bound addition.

-- create the bit position total order table  T
create table T(h integer, l integer);

-- 8-bound, bit positions are 0,1,2,3,4,5,6,7
insert into T(h,l) values 
(7,6),(7,5),(7,4),(7,3),(7,2),(7,1),(7,0),
(6,5),(6,4),(6,3),(6,2),(6,1),(6,0),
(5,4),(5,3),(5,2),(5,1),(5,0),
(4,3),(4,2),(4,1),(4,0),
(3,2),(3,1),(3,0),
(2,1),(2,0),
(1,0);

-- A: first addition source number
-- B: second addition source number
create table A(b integer);
create table B(b integer);
-- A is 101101
-- B is 11100111
insert into A(b) values (0),(2),(3),(4),(6);  
insert into B(b) values (0),(1),(2),(5),(6),(7);
--result: 1000100, i.e. { 6,2 }


---------------------sub queries -------------------------------

-- S1(h,l):- T(h,z) T(z,l) -A(z) -B(z)
--there exists a bit position z between h and l, such that A(z)=0 and
--B(z) =0 

-- select distinct T1.h h,T2.l l from T T1, T T2, A,B where
-- T1.l = T2.h and T1.l not in A and T1.l not in B;

-- C(b) :- T(b,l) A(l) B(l) -S1(b,l)
-- For b, there exists an lower bit position l, where A(l)=1 and
-- B(l)=1 and does not satisfy S1(b,l); i.e. the b position will get a
-- carry bit

-- select T.h b from T,A,B where T.l = A.b and T.l = B.b and not
-- exists (select * from (select distinct T1.h h,T2.l l from T T1, T
--     T2, A,B where T1.l = T2.h and T1.l not in A and T1.l not in B)
--   as S1 where S1.h=T.h and S1.l=T.l);

-------------------- full query ---------------------------------

-- R(x) :- A(x) B(x) C(x) | A(x) -B(x) -C(x) | -A(x) B(x) -C(x) | -A(x) -B(x) C(x)
-- The with clause is supporeted since sqlite3 version >=3.8.3

with C(b) as (select T.h b 
              from T,A,B 
              where T.l = A.b and T.l = B.b 
                and not exists (select * 
                                from (select distinct T1.h h,T2.l l 
                                      from T T1, T T2, A,B 
                                      where T1.l = T2.h and T1.l not in A and T1.l not in B) as S1
                                where S1.h=T.h and S1.l=T.l)
             ) 
select A.b x from A,B,C where A.b=B.b and A.b=C.b
union
select A.b x from A,B,C where A.b not in B and A.b not in C
union
select B.b x from A,B,C where B.b not in A and B.b not in C
union
select C.b x from A,B,C where C.b not in A and C.b not in B;


