Extending the Nested Sets Model with "Hardlinked Nested Sets"

Locked
friesengeist
Joomla! Guru
Joomla! Guru
Posts: 842
Joined: Sat Sep 10, 2005 10:31 pm

Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by friesengeist » Thu Jul 12, 2007 11:30 am

Hi all,

today I actually received a question about my Summer of Code project, so I thought I'd bring any discussion into the public, so that more people can get involved :)


First of all, what is the project Extending the Nested Sets Model with "Hardlinked Nested Sets" all about?

As some of you may know, the Nested Sets Model is a data model for organizing data in tree structures of unlimited depth. This model can be used for almost everything which can be organized in hierarchical trees. To give an example, "Categories" are almost always a candidate for this. But it applies to many more things. Currently, there's another Joomla! Summer of Code Project, the Joomla 1.5 Forum Component. I'm in contact with Niels, and his project will use the Nested Sets Model to save the structure of Forum Boards as well as Forum threads.

Now I called my project 'Extending the Nested Sets Model with "Hardlinked Nested Sets"', because I want to work on one very specialized part of this broad topic. I want to make it possible to put subtrees multiple times into the whole tree. This allows for example to copy a category into many different parent categories, and when a content item (articles, weblinks, newsfeeds, whatever...) is added to one of these categories, it will automatically appear in the other categories as well. Think of it like hardlinked filesystem paths under operating systems which support it. (For the more technical oriented reader, I named it hardlinked instead of softlinked, because I'm not setting up pointers like softlinks, as they would need recursive processing. That can be avoided by using my proposed model.)


So what will be the outcome of this project? Does Joomla! support unlimited nested categories with this?

I know that this feature has been requested many many times, and I also want to have it. However, we are not there yet... I will provide libraries which allow dealing with the Nested Set Data Structure. These libraries will be fully unit tested (actually, I use test-driven-development, which means that I write automated tests for the libraries first, while they are not even implemented. Only after that, I write the actual library code). So by the end of this years Summer of Code, we should have some very stable libraries for dealing with Nested Sets, and Hardlinked Nested Sets.

That means that I will not yet implement anything like a new category manager. When the code I produce will be implemented into Joomla! is a decision of the whole development workgroup, and of our Coordinator and our Lead Developers especially. I'm currently writing the libraries for PHP5 only, but it could be that they can be made compatible with PHP4 quite easily. So it *could* be that they end up in 1.6 or 1.7, to be used by 3PD developers. But it could also happen that they will be integrated not before 2.0. I can't give you an answer about that yet, though I wish to see them in one of the 1.x releases of course :)

From there on, the libraries can be used for almost everything which can be organized in a hierarchical structure.


What about the technical details?

I've put up my proposal for the SoC project on the JoomlaCode documents section some time ago. You can download it as a PDF document.


Questions? Suggestions? Comments?

I'm open for questions and suggestions, so if you would like to know anything about the project, or have anything to add, just reply to this thread :)

Enno
We may not be able to control the wind, but we can always adjust our sails

User avatar
willebil
Joomla! Guru
Joomla! Guru
Posts: 762
Joined: Thu Aug 18, 2005 12:06 pm
Location: Netherlands

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by willebil » Thu Jul 12, 2007 11:52 am

Thanks for this nice summary Enno!

AmyStephen
Joomla! Champion
Joomla! Champion
Posts: 7018
Joined: Wed Nov 22, 2006 3:35 pm
Location: Nebraska
Contact:

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by AmyStephen » Thu Jul 12, 2007 9:00 pm

friesengeist wrote:I want to make it possible to put subtrees multiple times into the whole tree. This allows for example to copy a category into many different parent categories, and when a content item (articles, weblinks, newsfeeds, whatever...) is added to one of these categories, it will automatically appear in the other categories as well.
Wow! Enno - that goes *well* beyond my expectation. I had incorrectly understood you were dealing only with the section-category-article structure.

