Pathing in a non-geographic environment

Question

For a school project, I need to create a way to create personnalized queries based on end-user choices.
Since the user can choose basically any fields from any combination of tables, I need to find a way to map the tables in order to make a join and not have extraneous data (This may lead to incoherent reports, but we're willing to live with that).

For up to two tables, I already managed to design an algorithm that works fine. However, when I add another table, I can't find a way to path through my database. All tables available for the personnalized reports can be linked together so it really all falls down to finding which path to use.

Answer 1

You might be able to try some form of an A* algorithm. Basically this looks at each of the possible next options to choose and applies a heuristic to it, a function that determines roughly how far it is between this node and your goal. It then chooses the one that is closer and repeats. The hardest part of implementing A* is designing a good heuristic.

Without more information on how the tables fit together, or what you mean by a 'path' through the tables, it's hard to recommend something though.

Looks like it didn't like my link, probably the * in it, try:

http://en.wikipedia.org/wiki/A*_search_algorithm

Edit: If that is the whole database, I'd go with a depth-first exhaustive search.

Answer 2

I thought about using A* or a similar algorithm, but as you said, the hardest part is about designing the heuristic.

My tables are centered around somewhat of a backbone with quite a few branches each leading to at most a single leaf node. Here is the actual map (table names removed because I'm paranoid). Assuming I want to view data from tha A, B and C tables, I need an algorithm to find the blue path.