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