Now, do you see this as potentially replacing the section-category structure, or as the beginnings of a new menuing system? I see some benefits to eliminating section-category, entirely. With this type of thinking where all objects are treated the same, eliminating that structure could make even more sense.

It's got to be difficult to design this, without also considering a redesign of the ACL. It's all tied together, huh? ;)

Thanks very much for your efforts and the update on this very important project,
Amy :)

friesengeist
Joomla! Guru
Joomla! Guru
Posts: 842
Joined: Sat Sep 10, 2005 10:31 pm

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by friesengeist » Sat Jul 14, 2007 10:54 am

Hi Amy,
AmyStephen wrote: Wow! Enno - that goes *well* beyond my expectation. I had incorrectly understood you were dealing only with the section-category-article structure.
It's one layer deeper than that. Before we can deal with the content structure, we need to have the libraries in place which deal with the Nested Sets Model.
AmyStephen wrote: Now, do you see this as potentially replacing the section-category structure, or as the beginnings of a new menuing system? I see some benefits to eliminating section-category, entirely. With this type of thinking where all objects are treated the same, eliminating that structure could make even more sense.
In the long run, the node based scheme will replace sections and categories. That's not part of my SoC project, though. The project would have gotten too big if I had included any of that into it. I'll make sure that the libraries which I program will be able to handle any kind of content, be it categories, weblinks, newsfeeds, articles, comments, books...
You wont be able to see any real user interface for this though. All that are the next steps once the NBS table libraries are finished after this years SoC.
AmyStephen wrote: It's got to be difficult to design this, without also considering a redesign of the ACL. It's all tied together, huh? ;)
It is, but I'm also not dealing with the ACL stuff as part of the SoC project. I'll make sure that ACL - when implemented - can work with the Hardlinked Nested Sets as if it was just a normal tree. That means that once ACL is implemented, and you specify some rules for e.g. a specific category, these rules will automatically apply for any "hardlinked" copies of the category as well.

Hope that answers most of your questions :)
We may not be able to control the wind, but we can always adjust our sails

AmyStephen
Joomla! Champion
Joomla! Champion
Posts: 7018
Joined: Wed Nov 22, 2006 3:35 pm
Location: Nebraska
Contact:

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by AmyStephen » Sat Jul 14, 2007 12:05 pm

friesengeist wrote: Hope that answers most of your questions :)
Yes, indeed, thank you! This is going to provide the foundation to restructure Joomla! in a very powerful way. Thank you for your efforts.

Amy :)

User avatar
darb
Joomla! Hero
Joomla! Hero
Posts: 2038
Joined: Thu Jul 06, 2006 12:57 pm
Location: Stockholm Sweden

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by darb » Thu Jul 19, 2007 11:50 am

Well this is good news! Hope we will have this feature soon in Joomla... ???

I just saw this MySql model too about "Managing Hierarchical Data in MySQL"

http://dev.mysql.com/tech-resources/art ... -data.html
and the earlier discussions here too  :) http://forum.joomla.org/index.php/topic,67076.0.html

User avatar
darb
Joomla! Hero
Joomla! Hero
Posts: 2038
Joined: Thu Jul 06, 2006 12:57 pm
Location: Stockholm Sweden

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by darb » Wed Aug 08, 2007 9:00 am

author=friesengeist link=topic=189840.msg899337#msg899337 date=1184239812]
Hi all,

today I actually received a question about my Summer of Code project, so I thought I'd bring any discussion into the public, so that more people can get involved :)

Hi Enno,

any news about how its going with this project?

Hope you are progressing and it should be nice to hear whats going on.. ;) hope though that the integration with the forum component don't slow this down...

friesengeist
Joomla! Guru
Joomla! Guru
Posts: 842
Joined: Sat Sep 10, 2005 10:31 pm

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by friesengeist » Thu Aug 09, 2007 6:49 pm

darb wrote: Hi Enno,

any news about how its going with this project?

