SQL: View Representing Missing Ranges
Given a table of rows each representing a numerical range.
CREATE TABLE ranges (
start INTEGER,
end INTEGER
)
How could I create a view that represents the "holes" in the ranges? (Ignoring the bounds from -infinity to +infinity).
For example if the table had the data:
(1,3)
(4,5)
(8,10)
(16,20)
The result I'd like is:
(6,7)
(11,15)
I'm using python and sqlite. I'm currently thinking that a using a procedural approach in a sqlite function or python might be the most clear and performant approach.
I've seen an approach for finding missing dates that rely on a temp table for all the possible dates, but this method isn't feasible for integer ranges as they could very large.
sql sqlite
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
add a comment |
Given a table of rows each representing a numerical range.
CREATE TABLE ranges (
start INTEGER,
end INTEGER
)
How could I create a view that represents the "holes" in the ranges? (Ignoring the bounds from -infinity to +infinity).
For example if the table had the data:
(1,3)
(4,5)
(8,10)
(16,20)
The result I'd like is:
(6,7)
(11,15)
I'm using python and sqlite. I'm currently thinking that a using a procedural approach in a sqlite function or python might be the most clear and performant approach.
I've seen an approach for finding missing dates that rely on a temp table for all the possible dates, but this method isn't feasible for integer ranges as they could very large.
sql sqlite
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
1
This is a classic gaps and islands problem. Lots of interesting ways to go about this one, none of them are plainly obvious though :)
– JNevill
Nov 20 '18 at 21:31
@JNevill Nice! I knew it was a common problem but didn't know what it was called to search for it. Thanks for the link.
– Grandy H Nguyen
Nov 20 '18 at 22:48
add a comment |
Given a table of rows each representing a numerical range.
CREATE TABLE ranges (
start INTEGER,
end INTEGER
)
How could I create a view that represents the "holes" in the ranges? (Ignoring the bounds from -infinity to +infinity).
For example if the table had the data:
(1,3)
(4,5)
(8,10)
(16,20)
The result I'd like is:
(6,7)
(11,15)
I'm using python and sqlite. I'm currently thinking that a using a procedural approach in a sqlite function or python might be the most clear and performant approach.
I've seen an approach for finding missing dates that rely on a temp table for all the possible dates, but this method isn't feasible for integer ranges as they could very large.
sql sqlite
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
Given a table of rows each representing a numerical range.
CREATE TABLE ranges (
start INTEGER,
end INTEGER
)
How could I create a view that represents the "holes" in the ranges? (Ignoring the bounds from -infinity to +infinity).
For example if the table had the data:
(1,3)
(4,5)
(8,10)
(16,20)
The result I'd like is:
(6,7)
(11,15)
I'm using python and sqlite. I'm currently thinking that a using a procedural approach in a sqlite function or python might be the most clear and performant approach.
I've seen an approach for finding missing dates that rely on a temp table for all the possible dates, but this method isn't feasible for integer ranges as they could very large.
sql sqlite
sql sqlite
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
asked Nov 20 '18 at 21:17
Grandy H NguyenGrandy H Nguyen
375
375
1
This is a classic gaps and islands problem. Lots of interesting ways to go about this one, none of them are plainly obvious though :)
– JNevill
Nov 20 '18 at 21:31
@JNevill Nice! I knew it was a common problem but didn't know what it was called to search for it. Thanks for the link.
– Grandy H Nguyen
Nov 20 '18 at 22:48
add a comment |
1
This is a classic gaps and islands problem. Lots of interesting ways to go about this one, none of them are plainly obvious though :)
– JNevill
Nov 20 '18 at 21:31
@JNevill Nice! I knew it was a common problem but didn't know what it was called to search for it. Thanks for the link.
– Grandy H Nguyen
Nov 20 '18 at 22:48
1
1
This is a classic gaps and islands problem. Lots of interesting ways to go about this one, none of them are plainly obvious though :)
– JNevill
Nov 20 '18 at 21:31
This is a classic gaps and islands problem. Lots of interesting ways to go about this one, none of them are plainly obvious though :)
– JNevill
Nov 20 '18 at 21:31
@JNevill Nice! I knew it was a common problem but didn't know what it was called to search for it. Thanks for the link.
– Grandy H Nguyen
Nov 20 '18 at 22:48
@JNevill Nice! I knew it was a common problem but didn't know what it was called to search for it. Thanks for the link.
– Grandy H Nguyen
Nov 20 '18 at 22:48
add a comment |
1 Answer
1
active
oldest
votes
I like to do this as:
select (start + 1) as missing_start, (next_start - 1) as missing_ne
from (select t.*,
(select min(t2.start)
from t t2
where t2.start > t.start
) as next_start
from t
) t
where next_start > end + 1;
Note that this assumes no overlaps. If overlaps are possible the problem can be more difficult to solve.
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53401667%2fsql-view-representing-missing-ranges%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I like to do this as:
select (start + 1) as missing_start, (next_start - 1) as missing_ne
from (select t.*,
(select min(t2.start)
from t t2
where t2.start > t.start
) as next_start
from t
) t
where next_start > end + 1;
Note that this assumes no overlaps. If overlaps are possible the problem can be more difficult to solve.
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
add a comment |
I like to do this as:
select (start + 1) as missing_start, (next_start - 1) as missing_ne
from (select t.*,
(select min(t2.start)
from t t2
where t2.start > t.start
) as next_start
from t
) t
where next_start > end + 1;
Note that this assumes no overlaps. If overlaps are possible the problem can be more difficult to solve.
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
add a comment |
I like to do this as:
select (start + 1) as missing_start, (next_start - 1) as missing_ne
from (select t.*,
(select min(t2.start)
from t t2
where t2.start > t.start
) as next_start
from t
) t
where next_start > end + 1;
Note that this assumes no overlaps. If overlaps are possible the problem can be more difficult to solve.
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
I like to do this as:
select (start + 1) as missing_start, (next_start - 1) as missing_ne
from (select t.*,
(select min(t2.start)
from t t2
where t2.start > t.start
) as next_start
from t
) t
where next_start > end + 1;
Note that this assumes no overlaps. If overlaps are possible the problem can be more difficult to solve.
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
answered Nov 20 '18 at 21:29
Gordon LinoffGordon Linoff
779k35307410
779k35307410
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53401667%2fsql-view-representing-missing-ranges%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
This is a classic gaps and islands problem. Lots of interesting ways to go about this one, none of them are plainly obvious though :)
– JNevill
Nov 20 '18 at 21:31
@JNevill Nice! I knew it was a common problem but didn't know what it was called to search for it. Thanks for the link.
– Grandy H Nguyen
Nov 20 '18 at 22:48