Many thanks for your neat, simple suggestion, Michael. Sometimes you can miss
the wood for the btrees...
Using tables seems a very attractive way to maintain such a hierarchy. The
problem is that I need to be able to operate on the structure in a way not
limited to just updating nodes and adding new ones. What I want to implement is
a general cut/copy/paste mechanism - which is why I investigated btree-like
data structures in the first place. Cutting and pasting in a btree is simple,
often being no more than a matter of reorganizing a few pointers. A tree with a
vast number of nodes (such as a typical b+tree) can be modified in this way
with O(logN) efficiency. And in such a hierarchical arrangement as the one I
require, localised changes are just as cheap, simply propagating up the tree to
the root. What I am wondering, then (leaving aside the question of hierarchy),
is if such a cut/copy/paste mechanism can be implemented using Sqlite tables,
and if so how efficient is it likely to be? Might a virtual table created via
ATTACH be useful here?
Apologies for any naive assumptions - I've studied trees a lot but not so much
SQL!
Thanks,
Christopher
> From: michael.bla...@ngc.com
> To: sqlite-users@sqlite.org
> Date: Sun, 10 Jul 2011 19:41:07 +0000
> Subject: Re: [sqlite] Storing/editing hierarchical data sets
>
> 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
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