Hope you are progressing and it should be nice to hear whats going on.. ;) hope though that the integration with the forum component don't slow this down...
Ah, sure, you guys want to stay updated, I forgot, sorry :D

So, a small status update, about some of the things I've done in the last weeks:
  • The "Hardlinked Nested Sets"-Part of the libraries is making good progress. All functions have been implemented, the basic functionality is working as it should.
    Some functions need a little more refactoring, but the "data handling" parts are nearly complete (that is, updating the "lft" and "rgt" sequence Id's in always one single query - the query count of operations with hardlinked nested sets does *not* increase with the number of hardlinked nodes! (Although there are usually one or two more queries for hardlinked operations than the plain/non-hardlinked equivalent would need)).
  • Integration with the forum component didn't slow this down at all - Niels and I found a temporary solution where he can use the NBS libraries in it's current, incomplete state.
    One of the things I'll have to do in the next days is to add the functionality which is needed to use the NBS libraries in other applications. I concentrated on the data handling part until now, to make sure that the functions do never produce a corrupt tree structure. So the library is (nearly) only useful for the unit test so far, but that will change soon.
  • Technical detail: JHardlinkedTable and JNBSTable now both implement the interface JNBSTableInterface. Since JHardlinkedTable overwrites every function of JNBSTable anyway, there is no use of extending JNBSTable in JHardlinkedTable. This makes the NBS libraries the first Joomla! classes (that I am aware of) that implement an interface.
darb wrote: I just saw this MySql model too about "Managing Hierarchical Data in MySQL"

http://dev.mysql.com/tech-resources/art ... -data.html
Actually, the non-hardlinked NBS library (where many parts are from last year's SoC) is based on that article, at least it says so in the file header ;)
darb wrote: and the earlier discussions here too  :) http://forum.joomla.org/index.php/topic,67076.0.html
I remember reading that discussion last year, when it was active... Thanks for the pointer :)


I've attached the output of a current test run to this post, as you can see the NBS libraries are tested by 422 tests right now.
BTW, whoever wants to follow up on the development, without creating your own SVN checkout, here's the changelog. There's also one folder just for documentation.

If anyone is interested in a more detailed explanation of the "Hardlinked Nested Sets" (internal technical details, as well as "how do i use it in my own code" questions), please let me know :)
You do not have the required permissions to view the files attached to this post.
We may not be able to control the wind, but we can always adjust our sails

friesengeist
Joomla! Guru
Joomla! Guru
Posts: 842
Joined: Sat Sep 10, 2005 10:31 pm

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by friesengeist » Mon Aug 20, 2007 9:38 pm

Another update, now that the "pencils down" deadline for SoC has passed:

The classes JHardlinkedTable and JNBSTable now both are "complete". It could be that there are some smaller bugs around, or some functionality still missing which I did not think of before (since I only tested the classes from the unit tests, but not "in the wild"), but generally, they should be usable for creating and handling tree structures and the associated data rows. All functions that I have written are fully unit tested.

I wished to get a bit further than I did with "routing" to tree items. However, at least a comprehensive document about how the routing should work has been created, it can be found here on joomlacode.org. That should hopefully eliminate all the problems that the Itemid brought us - the document is about finding the correct menu item based on the current page someone visits and the target content item where he wants to go to.

I will definitely keep working on the NBS structure. There's still plenty of work to do before it can really be used in a component. For example, a model class for reading the NBS tree page-wise (to display a tree just like the menu manager does now) needs to be created. I don't want to give a timeline or promise anything here, but I'll keep you posted ;)

Another thing which I believe is missing is some more documentation. Although I wrote documentation about my "Hardlinked Nested Sets", I guess that it makes sense to provide some basic info about the NBS classes or some working examples? Let me know if there is anyone working/experimenting with the libraries... :)
We may not be able to control the wind, but we can always adjust our sails

