To: "pgsql-sql@lists.postgresql.org" <pgsql-sql@lists.postgresql.org>
From: Adam Jensen <hanzer@riseup.net>
Openpgp: preference=signencrypt
Autocrypt: addr=hanzer@riseup.net; keydata=
 xsFNBFITbtMBEADj0R/kXShGc0soC29c5WkR56N/nsQ/VgXExduZ3Agyu/5AintZDbcJ9pLO
 PsaYKJfchIa9Fv1lcLhaaGPyPBYTklU8axSDpDa2Y6Kc2Ezyjq6dDEdk3La2eWER8BDQHNP+
 MYZ8Qin+tllQwX/uufC4UBvZxxIOhp05gAryvFPcXoq1MXrj5PdeNvFKtAVRNSwPDg1sIm6A
 ijZRcB6NfeMb/Yc543Yf450ewZTuebnJTQu55ywK5mpZExWiAZEr6z1cnbTfqG3Do82CWhak
 w16F5r0Vx25ckz0St8N5igdZOi57hS+dQLpxkVW2a6KqTQ+vbIjwEp4Kxj88PjI6CgZ9y6el
 mY4vmkDKXbGSDUjswUDQYuO2IXPT9GcE7H2grh2E5tvxH2DpL3lw5YFg5FPw6Ku8m1xYeh41
 xZ+tLGoYs9Qg/PA2a7pDeWn8p227jJ9Q9MxAcA2KfXRA6qfMTc/gvYF3bsVYorV8XwNcoQWv
 WoYFz7gAhXvmkbad40c8fUr8cKP0aFnqlIvC0QBkhhRMocG/1PcahwIMepv+F2nNBOFeFmxr
 YvcYXzNWnG5S/QNJvc5jAvgNZMfYz7R7KJGLinjq7ED/5Ly/EaDFkDSwNAAxKkPabxfryhb3
 6w7b509xa8EXRAi7reG04jFI+54PKMT5/FNrw9dhGnlJGU0KBQARAQABzR9BZGFtIEplbnNl
 biA8aGFuemVyQHJpc2V1cC5uZXQ+wsF3BBMBCgAhBQJSE27TAhsDBQsJCAcDBRUKCQgLBRYC
 AwEAAh4BAheAAAoJEGUApdpiqr3gNiAQAJ+lnXCQZZSsOYTxwXBlrVN5pepI8V+fd4ZZ3gn/
 wt7dpP2Ak4FQNDch8XvahhS/guKvosZjSayqynPF2eXcR8sXNV2uMwKpqas139PM/956FqYv
 XdN/GOGVHxR9KanafzJwMJj5f6+BrhPp1GVRwQYyUhdlmnZJhHMt+lRLu1h27m7E/IAngYia
 RJ6a3m6XJQFkRMz8mjSNV0AZBlNNvpycEJoS8RbMoynR5LIjdWlJye25ufox1pjY/XVhw3hF
 2HxRKAakO+q6Zc6v0MVmjDiIq+QxCqGdCoj0SACEmgOmI+SZl6rmenrSX0M/cktpNX9wyBYN
 CtxIdA6Zex+mOMmgo9g7T2n4xcqX83aIQKkuBJFfUj5yPBEWkjFvuYvtXbHogY3maFNYe+pm
 ZE6EZpBRZ8PCN17NLgxyh58yeJEx3oS1LDfqRz5SrFxfdN7bgExN3HKJJg7Jt32Oaml/8jSI
 BuxcEYimaP6MBkhrBHmd+TW3TUVGyQosqHGllQttXD92dm7wcaZnH0MNmroGG3+Czus2EgUS
 igFP4BwgNB8TaD17S6NQN83FVahAgjyhtadLtTzya/YSPrrvSHsKc88gasqNzvpsa+ggQZFX
 KALI/dozac61D6+UuTcUOvZCo5V4mIgeBMcw7PY6Ccycz9fHKghiPTuFdO1QI4KtujcXzsFN
 BFITbtMBEACnKEB3eI8FFIU4c9oDEkSPrZCwOOIjkaz9HfPOcLslFLVijqhPt4CCk5HM05KR
 yIYrYTyWytZfX+j2vW4TqJzntPBC+7oNjAIZ1l4UH6q8UxDya9+OLCx6awJNLo+5xmZ3pU7K
 vaTkvMguQfO7VWUK+f5nKYr/+lnZkxH0wuuLWomceEOk8Kt6g9+pQOC6w8FX4tYrtSFoSLHB
 bU7U1U4eJ3Hhp2b6PzHtJPtGORZ9i7CRRlZHONDNMw0EPcBkb5N0zgdLveVEUTfZfulR0TRN
 2dBktBXArfoO3qZN4aKseLXU8XRQUG5xJNwf8vY+8fzKvgeh3BUgz2USYofRcTKEmkurvoA+
 rKBMmGnW9s9pn8jlDLIB+V651YiJ+ip5HZL17pVI0zNDjKvqLw9EWGDaFh6WnIT+GTGKQBtu
 yzEZCKrPUkDxuqhZBRDw2ODdP37ccF9TippHW1e55oK3Wjgwon8DH7cJixzTXKIegTio459Y
 YE763IEXHjozhjZVYknaoysz4NRYJdYZKLjxsb4Xjc2BWLciumnEltaWGRl7MUblPH4jkMpD
 4dOmYNpuhtUau8/UPpeHn8uaIHGlPGq4G+z5Wlaf6WVwLFOZRG8LuFMqhQ/8AeYjqDy3dB10
 ruMDNpkiou/qDIIE2dHgvySMYntgPuEmCALHZMhIDvYCUwARAQABwsFfBBgBCgAJBQJSE27T
 AhsMAAoJEGUApdpiqr3gSxgP/jQJ34l85dNgrLqKOEOS7dfZzQRLjk0KkCIeCY/LmRDzyxD2
 Gre5jtxFBuGNvcdaG5puC8rVpM0KW+MATqf8OjUhks71nz9aT+aKIga7oA/USl6QtErsdx7s
 g0BSz3kId481W3SUsvk7sXUcdRdri5SXZvfXhC9cL7UUKiPaL6zet/SMtIv0lSNGWHo44h3i
 IJVggPcwTW0p5eQGn8+dLTtJFBNfdpHv+pwgtBCBtMnYckfxkq+Mfk1vDhjVYQjtc03N6LbU
 zSALmELQeKdmjqhDZGniq651CveqMSaS6UKKbf2iIAMvBiyjl+jWGgUy9EMcNUJIxkAM8EWV
 Lv8MNu72oJhaAJpjSybiCeK2prK4ZTJF0h7ll81ftGVr1Cp/jRkw1Pof2bVQmlILHXkJLZJs
 unFsEcHpwnw52gZXc/zYjMGfyZy/ihP4Pyp+E7qlUKuLpkpEB43Ix5u8jmcOkMKhBnNo9OO1
 p6Uwbl5GBIL/LXDKynYB98oXaxCzYkaxOrUWIu1ySJqRNnzAFMSwMqrR6fVumascjtAlBTMM
 sC/nN9VGG1VY0onGGJ80Vt+Fbhmj+zDpn0J3DfL2xD91+RxJaLCn8Iy/C4TikwsipXjnSmzA
 d6y+BJO5+lPxTTlg0UomOGv4ChmcVUEfXxk2GsvHZzsTA4qhLaZDuy9vR4eZ
