Somebody smarter than I may be able to figure out how to use views to do the
upper levels.
But if you can afford your database to be a bit less then twice as big just use
tables.
create table level1(id int,l int,r int);
insert into level1 values(1,251,18);
insert into level1 values(2,5,91);
insert into level1 values(3,11,17);
insert into level1 values(4,54,16);
insert into level1 values(5,9,31);
insert into level1 values(6,201,148);
insert into level1 values(7,173,214);
insert into level1 values(8,43,66);
select max(l,r) from level1;
251
91
17
54
31
201
214
66
create table level2(id int,l int, r int);
insert into level2(l) select max(l,r) from level1 where rowid%2=1;
update level2 set r= (select max(l,r) from level1 where
level2.rowid=level1.rowid/2);
select * from level2;
id|l|r
|251|91
|17|54
|31|201
|214|66
create table level3(id int,l int, r int);
insert into level3(l) select max(l,r) from level2 where rowid%2=1;
update level3 set r= (select max(l,r) from level2 where
level3.rowid=level2.rowid/2);
select * from level3;
id|l|r
|251|54
|201|214
insert into level4(l) select max(l,r) from level3 where rowid%2=1;
update level4 set r= (select max(l,r) from level3 where
level4.rowid=level3.rowid/2);
select * from level4;
id|l|r
|251|214
Now let's update
update level1 set l=90 where id=1;
update level2 set l=(select max(level1.l,level1.r) where
level2.rowid=level1.rowid/2)
update level2 set l= (select max(l,r) from level1 where
level2.rowid=(level1.rowid+1)/2);
select * from level2;
id|l|r
|90|91
|17|54
|31|201
|214|66
update level3 set l=(select max(level2.l,level2.r) from level2 where
level3.rowid=level2.rowid/2);
update level3 set l= (select max(l,r) from level2 where
level3.rowid=(level2.rowid+1)/2);
select * from level3;
id|l|r
|91|54
|201|214
update level4 set l=(select max(level3.l,level3.r) from level3 where
level4.rowid=level3.rowid/2);
update level4 set l= (select max(l,r) from level3 where
level4.rowid=(level3.rowid+1)/2);
select * from level4;
id|l|r
|91|214
Michael D. Black
Senior Scientist
NG Information Systems
Advanced Analytics Directorate
________________________________
From: sqlite-users-boun...@sqlite.org [sqlite-users-boun...@sqlite.org] on
behalf of Christopher Melen [relativef...@hotmail.co.uk]
Sent: Sunday, July 10, 2011 12:52 PM
To: sqlite-users@sqlite.org
Subject: EXT :[sqlite] Storing/editing hierarchical data sets
Hi,
I am developing an application which analyses audio data, and I have recently
been looking into Sqlite as a possible file format. The result of an analysis
in my application is a hierarchical data set, where each level in the hierarchy
represents a summary of the level below, taking the max of each pair in the
sub-level, in the following way:
251 214
251 54 201 214
251 91 17 54 31 201
214 66
251 18 5 91 11 17 54 16 9 31 201 148 173 214 43 66
Such a structure essentially represents the same data set at different levels
of resolution ('zoom levels', if you like). My first experiments involved a
btree-like structure (actually something closer to an enfilade* or counted
btree**), where the data stored in each node is simply a summary of its child
nodes. Edits to any node at the leaf level propagate up the tree, whilst large
edits simply entail unlinking pointers to subtrees, thus making edits on any
scale generally log-like in nature. This works fine as an in-memory structure,
but since my data sets might potentially grow fairly large (a few hundred MB at
least) I need a disk-based solution. I naively assumed that I might be able to
utilize Sqlite's btree layer in order to implement this more effectively; this
doesn't seem possible, however, given that the btree layer isn't directly
exposed, and in any case it doesn't map onto the user interface in any way that
seems helpful for this task.
I am aware of some of the ways in which hierarchical or tree-like structures
can be represented in a database (adjacency lists, nested sets, materialized
paths, etc.), but none of these seems to offer a good solution. What I'm
experimenting with at present is the idea of entering each node of the
hierarchy into the database as a blob (of say, 1024 bytes), while maintaining a
separate in-memory tree which then maps on to this flat database of nodes (each
node in the tree maintains a pointer to a node in the database).
I would be very interested in
thoughts/observations
on this problem - or even better a solution!
Many thanks in advance,
Christopher
* http://en.wikipedia.org/wiki/Enfilade_(Xanadu)
** http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