User avatar
moijafcor
Joomla! Enthusiast
Joomla! Enthusiast
Posts: 218
Joined: Thu Mar 02, 2006 9:41 am
Location: Santo Domingo, Dominican Republic
Contact:

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by moijafcor » Fri Sep 07, 2007 5:27 am

If anyone is interested in a more detailed explanation of the "Hardlinked Nested Sets" (internal technical details, as well as "how do i use it in my own code" questions), please let me know
I am!!!!

Brilliant idea, Enno!

Enhorabuena...

P.S. Please take a look at this thread: http://forum.joomla.org/index.php/topic,199298.0.html
Nicht mehr!
Los acentos en castellano omitidos intencionalmente. | Les accents et les signes en français omis intentionnellement.
http://bio.moisesjafet.com

friesengeist
Joomla! Guru
Joomla! Guru
Posts: 842
Joined: Sat Sep 10, 2005 10:31 pm

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by friesengeist » Mon Sep 24, 2007 10:35 pm

moijafcor wrote:
If anyone is interested in a more detailed explanation of the "Hardlinked Nested Sets" (internal technical details, as well as "how do i use it in my own code" questions), please let me know
I am!!!!

Brilliant idea, Enno!
I just wanted to let you know that I haven't forgotten about this ;)
I just didn't have any time available the last weeks, but should hopefully get to it shortly...
We may not be able to control the wind, but we can always adjust our sails

User avatar
darb
Joomla! Hero
Joomla! Hero
Posts: 2038
Joined: Thu Jul 06, 2006 12:57 pm
Location: Stockholm Sweden

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by darb » Sat Oct 20, 2007 5:37 pm

Any news and status about this?  should be nice to hear...... :pop

Think you also should emphasis on the first topic July 12, 2007 with links to the Joomla code project so people can go there more easily, read and also see the stuff there.

You know if anyone using this yet?
Last edited by darb on Sun Dec 09, 2007 8:48 am, edited 1 time in total.

User avatar
darb
Joomla! Hero
Joomla! Hero
Posts: 2038
Joined: Thu Jul 06, 2006 12:57 pm
Location: Stockholm Sweden

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by darb » Fri Dec 21, 2007 10:45 pm

darb wrote: Any news and status about this?  should be nice to hear...... :pop

Think you also should emphasis on the first topic July 12, 2007 with links to the Joomla code project so people can go there more easily, read and also see the stuff there.

You know if anyone using this yet?
Joomla still sleeping and Drupal moves on with faster and faster development speed... :pop

AmyStephen
Joomla! Champion
Joomla! Champion
Posts: 7018
Joined: Wed Nov 22, 2006 3:35 pm
Location: Nebraska
Contact:

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by AmyStephen » Fri Dec 21, 2007 11:02 pm

darb wrote:
darb wrote: Any news and status about this?  should be nice to hear...... :pop

Think you also should emphasis on the first topic July 12, 2007 with links to the Joomla code project so people can go there more easily, read and also see the stuff there.

You know if anyone using this yet?
Joomla still sleeping and Drupal moves on with faster and faster development speed... :pop
Darb -

Do *not* pit open source projects against one another. We are not competing with Drupal. We hope they are progressing quickly! We hope they are developing more and more. They are friends of ours - not enemies - not anyone we are trying to beat.

Here are our choices: 1) Wait for people to build what we want and offer it to us freely. 2) Do it ourselves and offer it for others. 3) Pay someone to build it for us and share it with the community. 4) Use what's available - and that includes Drupal. Use it if it meets your needs!

Now, be nice or don't post.

Amy

User avatar
darb
Joomla! Hero
Joomla! Hero
Posts: 2038
Joined: Thu Jul 06, 2006 12:57 pm
Location: Stockholm Sweden

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by darb » Sat Dec 22, 2007 12:34 am

