I know that this question is not strictly related to SQLite.
I want to persist a random-access sequence with SQLite. A random-access
sequence is a queue with random-access to its queued elements. Suppose
that a random-access sequence [x_0, ..., x_n] has the following operations:
enqueue([x_0, ..., x_n], x) = [x_0, ..., x_n, x]
dequeue([x_0, ..., x_n]) = [x_1, ..., x_n]
lookup([x_0, ..., x_n], i) = x_i
update([x_0, ..., x_n], i, y) =
[x_0, ..., x_(i - 1), y, x_(i + 1), ... x_n]
length([x_0, ..., x_n]) = n + 1
A naive implementation list-based would have at least one operation that
is in O(n).
A possible implementation in SQLite with all operations in O(log n)
could be:
CREATE TABLE sequence (
position INTEGER PRIMARY KEY AUTOINCREMENT,
...
);
-- enqueue
INSERT INTO sequence VALUES (...);
-- dequeue
SELECT position, ... FROM sequence ORDER BY position ASC LIMIT 1;
DELETE FROM sequence WHERE position = :position;
-- lookup
SELECT position AS start, ... FROM sequence
ORDER BY position ASC LIMIT 1;
SELECT ... FROM sequence WHERE position = :start + :i;
-- update
UPDATE sequence SET ... WHERE position = :i;
-- length
SELECT position AS start, ... FROM sequence
ORDER BY position ASC LIMIT 1;
SELECT position AS end, ... FROM sequence
ORDER BY position ASC LIMIT 1;
SELECT :end - :start + 1;
Unfortunately, this limits the maximum number of elements that can ever
be inserted during a table's life-time to 2^63 - 1. While this might be
acceptable in some cases it is an artificial limitation.
It seems that one way that is not subject to to such limitations is to
abuse tables as lists and use algorithms for purely functional data
structures. There is an algorithm that could be used to implement
random-access sequences in SQLite efficiently [1] but it's neither
elegant nor simple.
Does anyone have another idea how to elegantly implement random-access
sequences in O(log n) in SQLite?
- Matthias-Christian
[1] Robert Hood and Robert Melville. Real-time queue operations in pure
LISP
