Question

I am working on a project to create an automated evaluation system for Entity Relationship diagrams. Now I came up with an abstract matching algorithm.

--First of all for all the labels in the diagram, they can be selected only from a set of given keywords so that's not a problem.

--Second of all, for each element(entity/relationship) whose label matches the labels in the answer key a local metric can be created. There can be some a few criteria in this metric like:

  • Correctness of adjacent elements.
  • Correctness of entity type.
  • Correctness of attributes.
  • Correctness of edge types. etc.

--Each criteria can be assigned some weight and evaluation can be done.

Does it seem plausible to do it in this way?

Also I have been advised to view the problem in terms of graph isomorphism instead. Since in my case labels have to matched so the problem is bit simpler than that. Also I need a partial matcher and build a scoring system on top of the matcher. I know I have talked way too abstractly, but I need some pointers as in where to start with this alternative view.

Thank you!!

No correct solution

OTHER TIPS

For sure your solution is around the graph isomorphism. Indeed you want to see whether two graphs (ERDs in fact) are isomorphic or not. First of all please keep in mind that you are facing a really hard problem:

"it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete: it is one of only 12 such problems listed by Garey & Johnson (1979), and one of only two of that list whose complexity remains unresolved."(1)

As you are working on a project so run time is of big concern for you so I recommend you to implement an approximate algorithm and specially read this paper:

Approximate Graph Isomorphism by V. Arvind et al.
http://eccc.hpi-web.de/report/2012/078/download [+ please consider the copy right if exists.]


(1): http://en.wikipedia.org/wiki/Graph_isomorphism_problem

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top