Menusystem!

**Hendri Kurniawan** · Feb 8 '07, 06:55 AM

Re: Menusystem!

Jan Morten Sørensen wrote:

Hi All!
>
I am trying to put up a menusystem and need some tips on how to approach
this...
>
>

1. SELECT all parents

SELECT
Category.id, Category.name
FROM Category JOIN Category_relati onships ON Category.id =
Category_relati onship.id
WHERE Category_relati onsip.parentid = 0;

2. For each parent, do a select again, this time with parentid = the id

Just a suggestion, your db structure can be optimized in some ways.

Hendri Kurniawan

**P Pulkkinen** · Feb 8 '07, 12:05 PM

Re: Menusystem!

"Jan Morten Sørensen" <jms@sensewave. comkirjoitti
viestissä:52056 $45ca8cfe$54d23 962$9774@news.c hello.no...

I have this all stored in a mysql-database in the following tables
Category
id(integer, autonumber)
name(text)
language(intege r)

Category_relati onships
id(integer, autonumber)
childid(integer )
parentid(intege r)
language(intege r)

¨
Hello. Like other person already mentioned, there is some database
optimisation need. Parent_id in category table itself would be sufficient,
becuse table CAN refer to itself, also. Not that it would greatly make thing
so much different though. But then in quiries you can do SOMETHING like:

select * from category as thechild, category as theparent where
thechild.parent id = theparent.id (and then other conditions);
(sorry if there's some typos etc., my mysql syntax is in "passive memory"
:-)

and you can get information from both the child and its parent. Just as the
other person mentioned, in menu building you start from oldest parents, who
have 0 as parentid. And then recursively downwards, using the id of the
child as new parentid. You follow every branch to the very end (but since
its recursive work, once you get it right in FUNCTION, you dont worry so
much):

Grandpapa#1 -Papa#1 -Son#1
Grandpapa#1 -Papa#1 -Son#2
Grandpapa#1 -Papa#2 -Son#3
Grandpapa#1 -Papa#2 -Son#4
Grandpapa#2 -Papa#3 -Son#5
Grandpapa#2 -Papa#3 -Son#6
Grandpapa#2 -Papa#4 -Son#7
Grandpapa#2 -Papa#4 -Son#8

Downside is growing number of queries. There are ways, different database
models for this, etc. but it'is also ok to do this, since website menu us
not an excessive list. In the example above, there are 2+4+8=14 categories
and you would get them without trying anything complicated with 7 queries. I
believe that could optimised though.

BTW, after using this model this far, and even after viewing on the surface
alternate models like nested set model, I feel that either xml or an
associative array stored with serialize()-function, would be the most
natural ways to store category strucures, whicha are basicly
multidimensiona l arrays. But I think that we get used to love database
because of the fun of it (?) and searchability. But if someone just would
make a class that would have some sql-like search features, i'd love to
store caterories in simple xml.

**Jan Morten Sørensen** · Feb 8 '07, 02:15 PM

Re: Menusystem!

"P Pulkkinen" <perttu.POISTAT AMA.pulkkinen@P OISTATAMA.elisa net.fiskrev i
meddelandet news:39Eyh.7701 $T22.2430@reade r1.news.saunala hti.fi...

>
"Jan Morten Sørensen" <jms@sensewave. comkirjoitti
viestissä:52056 $45ca8cfe$54d23 962$9774@news.c hello.no...
>

I have this all stored in a mysql-database in the following tables
Category
id(integer, autonumber)
name(text)
language(intege r)

>

Category_relati onships
id(integer, autonumber)
childid(integer )
parentid(intege r)
language(intege r)

¨
Hello. Like other person already mentioned, there is some database
optimisation need. Parent_id in category table itself would be sufficient,
becuse table CAN refer to itself, also. Not that it would greatly make

thing

