MySQL & PHP - Creating Multiple Parent Child Relations

Question

Hi, I'm trying to build a navigation system using categories table with hierarchies. Normally, the table would be defined as follows:

id (int) - Primary key
name (varchar) - Name of the Category
parentid (int) - Parent ID of this Category referenced to same table (Self Join)

But the catch is that I require that a category can be child to multiple parent categories.. Just like a Has and Belongs to Many (HABTM) relation.

I know that if there are two tables, categories & items, we use a join table categories_items to list the HABTM relations. But here i'm not having two tables but only table but should somehow show HABTM relations to itself. Is this be possible using a single table? If yes, How? If not possible, what rules (table naming, fields) should I follow while creating the additional join table?

I'm trying to achieve this using CakePHP, If someone can provide CakePHP solution for this problem, that would be awesome. Even if that's not possible, any solution about creating join table is appreciated. Thanks for your time.

-- Edit -- My question seems to be a bit confusing, so I'm trying to restate what I'm looking for. In traditional self referenced (self join) parent-child relations, each item can have only one parent. What I'm looking for is to simulate a HABTM relation i.e. multiple parents for each item.

Categories & Items - To define HABTM, we use categories_items join table.

If within Categories I need HABTM, what should I do?

Answer 1

What you are trying to achieve isn't really a Cake way approach. You should be using two tables with a join table between. Cake's maxim is 'convention over configuration' so you should really use the standard cake way.

To create the HABTM, you'll be wanting three tables.

items
categories
categories_items

Item and Category are as you'd expect. Your join table should just contain the two id's of the joined tables as follows,

category_id
item_id

This will allow you to have one navigation item appear in multiple categories, should you so choose.

More info can be found in the book, http://book.cakephp.org/view/1044/hasAndBelongsToMany-HABTM

Answer 2

Trying to squeeze an n:m relationship (HABTM) into a 1:n relationship is not good practise and you'll run into limitations you wouldn't have if you did it cleanly, but this is how you could do it (generic PHP, not CakePHP-specific):

You can create a column in your table to store all parent IDs in a comma-separated list. You can read the individual IDs out by using...

$ids = explode(',', $idsFromColumn);

...and write them back into the column using...

$idsForColumn = implode(',', $ids);

Actual read-write of the database would happen before/after those snippets, respectively.

---

If you want to do it properly, you want you main table to look like this:

id (int) - Primary key
name (varchar) - Name of the Category

And your n:m relationship table to look like this:

id (int) - child
parentid (int) - parent

You would query it like this:

SELECT ...
FROM
    main_table AS m
    [LEFT OUTER|INNER]  JOIN
    relationship_table AS r
        ON r.id=m.id
    [LEFT OUTER|INNER] JOIN
    main_table AS n
        ON r.parentid=n.id
WHERE ...

Exactly what you want in you WHERE and your SELECT will be up to what you're hoping to achieve. As to whether you want LEFT OUTER JOIN or INNER JOIN, that depends on whether you want to return categories in m.* that do not have an entry in your relationship_table (= do not have any parent). If you're new to join syntax, take a look at this Wiki article on joins.

Answer 3

This is almost exactly what the the Tree behaviour is designed for. The behaviour is built on top of MPTT (Modified Preorder Tree Traversal). You would configure it thus:

Add the following fields to your table:

`parent_id` int(10) unsigned default NULL
`lft` int(10) unsigned default NULL
`rght` int(10) unsigned default NULL

Model:

class Category extends AppModel
{
    var $actsAs = array('Tree');
}

You'd then build a parent_id <select> into your category-modification forms, and the Tree behaviour would take care of the rest. I suppose you could handle manually the reordering of categories within a tier of your category hierarchy, but you're probably better off using the moveUp and moveDown methods available in models extended with the Tree behaviour.

Here, also, is a useful Tree Helper for converting the tree lists into ordered/unordered lists in your views.

Answer 4

I hope it isn't bad form to answer a second time, having misunderstood the question the first time. The following is essentially a CakePHP implementation of pinkgothic's answer.

New HABTM join table:

CREATE TABLE `categories_parent_categories` (
  `category_id` int(10) unsigned NOT NULL,
  `parent_category_id` int(10) unsigned default NULL,
  `order` int(10) unsigned NOT NULL default '0'
);

Association in model:

class Category extends AppModel
{
    var $hasAndBelongsToMany = array(
        'ParentCategory' => array(
            'className'             => 'Category',
            'joinTable'             => 'categories_parent_categories',
            'foreignKey'            => 'category_id',
            'associationForeignKey' => 'parent_category_id',
            'order'                 => 'CategoriesParentCategory.order'
        )
    );
}

Answer 5

Got it finally.

Naviitems Table:

CREATE TABLE IF NOT EXISTS `naviitems` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) NOT NULL,
  `linkurl` varchar(250) NOT NULL,
  PRIMARY KEY (`id`)
);

Self Join Table:

CREATE TABLE IF NOT EXISTS `naviitems_parents` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `naviitem_id` int(11) NOT NULL,
  `parent_id` int(11) NOT NULL,
  PRIMARY KEY (`id`)
);

Naviitems Model:

<?php
class Naviitem extends AppModel {

    var $name = 'Naviitem';

    //The Associations below have been created with all possible keys, those that are not needed can be removed
    var $hasAndBelongsToMany = array(
        'Parent' => array(
            'className' => 'Naviitem',
            'joinTable' => 'naviitems_parents',
            'foreignKey' => 'naviitem_id',
            'associationForeignKey' => 'parent_id',
            'unique' => true,
            'conditions' => '',
            'fields' => '',
            'order' => '',
            'limit' => '',
            'offset' => '',
            'finderQuery' => '',
            'deleteQuery' => '',
            'insertQuery' => ''
        )
    );
}
?>

I've generated the Controller and Views using Cake Bake shell. It's working fine now. Thanks for all the ideas you've contributed, they've helped me a lot.