[quote Joomla still sleeping and Drupal moves on with faster and faster development speed... :pop
[/quote]
AmyStephen wrote:
Darb -

Do *not* pit open source projects against one another. We are not competing with Drupal. We hope they are progressing quickly! We hope they are developing more and more. They are friends of ours - not enemies - not anyone we are trying to beat.

Here are our choices: 1) Wait for people to build what we want and offer it to us freely. 2) Do it ourselves and offer it for others. 3) Pay someone to build it for us and share it with the community. 4) Use what's available - and that includes Drupal. Use it if it meets your needs!

Now, be nice or don't post.

Amy
Sorry for that post I do understand that things take time especially with a open source project like this :-[. I really love and like Joomla but there is also a question of priority here. And It seems that nothing happens with this good work from Enno Klasing.

Amy, in my opinion it is of course between competition between different systems and subsystems!  Why should Joomla not be proud of that they just won the "Joomla! Wins 'Best CMS Award' Again" if they don't  want to be part of that CMS competition? This is the same logic for open source or commercial applications. If you not create a good value to the end users you will have less end users and the project will soon be dead bcs other competitors are better.

So I believe its good to learn from other world leading open source projects like phpBB, SPAGO, TALEND etc in many aspects and also good to see what, I believe is the main CMS competitor, Drupal is doing so you don't need to invent the wheel again. 

If you understand and use intelligent criticism positive there is a 5th choice too and that is about core priority for J 1.5. This priority, in my opinion is about creating the long discussed taxonomy, hierarchies and nodes where Drupal is far away from what Joomla is doing now and the doing many things very fast now coming from their 3pds add ons.

So Amy maybe I am not a nice person that always talk nice about Joomla but I also think that we can do things better and better so Joomla will be the no 1 CMS open source choice of everyone in future!

Merry Christmas and a Happy New Year to you!

AmyStephen
Joomla! Champion
Joomla! Champion
Posts: 7018
Joined: Wed Nov 22, 2006 3:35 pm
Location: Nebraska
Contact:

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by AmyStephen » Sat Dec 22, 2007 1:06 am

darb wrote: So Amy maybe I am not a nice person that always talk nice about Joomla but I also think that we can do things better and better so Joomla will be the no 1 CMS open source choice of everyone in future!
Darb -

What do you mean *we* can do things better and better? What is your contribution to Joomla!? I actually had one person tell me that his contributions were his criticism of our work. That, we don't need.

What we need are people who will help with the work. Doing work is what makes Joomla! better and better and better.

Your unkind words are not magical powers that shame what you must think are lazy or stupid contributors into working. Unkind words are just discouraging.

If you want Joomla! to be better, then, let that desire motivate you into contributing. If you prefer not to help, then fine, you do not have to help to take our freely offered gifts. But, please do not discourage those of us who are trying.

Enough of this.

Amy :)

User avatar
darb
Joomla! Hero
Joomla! Hero
Posts: 2038
Joined: Thu Jul 06, 2006 12:57 pm
Location: Stockholm Sweden

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by darb » Sat Dec 22, 2007 9:37 am

"What do you mean *we* can do things better and better? What is your contribution to Joomla!? I actually had one person tell me that his contributions were his criticism of our work. That, we don't need."
"Your unkind words are not magical powers that shame what you must think are lazy or stupid contributors into working. Unkind words are just discouraging."  ".....you do not have to help to take our freely offered gifts"
Amy,

You are right that I am not a contributing core php programmer and I think this structure of Joomla don´t need more of that power too. Its fine as it is with that but I never never think and write that Jomla developers are lazy or stupid contributors into working Amy!

I know they are very skilled and intelligent people and I also admirer them for their work and contributions to this "Open Source Matters". This is one of the reasons why I not leave for Drupal...

And I also must admit that I don't like the way you jump on my as a person like this and to interfere me with other controversies you have had with other persons in these kind of questions about criticism is not fair.

I am used to be in a real democratic country where we are open to discuss everything in a transparent manner and I don't look at criticism like you do maybe. No control and interfere of e-mail, blogs, forums, checking peoples electronic transactions, opinions etc. So I like to be encourage to be open about criticism and it is important too in my opinion for making things better. "Open Mouth Matters" also. :D