so much different though. But then in quiries you can do SOMETHING like:
>
select * from category as thechild, category as theparent where
thechild.parent id = theparent.id (and then other conditions);
(sorry if there's some typos etc., my mysql syntax is in "passive memory"
:-)
>
and you can get information from both the child and its parent. Just as

the

other person mentioned, in menu building you start from oldest parents,

who

have 0 as parentid. And then recursively downwards, using the id of the
child as new parentid. You follow every branch to the very end (but since
its recursive work, once you get it right in FUNCTION, you dont worry so
much):
>
Grandpapa#1 -Papa#1 -Son#1
Grandpapa#1 -Papa#1 -Son#2
Grandpapa#1 -Papa#2 -Son#3
Grandpapa#1 -Papa#2 -Son#4
Grandpapa#2 -Papa#3 -Son#5
Grandpapa#2 -Papa#3 -Son#6
Grandpapa#2 -Papa#4 -Son#7
Grandpapa#2 -Papa#4 -Son#8
>
Downside is growing number of queries. There are ways, different database
models for this, etc. but it'is also ok to do this, since website menu us
not an excessive list. In the example above, there are 2+4+8=14 categories
and you would get them without trying anything complicated with 7 queries.

I

believe that could optimised though.
>
BTW, after using this model this far, and even after viewing on the

surface

alternate models like nested set model, I feel that either xml or an
associative array stored with serialize()-function, would be the most
natural ways to store category strucures, whicha are basicly
multidimensiona l arrays. But I think that we get used to love database
because of the fun of it (?) and searchability. But if someone just would
make a class that would have some sql-like search features, i'd love to
store caterories in simple xml.

What then if I wanted to have multiple parents maybe even from different
tree levels?
(Is that possible with your solution?)

I wrote a solution to this last nite after posting this question and it was
smashing. I am thinking about publishing it somewhere because I know others
have the same problem as I do.

--
Jan Morten

http://www.sitconsulting.no

Billig datahjelp i Oslo området.

**Rik** · Feb 8 '07, 02:55 PM

Re: Menusystem!

Jan Morten SÃ¸rensen <jms@sensewave. comwrote:

"P Pulkkinen" <perttu.POISTAT AMA.pulkkinen@P OISTATAMA.elisa net.fiskrev
i
meddelandet news:39Eyh.7701 $T22.2430@reade r1.news.saunala hti.fi...

>>
>"Jan Morten SÃ¸rensen" <jms@sensewave. comkirjoitti
>viestissÃ¤:520 56$45ca8cfe$54d 23962$9774@news .chello.no...
>>

I have this all stored in a mysql-database in the following tables
Category
id(integer, autonumber)
name(text)
language(intege r)

>>

Category_relati onships
id(integer, autonumber)
childid(integer )
parentid(intege r)
language(intege r)

>Â¨
>Hello. Like other person already mentioned, there is some database
>optimisation need. Parent_id in category table itself would be
>sufficient,
>becuse table CAN refer to itself, also. Not that it would greatly make

thing

>so much different though. But then in quiries you can do SOMETHING like:
>>
>select * from category as thechild, category as theparent where
>thechild.paren tid = theparent.id (and then other conditions);
>(sorry if there's some typos etc., my mysql syntax is in "passive
>memory"
>:-)

What then if I wanted to have multiple parents maybe even from different
tree levels?
(Is that possible with your solution?)
>
I wrote a solution to this last nite after posting this question and it
was
smashing. I am thinking about publishing it somewhere because I know
others
have the same problem as I do.

A relational table isn't that uncommon.

I'd trim it down though:

Category
id(integer, autonumber)
name(text)
language(intege r)
Category_catego ries
parent_id (int, index)
child_id (int, index)
(possibly: order (int, index), for a custom order of subcategories in a
categorie)

Keep in mind that 'main' categories (with no parent) should have an entry
in the category_catego ries with parent_id either 0 (as this will never be
assigned as autonumber, or NULL). Be very, very aware that this could
result in everlasting loop when for instance id 1 is both a parent and a
child of id 2...