Subject: interval origami
Message-ID: <a4b97a40-6c5a-580f-361d-03de6572ce27@riseup.net>
Date: Fri, 30 Nov 2018 12:52:31 -0500
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

Hi,

I am working on a hobby project that might eventually make its way into
the public domain. The goal is to create a Media Annotation, Analysis
and Playback Synthesis System (I call the project MAAPSS). Conceptually,
it is somewhat similar to vcode[1,2] but more "hackable" with broader
general applications.

[1]: http://social.cs.uiuc.edu/projects/vcode.html
[2]: https://youtu.be/Sv_OZ174wpg

In the configuration that I am currently exploring, the database will
contain many entries with intervals that could overlap in every possible
way. The entries could be labeled in many ways other than "interesting"
and "fail". This little example is a simplified attempt to isolate what
I see as the core problem, which is probably mostly based in my current
lack of understanding of SQL.

CREATE TABLE Example (start REAL, stop REAL, tag TEXT);
INSERT INTO Example VALUES
(10, 30, 'interesting'),
(12, 32, 'interesting'),
(15, 20, 'fail'),
(16, 39, 'interesting'),
(17, 21, 'fail'),
(50, 80, 'interesting'),
(60, 65, 'fail'),
(85, 90, 'fail');

The 'start' and 'stop' values stored in the database are numbers of type
 REAL, representing seconds. There is no need for calculations with, or
transformations between, elaborate time representation formats.

Here is a cognitive approach to a solution:

0. Starting with a dataset like this:
10.0|30.0|interesting
12.0|32.0|interesting
15.0|20.0|fail
16.0|39.0|interesting
17.0|21.0|fail
50.0|80.0|interesting
60.0|65.0|fail
85.0|90.0|fail

1. Find all of the "interesting" segments.
10.0|30.0|interesting
12.0|32.0|interesting
16.0|39.0|interesting
50.0|80.0|interesting

2. Find any "interesting" segments with overlaps and merge them.
10.0|39.0|interesting
50.0|80.0|interesting

3. Find all "fail" segments with a period that overlaps the period of any
(step 2) "interesting" segment.
15.0|20.0|fail
17.0|21.0|fail
60.0|65.0|fail

4. Find any overlaps in those (step 3) "fail" segments and merge.
15.0|21.0|fail
60.0|65.0|fail

5. Derive a new list of "interesting" segments from (step 2) that omits
all "fail" segments from (step 4).
10.0|15.0|interesting
21.0|39.0|interesting
50.0|60.0|interesting
65.0|80.0|interesting

A relational database solution is needed. I am not yet very familiar
with relational database design and SQL beyond the very basics. So any
pointers to similar SQL problems with solutions and explanations would
be tremendously useful at this point. Any hints at all, really, will be
much appreciated.

Beyond a basic solution, I suspect something like an R-Tree index might
be useful. I gather this from the SQLite page on R-Trees:

https://sqlite.org/rtree.html

--

SELECT version();
                                                 version

---------------------------------------------------------------------------------------------------------
 PostgreSQL 11.1 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.5
20150623 (Red Hat 4.8.5-28), 64-bit
(1 row)