"We" you and me are the Joomla community with a structure of different people from all of the world that contribute with different skills and brain power in different ways if it so is programming, promoting, designing, bringing in good ideas etc to this community. Not everyone is being seen on headlines of the Joomla site everyday but that doesnt mean that they are not important to Joomla.

So earlier I have discussed about Joomla and what happens with JNBS - not about Joomla people. I just follow this thread and personally get a little disappointed about no one using JNBS and also about other adjacent questions to using JNBS.

I am just working with Joomla spare time and what I am trying to do now is promoting Joomla to end users so there is a need for this kind of open source alternative for different kind of people and organizations. Now I working on a voluntary project for a central labor union covering 4 countries in Europe leaving another commercial CMS system, competition ?

I also try to help different 3 pds developer to make their work getting better so the value of using Joomla increases. 

I never intent to discourage a n y o n e and if so I apologize for that.

You are right "Doing work is what makes Joomla! better and better and better.;) Its not what you say its what you do that matters!

Amen

AmyStephen
Joomla! Champion
Joomla! Champion
Posts: 7018
Joined: Wed Nov 22, 2006 3:35 pm
Location: Nebraska
Contact:

Re: Extending the Nested Sets Model with "Hardlinked Nested Sets"

Post by AmyStephen » Sat Dec 22, 2007 2:38 pm

darb wrote: And I also must admit that I don't like the way you jump on my as a person like this and to interfere me with other controversies you have had with other persons in these kind of questions about criticism is not fair.

I am used to be in a real democratic country where we are open to discuss everything in a transparent manner and I don't look at criticism like you do maybe.
I am curious how you reconcile those ideas.  How is it unfair if I "jump on" you and "interfere" with your "right" to "criticize" others? If you have a right to complain, don't I?

Whether you intend it, or not, these types of approaches *do* discourage contributors. Consider now, the implications IF what I said is true. If these approaches (in this case, unfriendly, sarcastic comparisons to another open source project because someone is disappointed the feature they want is not yet available) actually do discourage contributors, what should someone do when they see it happening?

You are not understanding how free software communities work. Joomla! is not a democracy. The work in this project is accomplished by unpaid volunteers. People who use the Joomla! software are not entitled to decide what volunteers are required to do. Volunteers are free to contribute and free not to contribute. Our "disappointments" and expectations do not make them our slaves.

Those who want a voice in the direction of this project, those who want to become members of this community, earn that voice and that membership through contribution.

There is a documentation weekend coming up in January where we can participate as a community members to make available help screens and user guides and FAQs for Joomla! v 1.5. It will be similar to the bug smashing weekend developers participated in a couple of weekends ago. Please consider joining us. Getting that work done will help make Joomla! better and we need your help.

Amy

User avatar
darb
Joomla! Hero
Joomla! Hero
Posts: 2038
Joined: Thu Jul 06, 2006 12:57 pm
Location: Stockholm Sweden

Re: Extending the Nested Sets Model with

Post by darb » Mon Aug 25, 2008 7:49 am

Coming back to topic. :pop

I just try to follow this good intention from Enno but I have not seen anyone in the Joomla community to use this?

I tried long time inform about this but no one interested even in directory forums like Mosets where it fits perfectly. I only get comments like this if this is something for the real world? I believe.

-------------------------------------------------------------------------------------------------------------------------------------------
Not sure if this is something for the real world? Sound like some mad data modelling structure to talk and discuss about. But if this is really something we need I am not sure . I read to many of these mindboggling software theories that have never seen the light of day. Interesting concept nonetheless. Will keep an eye on it. http://www.mosets.com/forum/showthread.php?t=5791
-------------------------------------------------------------------------------------------------------------------------------------------

Maybe I have missed something about this but If anyone knows if this have been used somewhere pls post and tell us!

Best rgds


Locked

Return to “Past Google Summer of Code Editions”