MySQL Recursive Query (kind of) help to determine tech tree prerequisites

Question

I'm trying to figure out how to do what I can only call a recursive query (my knowledge of MySQL is extremely limited). The game I'm designing has a tech tree with items to research that will grant you stronger stuff down the line. The prerequisites are broken down in another table, since each tech item can have 0 or more prereqs.

CREATE  TABLE IF NOT EXISTS `tech` (
  `id` INT NOT NULL ,
  `name` VARCHAR(45) NULL DEFAULT NULL ,
  PRIMARY KEY (`id`) );
CREATE  TABLE IF NOT EXISTS `prereq` (
  `src_id` INT NOT NULL ,
  `prereq_id` INT NOT NULL );
INSERT INTO tech (`id`,`name`) VALUES(1001, 'Logic');
INSERT INTO tech (`id`,`name`) VALUES(1002, 'Classical Physics');
INSERT INTO tech (`id`,`name`) VALUES(1005, 'Global Economics');
INSERT INTO tech (`id`,`name`) VALUES(1008, 'Solar Power Collector');
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1008,1005);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1005,1001);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1005,1002);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1001,NULL);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1002,NULL);

With this set up, I can query the tables and find that if I want solar power, I need to first research Global Economics:

SELECT t.name, t.id, GROUP_CONCAT(p.prereq_id ORDER BY p.prereq_id ASC)
FROM tech t LEFT JOIN prereq p on t.id=p.src_id
WHERE t.id=1008
GROUP BY t.name, t.id
ORDER BY t.id

What I'm trying to get at is a result set that include the next level of prerequisites, then the next, until we hit nodes that have NULL. So I'm looking for this:

id     name
1008   Solar Power Collector
1005   Global Economics
1001   Logic
1002   Classical Physics

Is this even possible within MySQL? I tried to use a cursor, but was unsuccessful. I could handle this within the actual code, but I'd rather it be done server side somehow.

Any help in pointing me in the right direction would be greatly appreciated!

Answer 1

In postgreSQL or MS SQL Server, you'd use a recursive CTE for this.

Since MySQL doesn't support recursive CTEs, you'll have to change the structure of your table to use nested sets, or you could use as many self-joins as the depth of your tech tree. See this article http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/ for how to do it.

However, there are quite a few drawbacks to doing this kind of operation in MySQL (nested sets are really slow to insert into, the Spatial index requires a table-lock), so you should consider calculating the depencies outside of MySQL if at all possible.

Answer 2

Seeing the discussion in comments, I guess I'd better put my recommendations as an answer.

See, I've used relational databases for all kinds of static data in the past. And it always lead to shenanigans like these. This question or this one have to deal with this too.

Relational databases are really quite inflexible in terms of data representation. Usually, you trade this flexibility for efficient storage and, first and foremost, efficient querying of large datasets.

Static game data is almost always very small, and fits easily in memory. And you very rarely need to query it in the way databases support. 99% of the time you just need the "give me object with this Id" request, and using RDBMS for it is overkill. 1% of the time, you have some crazy recursive query that becomes needlessly complex and slow, and an ugly hack.

On the other hand, static data tends to have complex schemata, lots of optional values, tree-like structure, etc. This is hard to represent efficiently in a database. Changing a database schema is also a pain usually. Lastly, you cannot put your database under source control - and you WANT your static data under source control.

So in the end, database does not give you any advantages. A better way is to store everything in config files: XML, JSON, YAML - anything goes, if you have/can develop a good library to work with the format. Config files can be put under source control, can be easily extended, and are not bound by a rigid schema. With some libs, like LINQ2XML, you can even run queries against them, just like with a DB. Config files are also human-readable and human-editable, which might come in handy. Of course, at runtime these files are read, parsed and stored in memory, using whatever data structure you want (and a simple hash table will be a billion times faster than a database query). Then your server works with this in-memory representation.

The only time when you can't do that is when you don't actually have a server, and your clients call DB directly. But then you have much, much worse problems than this (-8

Answer 3

Relational databases aren't suited to tree representations for precisely this reason. I advise you to just do this iteratively, in whatever code is using this SQL.

Note that you also have to specify how you want to traverse the tree, which isn't clear from your question. Your example has an ambiguous ordering as there either Logic or Classical Physics could go last - this will matter more when you have a bigger tree, and some of the nodes with no prerequisites might exist at different levels - should they all appear at the bottom, or should they appear some way through the structure depending on which options they make available?

Although, I second Nevermind's comment about this being the wrong data storage approach for static data. An in-memory structure would be faster and easier to process.