Did you try something like(pseudo code): select * from A inner join B on A.name = B.name AND ( B.left between(A.left,A.right) OR B.right between(A.left,A.right) )
On 8/13/2010 8:07 AM, Peng Yu wrote: > Hi, > > Suppose that I have a table "A", each row represents a interval. For > example, the first row represents an interval [1,10) with a name "a". > The first and second rows are considered overlapping because the > interval [1,10) and interval [5,15) intersect and both rows have the > same name "a". > > name left right tag > ------------------------------------- > a 1 10 tag1 > a 5 15 tag2 > a 21 30 tag3 > b 3 12 tag4 > b 15 25 tag5 > b 19 30 tag6 > > I want to "inner join" the above table and the following table "B" > based on the named interval overlapping. > > name left right attr > ------------------------------------- > a 3 7 attr1 > a 8 12 attr2 > a 16 18 attr3 > a 25 35 attr4 > b 31 32 attr5 > > The result is the following. In each row, the named interval from A > overlaps the named interval from B. I don't see there is an easy way > to do this in sqlite3. I could use an external program (such as python > sqlite package) to enumerate all the named interval from table A and > search for overlapping named intervals in table B, but this operation > has a complexity of M log (N), where M is the length of table A and N > is the length of table B. If some sort of "inner join" could be used, > the complexity should be reduced to log(M+N). I'm wondering if there > something that can help do this kind of named interval inner join > easily. > > A.name A.left A.right A.tag B.name B.left B.right B.attr > ------------------------------------------------------------------------ > a 1 10 tag1 a 3 7 attr1 > a 1 10 tag1 a 8 12 attr2 > a 5 15 tag2 a 3 7 attr1 > a 5 15 tag2 a 8 12 attr2 > a 21 30 tag3 a 16 18 attr3 > > _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users