Saturday, December 18, 2004

L-TREE a new datastructure for efficient hierarchy representation in a database.....

Hey don't say that you guys have never came across an LDAP server....hmm...ok its your directory within your organizaion.....since every organizaition is hierarchical in the sense a 'senior manager' has several 'managers' reporting to him and a 'manager' has 'developers' etc.....so all this data is hierarchical. So if I were to give you this problem and make a system which will report queries like 'gimme all the employees under employee X' how would you approach the problem ?....
One quick solution is create a table in the database
CREATE TABLE ORG_DIR (int EMP_ID NOT_NULL,VARCHAR(10) EMP_NAME, int SUP_ID);
To answer that you might query the database like
SELECT T1.EMP_NAME
FROM ORG_DIR T1, ORG_DIR T2
WHERE T1.SUP_ID == T2.EMP_ID && T2.EMP_ID = &INPUT

Finally you have got a workaround...Unfortunately this kind of workarounds seem to be very inefficient for storing and retriving Structured Hierarchical Data hmm...I know you are thinking about some thing right??? XML :)) Yes its XML. How can I store XML in my database and answer my queries on the Hierarchical data. My Idea is to make HIERARCHY as a datatype itself rather than some thing else. That is just as we have primitive datatype support within a database..ie every column in the database would be of some primitive datatype supported by the database...so The idea is can we make HIERARCHY a datatype.....hey wait a sec just figured out I'am not the only one who thought about it....yes Oleg has alreay added a great Contrib Module for postgresql. Oleg made is generic so that you can persist any label based HIERARCHY...now I have a good Idea in extending L-TREE to support XML....its really great to have such an optimized HIERARCHY representation for structured data...people have been talking about indexing and datastructures for XML Databases but this seems to me as a really good contribution from Oleg..... Vamsi

Tuesday, December 14, 2004

Useful unix command for finding all the files recusively which contain a string

peemt4:vamsik:(vamsi_aix_ns_port):/vobs/ETG_Repository/src>find . -name "*.c" -exec grep -i "Your Search String" \{\} \; -print
Sound simple but thought it would be useful....

Saturday, December 04, 2004

Moving from STL to GTL

GTL
Originally uploaded by vamsi.
Most of the developers building any systems are generally stuck with the problem of implementing graph algorithms. Graph algorithms are really fundamental algorithms and are applied extensively...take the following example's

1. Circuit Partitioning: The stage where the designer had come up with a netlist and technology mapping being done. Now want to partition the circuit so that highly connected blocks stay together.....So when I talk about netlist....there it goes the HYPERGRAPH. The most fundamental netlist representation so to make systems which process these hypergraphs (netlist's) you need to write code in a very generic manner because the partioned hypergraph by the partitioning algorithms will be used by the placement algorithms and it goes on and on.......hmmmm now I recollect the network stack where pointer to the packet is passed across several layers and its done in such a way that to avoid redundancy involved in copying over the stack (process stack not network stack) they use a pointer to some heap space.......similarly in EDA tools where the netlist is taken through several stages(involves verification also) and finally realized into physical geometry, the developers especially EDA tool developers need some generic implementations like STL....its really great TEMPLATE LIBRARY lets you quickly do your tasks and modify only appropriate parts of the algorithms.....but STL has no support of hypergraphs...I mean not even graphs....you need to create your own Graph Container on the existing framework.....so now to avoid this we have got GTL a great libray.....I came across it while helping a friend in implementing KLM circuit partitioning algorithm...I feel that it would be really helpful for may other computer science domains apart from CAD....

Cheers
Vamsi