On 13 August 2010 16:07, 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
Last line does not overlap. Assuming that is an oversight, then select * from A inner join B on A.name=B.name and A.left<=B.right and A.right >=B.left; seems to do what you want. > > -- > Regards, > Peng Regards, Simon _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