Now, the next bit has some unwanted overhead, but is a rather simple way
to do it (untested, might need some debugging):
<?php
$list = array(0 =array('childs' ='array'));
$list_result = mysql_query('SE LECT `id`, `name`,`languag e` FROM
`category`');
while($row = mysql_fetch_ass oc($list_result )){
$list[intval($row['id'])] = $list;
}
$relations_resu lt = mysql_query('SE LECT `parent_id`, `child_id` FROM
`category_categ ories` ORDER BY `parent_id`, `order`');
while($row = mysql_fetch_ass oc($relations_r esult)){
if(!isset($list[$row['parent_id']]['childs']))
$list[$row['parent_id']]['childs'] = array();
$list[$row['parent_id']]['childs'][] =& $list[$row['child_id']];
}
function html_nested_lis ts($array, $safety = 0){
if($safety == 30){
trigger_error(' html_nested_lis ts: nesting to deep, 30 levels allowed');
return false;
}
$safety++;
if(!is_array($a rray) || empty($array)) return '';
$return = '<ul>';
foreach($array as $item){
$return .= '<li>'.$item['name'];
if(isset($item['childs'])) $return .=
html_nested_lis ts($item['childs'],$safety);
$return .= '</li>';
}
return $return;
}
echo html_nested_lis ts($list[0]['childs']);
?>
--
Rik Wasmus

**P Pulkkinen** · Feb 8 '07, 03:05 PM

Re: Menusystem!

"Jan Morten Sørensen" <jms@sensewave. comkirjoitti
viestissä:55adb $45cb2e90$54d23 962$12085@news. chello.no...

What then if I wanted to have multiple parents maybe even from different
tree levels?
(Is that possible with your solution?)
>
I wrote a solution to this last nite after posting this question and it
was
smashing. I am thinking about publishing it somewhere because I know
others
have the same problem as I do.

I don't get what you mean. Do you mean that a category would have many
parents, like in a real world we have both father and mother? And those
parents were from different "generation ".

Maybe I miss something of your point or original idea. But when i think word
"menu", I just think of a everlastingly classical system in web site or
application where you can access child through its parent, following the
path down to level that you want. (Although you just hover over parent names
with mouse, but anyway).

**Rik** · Feb 8 '07, 03:15 PM

Re: Menusystem!

P Pulkkinen <perttu.POISTAT AMA.pulkkinen@P OISTATAMA.elisa net.fiwrote:

>
"Jan Morten Sørensen" <jms@sensewave. comkirjoitti
viestissä:55adb $45cb2e90$54d23 962$12085@news. chello.no...
>

>What then if I wanted to have multiple parents maybe even from different
>tree levels?
>(Is that possible with your solution?)
>>
>I wrote a solution to this last nite after posting this question and it
>was
>smashing. I am thinking about publishing it somewhere because I know
>others
>have the same problem as I do.

>
I don't get what you mean. Do you mean that a category would have many
parents, like in a real world we have both father and mother? And those
parents were from different "generation ".

He means the data is not really a tree, just relations. An odd structure
for a menu, but possible.
--
Rik Wasmus

**Rik** · Feb 8 '07, 03:45 PM

Re: Menusystem!

Hmmmz, did some testing just in case... here's the debugged code, and man
can one get huge and weird structures if one's not carefull assigning
what's a child of what :-)

<?php
$list = array(0 =array('childs' =array()));
$list_result = mysql_query('SE LECT `id`, `name` FROM `category`');
while($row = mysql_fetch_ass oc($list_result )){
$list[intval($row['id'])] = $row;
}
$relations_resu lt = mysql_query('SE LECT `parent_id`, `child_id` FROM
`category_categ ories` ORDER BY `parent_id`');
while($row = mysql_fetch_ass oc($relations_r esult)){
if(!isset($list[$row['parent_id']]['childs']))
$list[$row['parent_id']]['childs'] = array();

$list[$row['parent_id']]['childs'][] =& $list[$row['child_id']];
}
function html_nested_lis ts($array, $safety = 0){
if($safety == 30){
trigger_error(' html_nested_lis ts: nesting to deep, 30 levels allowed');
return '';
}
$safety++;
if(!is_array($a rray) || empty($array)) return '';
$return = '<ul>';
foreach($array as $item){
$return .= '<li>'.$item['name'];
if(isset($item['childs'])) $return .=
html_nested_lis ts($item['childs'],$safety);
$return .= '</li>';
}
return $return;
}
echo html_nested_lis ts($list[0]['childs']);
?>
--
Rik Wasmus

**Jan Morten Sørensen** · Feb 8 '07, 03:55 PM

Re: Menusystem!

"Rik" <luiheidsgoeroe @hotmail.comskr ev i meddelandet
news:op.tnfquer kqnv3q9@misant. kabel.utwente.n l...

P Pulkkinen <perttu.POISTAT AMA.pulkkinen@P OISTATAMA.elisa net.fiwrote:
>

"Jan Morten Sørensen" <jms@sensewave. comkirjoitti
viestissä:55adb $45cb2e90$54d23 962$12085@news. chello.no...

What then if I wanted to have multiple parents maybe even from

different

tree levels?
(Is that possible with your solution?)
>
I wrote a solution to this last nite after posting this question and it
was
smashing. I am thinking about publishing it somewhere because I know
others
have the same problem as I do.

I don't get what you mean. Do you mean that a category would have many
parents, like in a real world we have both father and mother? And those
parents were from different "generation ".

>
He means the data is not really a tree, just relations. An odd structure
for a menu, but possible.

I'll put out an example menu for you!

main_category
---subcategory1
------subcategory2
---subcategory2
---subcategory3
main_category
---subcategory1
------subcategory2
---------subcategory3
main_category
main_category
etc...

as you can see the subcategories can be present in many variable levels and
have several parents and children...
I have solved this issue like this:

<?php
class MenuElement {
var $id;
var $text;
var $parents;
var $gotParents = false;
var $gotChildren = false;
var $children;
var $num_par = 0;
var $num_chi = 0;
var $level = '';

public function __construct($id , $text) {
$this->id = $id;
$this->text = $text;
}
public function isParent() {
return $this->gotChildren;
}
public function isChild() {
return $this->gotParents;
}
public function setParent($id) {
$this->parents[$this->num_par] = $id;
$this->num_par++;
}
public function loopChildren($e lement, &$list, &$k) {
for ($i=0;$i<count( $this->children);$i++ ) {
for ($j=0;$j<count( $element);$j++) {
if ($this->children[$i] == $element[$j]->getId()) {
if ($element[$j]->getLevel() == '')
$element[$j]->setLevel($th is->level+1);
$list[$k] = $element[$j];
$k++;
if ($this->gotChildren) {
$element[$j]->loopChildren($ element, $list, $k);
}
}
}
}
}
public function setChild($id) {
$this->children[$this->num_chi] = $id;
$this->num_chi++;
}
public function setParenthood($ gotParent) {
$this->gotParents = $gotParent;
}
public function setChildhood($g otChild) {
$this->gotChildren = $gotChild;
}
public function getId() {
return $this->id;
}
public function getLevel() {
return $this->level;
}
public function setLevel($level ) {
$this->level = $level;
}
public function getElementText( ) {
return $this->text;
}
}
// First fetch categories sorted.
$result = getCategories($ link, $language);
$result2 = getAllRelations hips($link, $language);
$i = 0;
// Then find main_categories
while ($row = mysql_fetch_ass oc($result)) {
$gotParents = false;
$gotChildren = false;
$element[$i] = new MenuElement($ro w['id'], $row['navn']);
if (mysql_num_rows ($result2) 0) {
mysql_data_seek ($result2, 0);
}
while ($row2 = mysql_fetch_ass oc($result2)) {
if ($row['id'] == $row2['childid']) {
if ($row2['parentid'] != 0) {
$gotParents = true;
$element[$i]->setParent($row 2['parentid']);
}
}
if ($row['id'] == $row2['parentid']) {
$gotChildren = true;
$element[$i]->setChild($ro w2['childid']);
}
}
$element[$i]->setParenthood( $gotParents);
$element[$i]->setChildhood($ gotChildren);
$i++;
}
$j = 0;
$k = 0;
while ($j < $i) {
if (!$element[$j]->isChild()) { // If main_category
$level = 0;
$element[$j]->setLevel($leve l);
$list[$k] = $element[$j];
$k++;
$element[$j]->loopChildren($ element, $list, $k);
}
$j++;
}
echo '<ul>';
for ($i = 0;$i < count($list);$i ++) {
echo '<li>' . str_repeat("--", $list[$i]->getLevel()) .
$list[$i]->getElementText ();
}
echo '</ul>';
?>

Now you end up with a list of all the elements in a sorted order and with
all variable data present. Only need for two mysql queries...

--
Jan Morten

http://www.sitconsulting.no

Billig datahjelp i Oslo området.

**Rik** · Feb 8 '07, 04:05 PM

Re: Menusystem!

Jan Morten Sørensen <jms@sensewave. comwrote:

I'll put out an example menu for you!
>
main_category
---subcategory1
------subcategory2
---subcategory2
---subcategory3
main_category
---subcategory1
------subcategory2
---------subcategory3
main_category
main_category

In the current setup wouldn't this mean:
main_category
---subcategory1
------subcategory2
--------subcategory3
---subcategory2
------subcategory3
---subcategory3
main_category
---subcategory1
------subcategory2
---------subcategory3

At least. if the number of subcategories stands for an id.
--
Rik Wasmus

**P Pulkkinen** · Feb 8 '07, 04:05 PM

Re: Menusystem!

Rik wrote:

He means the data is not really a tree, just relations. An odd
structure for a menu, but possible.

Okay. But if any kind of relationship is possible, I'd like to see the
visual representation of the menu.

By the way, this structure could work too imho, if the point was to have
tree, but be able to "recycle" same contents like "About us"-page.

Categories
=======
cat_id
cat_name
parent_id
content_id

Cat_contents
=========
content_id
content_blob

**Jan Morten Sørensen** · Feb 8 '07, 04:05 PM

Re: Menusystem!

"P Pulkkinen" <perttu.POISTAT AMA.pulkkinen@P OISTATAMA.elisa net.fiskrev i
meddelandet news:iJHyh.7870 $lw4.3113@reade r1.news.saunala hti.fi...

Rik wrote:
>

He means the data is not really a tree, just relations. An odd
structure for a menu, but possible.

>
Okay. But if any kind of relationship is possible, I'd like to see the
visual representation of the menu.
>
By the way, this structure could work too imho, if the point was to have
tree, but be able to "recycle" same contents like "About us"-page.
>

That was my idea yeah :) But my little code snippet fixed it for me ;)

Categories
=======
cat_id
cat_name
parent_id
content_id
>
Cat_contents
=========
content_id
content_blob
>
>
>

**Michael Fesser** · Feb 8 '07, 04:25 PM

Re: Menusystem!

..oO(Rik)

>P Pulkkinen <perttu.POISTAT AMA.pulkkinen@P OISTATAMA.elisa net.fiwrote:
>

>I don't get what you mean. Do you mean that a category would have many
>parents, like in a real world we have both father and mother? And those
>parents were from different "generation ".

>
>He means the data is not really a tree, just relations. An odd structure
>for a menu, but possible.

It's not that odd. On a shop site for example it could be possible to
reach a particular subcategory or product on different paths. There
might be cases where a simple tree is not enough.

For some examples here's an interesting paper (PDF) describing different
types of breadcrumbs:

Location, Path & Attribute Breadcrumbs

http://instone.org/breadcrumbs

Micha

**Toby A Inkster** · Feb 9 '07, 12:05 PM

Re: Menusystem!

Jan Morten SÃ¸rensen wrote:

Category
id(integer, autonumber)
name(text)
language(intege r)
>
Category_relati onships
id(integer, autonumber)
childid(integer )
parentid(intege r)
language(intege r)

Here's some example code using the PDO module (if you prefer a different
database module, you'll need to adapt the code). It is thoroughly
unchecked, so probably contains syntax errors. Maybe even logic errors,
but it ought to give you a good place to start.

Note that the structure you describe above allows for circular ancestries.
For example:

A parentof B && B parentof A
OR
A parentof B && B parentof C && C parentof A

I'll assume that you check for circular ancestries before adding a new
menu item, so the database contains no such loops.

<?php

define ('NODE_EXISTS', 1);
define ('NODE_IS_CHILD ', 2);
define ('NODE_IS_PAREN T', 4);

class MenuNode
{
public $id;
public $name;
public $lang;
public $children;

public function __construct($id , $name, $lang)
{
$this->id = $id;
$this->name = $name;
$this->lang = $lang;
$this->children = array();
}

public function make_link ()
{
return sprintf('<a href="menuselec t?id=%s" lang="%s">%s</a>'
, (int)$this->id
, htmlspecialchar s($this->lang)
, htmlspecialchar s($this->name)
);
}

public function menu_out ($indent='')
{
$retval = "$indent<li>\n" ;
$retval .= "$indent\t".$th is->make_link()."\ n";
if (count($this->children) 0)
{
$retval .= "$indent\t<ul>\ n";
foreach ($this->children as $C)
$retval .= $C->menu_out("$ind ent\t\t");
$retval .= "$indent\t</ul>\n";
}
$retval .= "$indent</li>\n";
return $retval;
}
}

function build_tree ($db)
{
$nodelist = array();
$links = array();
$statuses = array();

$q = 'SELECT c.id, c.name, c.language, r.parentid
FROM "Category" c
LEFT JOIN "Category_relat ionships" r ON c.id=r.childid; ';

foreach ($db->query($q) as $data_row)
{
list($I, $N, $L, $P) = $data_row;
$I = (int)$I;
$P = (int)$P; // nulls are now 0.
if (!isset($nodeli st[$I]))
$nodelist[$I] = new MenuNode($I, $N, $L);
if ($P>0)
$links[] = array($P, $I);
if (! ($statuses[$I] & NODE_EXISTS) )
$statuses[$I] += NODE_EXISTS;
}

// Database usage is finished here. Can close connection
// if you like.

if (isset($links[0]))
foreach ($links as $link)
{
list($P, $C) = $link;
$nodelist[$P]->children[] &= $C;
if (! ($statuses[$P] & NODE_IS_PARENT) )
$statuses[$P] += NODE_IS_PARENT;
if (! ($statuses[$C] & NODE_IS_CHILD) )
$statuses[$C] += NODE_IS_CHILD;
}

$top_level = array();
foreach ($statuses as $N=>$status)
{
if ( ($status&NODE_E XISTS) && !($status&NODE_ IS_CHILD) )
$top_level[] &= $nodelist[$N];
}

if (!isset($top_le vel[0]))
return FALSE;

if (count($top_lev el) == 1)
return $top_level[0];

$T = new Node(0, 'Home', 'en'); // default lang is 'en'.
foreach ($top_level as $C)
$T->children[] &= $C;
return $T;
}

$db = new PDO($dsn, $username, $password);
$tree = build_tree($db) ;
if ($tree !== FALSE)
print "<ul>\n".$t ree->menu_out("\t") ."</ul>\n";

?>

--
Toby A Inkster BSc (Hons) ARCS
Contact Me ~ http://tobyinkster.co.uk/contact
Geek of ~ HTML/CSS/Javascript/SQL/Perl/PHP/Python*/Apache/Linux

* = I'm getting there!

Menusystem!

Menusystem!

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment