Re: [sqlite] Storing/editing hierarchical data sets

[Christopher Melen]

Thank you again, Michael - a very interesting suggestion. I'm going to start 
experimenting with your previous suggestion of a linked list. This is simple 
and intuitive, and I can see it working very well. In fact it's a similar 
principle to that used by Audacity, the open source audio editor, which 
segments the original audio into a linked list of temporary 'block' files, 
enabling fast cut/copy/paste manipulations (in contrast to many editors, which 
rely on literal copying and insertion into a single file).


I will be storing my data as blobs between 1024 and 2048 bytes, rather than 
individual samples. Of course it is extremely unlikely that any cut or copy 
selection will fall on the boundary of a blob - most of the time it will slice 
through it. So any blob thus affected will have to be rebuilt, or its data 
redistributed to neighbouring rows. Given the average size of a blob this 
shouldn't be an issue, however. And even for a large file experiment indicates 
that the corresponding reduction hierarchy will be unlikely to exceed a few MB.


So now I am going to actually perform some tests...



Many thanks again,
Christopher

> From: michael.bla...@ngc.com
> To: sqlite-users@sqlite.org
> Date: Tue, 12 Jul 2011 11:38:13 +
> Subject: Re: [sqlite] Storing/editing hierarchical data sets
> 
> I thought of another way to do your copy/cut/paste...
> 
> 
> 
> Assuming you keep the original audio around and use the levels I showed 
> before.
> 
> 
> 
> create table sequence(level int,parent int,start int,end end);
> 
> insert into seqeunce values(1,0,0,-1); // note that -1 means "until end of 
> data".
> 
> 
> 
> See where I'm going?  You keep a sequence table that is much like your btree. 
>  It's just a collection of clips that when strung together can make your 
> audio clip.  By default you have one sequence per level.
> 
> 
> 
> Cut 1000-1999 from level=1
> 
> select * from sequence where level=1;
> 
> delete from sequence where level=1;
> 
> insert into sequence values(1,0,0,999);
> 
> insert into sequence values(2,1,2000,-1);
> 
> 
> 
> Insert some data:
> 
> 1st you find where it fits
> 
> select * from sequence where level=1;
> 
> bytes1=0;
> 
> while moredata
> 
>   bytes2+=end-start;
> 
>   if (insertpoint >=bytes1 and insertpoint <=bytes2)
> 
>   update sequence set id=id+1,parent=parent+1 where id>=currentid;
> 
>   break;
> 
> end
> 
> 
> 
> Cuts are just splitting one record in 2, or adjusting 2 records and deleting 
> records in between.
> 
> I'll leave that as an exercise for you.
> 
> 
> 
> This would
> 
> 
> 
> 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  9117   54   31  201   
> 214  66
> 
> 
> 251 18 5 91   11 17 54 169 31 201 148173 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 

Re: [sqlite] Storing/editing hierarchical data sets

[Black, Michael (IS)]

I thought of another way to do your copy/cut/paste...



Assuming you keep the original audio around and use the levels I showed before.



create table sequence(level int,parent int,start int,end end);

insert into seqeunce values(1,0,0,-1); // note that -1 means "until end of 
data".



See where I'm going?  You keep a sequence table that is much like your btree.  
It's just a collection of clips that when strung together can make your audio 
clip.  By default you have one sequence per level.



Cut 1000-1999 from level=1

select * from sequence where level=1;

delete from sequence where level=1;

insert into sequence values(1,0,0,999);

insert into sequence values(2,1,2000,-1);



Insert some data:

1st you find where it fits

select * from sequence where level=1;

bytes1=0;

while moredata

  bytes2+=end-start;

  if (insertpoint >=bytes1 and insertpoint <=bytes2)

  update sequence set id=id+1,parent=parent+1 where id>=currentid;

  break;

end



Cuts are just splitting one record in 2, or adjusting 2 records and deleting 
records in between.

I'll leave that as an exercise for you.



This would



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  9117   54   31  201 
  214  66


251 18 5 91   11 17 54 169 31 201 148173 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

Re: [sqlite] Storing/editing hierarchical data sets

[Alexey Pechnikov]

See FTS3 extension where the full-text index is stored in multi btree
in regular tables. Note: FTS2 is more simple.

-- 
Best regards, Alexey Pechnikov.
http://pechnikov.tel/
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Storing/editing hierarchical data sets

[J Decker]

On Sun, Jul 10, 2011 at 10:52 AM, Christopher Melen
 wrote:
>
> 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 developed an option tree that is heirarchal and is basically like a
registry.  I only store the parent_id, since order isn't entirely
important.

node_id | parent_node_id | content | sequence

maybe adding a sequence if which is to the left or right is
important but this isn't really binary treeing either

if you want what's under a thing just select who has that node_id as a
parent_node_id




>
> 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

Re: [sqlite] Storing/editing hierarchical data sets

[Black, Michael (IS)]

I can see adding a forward/reverse link to the tables making it a linked-list 
type structure much like your btree.

By default each node is linked to the one in front and back.  Then you adjust 
those pointers for cut/paste operations.

You could also do the cut/paste just by copying to a new table.





If you want a disk-based B-Tree try this:

http://www.die-schoens.de/prg/





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: Monday, July 11, 2011 3:28 PM
To: sqlite-users@sqlite.org
Subject: EXT :Re: [sqlite] Storing/editing hierarchical data sets


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 +
> 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:5

Re: [sqlite] Storing/editing hierarchical data sets

[Christopher Melen]

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 +
> 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  9117   54   31  201   
> 21

Re: [sqlite] Storing/editing hierarchical data sets

[Petite Abeille]

On Jul 10, 2011, at 9:41 PM, Black, Michael (IS) wrote:

> Somebody smarter than I may be able to figure out how to use views to do the 
> upper levels.

Was there a question hidden somewhere in your post? :)

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Storing/editing hierarchical data sets

[Black, Michael (IS)]

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  9117   54   31  201 
  214  66


251 18 5 91   11 17 54 169 31 201 148173 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] Storing/editing hierarchical data sets

[Christopher Melen]

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  9117   54   31  201 
  214  66


251 18 5 91   11 17 54 169 31 201 148173 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