All geek questions in one place

Response score for ER charts (entity)

I am working on a project to create an automated Entity Relationship Chart Assessment System. 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 the set of specified keywords, so that there is no problem.

- Secondly, for each element (entity / relationship) whose label corresponds to the labels in the response key, a local metric can be created. There may be several criteria in this metric, for example:

  • The correctness of neighboring elements.
  • The correctness of the type of entity.
  • Correctness of attributes.
  • The correctness of the types of edges. and etc.

- Each criterion can be assigned some weight, and an assessment can be performed.

It may seem plausible to do it this way?

It was also recommended that I consider the problem in terms of graph isomorphism . Since in my case the labels should match, so the problem is a bit simpler. In addition, I need a partial assistant and build a system for scoring over matches. I know that I spoke too abstractly, but I need some pointers, like where to start with this alternative view.

Thanks!

+4
source share
1 answer

Of course, your solution lies around the isomorphism of the graph. Indeed, you want to see if two graphs (actually ERD) are isomorphic or not. First of all, keep in mind that you are facing a very difficult problem:

" , NP, , , NP-: 12 , (1979), , ". (1)

, , :

. .
http://eccc.hpi-web.de/report/2012/078/download [+ , .]

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

0

Source: https://habr.com/ru/post/1526605/

More articles:


All Articles