A few days ago I saw a question that, among other things, implied a problem similar to the one I am going to pose, I wanted to do it in a more general way, because I understand that the well-posed solution could serve as a reference to similar problems. Perhaps for some of you the answer is trivial or obvious, but in my case only when I chewed it enough I found (at least I think so) that it was simpler than I thought. I propose it in Sql but it could be more about algorithms, the issue is that it seemed more practical to be able to test the solutions.
Suppose the following example:
CREATE TABLE A (
NRO_DESDE INT,
NRO_HASTA INT
)
CREATE TABLE B (
NRO_DESDE INT,
NRO_HASTA INT
)
INSERT INTO A (NRO_DESDE, NRO_HASTA)
VALUES (5, 8)
INSERT INTO B (NRO_DESDE, NRO_HASTA)
VALUES (1, 2), (4, 5), (5, 8), (6, 7), (7, 9), (4, 10), (9, 11)
SELECT NRO_DESDE, NRO_HASTA FROM A;
SELECT NRO_DESDE, NRO_HASTA FROM B;
The table A
has a single value:
NRO_DESDE NRO_HASTA
========= =========
5 8
The boardB
NRO_DESDE NRO_HASTA
========= =========
1 2
4 5
5 8
6 7
7 9
4 10
9 11
The tables A
and B
represent sets of intervals, but for which we do not have all the values but rather we know the first and last element of each set, the idea is to compare the only set in A
with all of B
and determine if they share any element. As an example, the record B
(4, 5)
shares the 5
with A
, the (1, 2)
does not share any element, the (7, 9)
share the 7, 8
. The result would then be the records of B
that have elements shared with those of A
, it is not important to know what they are, just to know that there are, we can also assume that the number of elements in each set is relatively manageable. Don't worry about missing primary keys, it's just a conceptual example.
Note: The code is built in SQL Server but could be resolved in any "flavor" of SQL.
gbianchi's answer effectively answers my question, looking at the 4 different cases in which intervals can be connected. Let's see:
Cases 1 and 2 are classic intersections of sets, being intervals, one can be located before the other and have contact at their ends. In the example it would be, for example, the interval
4-5
or7-9
that are connected to the intervalA
5-8
by one of its ends.The other two possible cases are the inclusion cases, where one set is included in the other. For example the interval
B (6-7)
is included in theA (5-8)
, or vice versa, theA
is included in theB (4-10)
. To contemplate the 4 cases and since the only data we have about the sets are their limits, the query must be resolved as mentioned by gbianchi.Another way of looking at this problem is to think that cases do not meet these conditions. If we go to the theory, the only case is that of disjoint sets , that is:
Sets that are not connected, being intervals, the cases are two, when
B
it is less thanA
or vice versa. If we now study how to compare the limits we will see that it is much simpler, it would be:and the interesting thing about this is that the negation of these cases is one of the previous cases, so we could simplify the original query to the following:
Or better yet, with explicit Joins:
Or as Fede H says, applying a bit of algebra to remove the
NOT
:Although this is a conceptual example, in reality we can find many cases similar to this, for example, it is common to work with dates in certain problems in this way:
I don't know if it's the most performant query on the planet... but you have a set problem.
With a query like this you are looking for all the variants of the two sets that intersect.
Notice that we first test A against the intervals of B. And then we do the same for B. The latter, because if the interval of A completely contains the interval of B, then it would not come up in the first query.
For me the clearest solution is similar to Patricio's but with the conditions inverted. Just recently I had to use it with dates and perhaps in that case it will be better understood. I will try to paraphrase it to see if it is understood.
The ranges I'm looking for are those that end after the start of the target range and start before the end of the target range.