I don't understand where do you see a problem but it looks like this join will do what you want:
select * from A, B where A.name = B.name and A.left < B.right and A.right > B.left > 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). How did you come to this conclusion? Any inner join will execute with complexity either M log(N) or N log(M) anyway. The only benefit is that SQLite can decide which way to join depending on relative size of tables A and B. And constant in operation complexity is a bit smaller with C code that in python code... Pavel On Fri, Aug 13, 2010 at 11:07 AM, Peng Yu <pengyu...@gmail.com> 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 > > -- > Regards, > Peng > _______________________________________________ > 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