Penilaian Kesamaan Entity Relationship Diagram dengan Algoritme Tree Edit Distance

Humasak Simanjuntak, Rosni Lumbantoruan, Wiwin Banjarnahor, Erisha Sitorus, Magdalena Panjaitan, Sintong Panjaitan


Main competency in database learning is ability to design Entity Relationship Diagram (ERD). Generally, lecturer gives task to students to design an ERD with some requirements. These ERDs are then assessed by comparing them with the answers. In practice, the process takes long time and it is possible that the lecturer grades the students inconsistently. Furthermore, plagiarism could be occured without being noticed by the lecturer. This research aims to design and build an application that assess similarity of ERD. The application apply tree edit distance algorithm in checking ERD similarity. ERD is exported into XMI document and then processed using the tree edit distance algorithm. The results show that ERD similarity value depends on number of insert, delete, and rename operation in tree edit distance Algorithm rather than number of difference component.

Full Text:



P. Thomas, K. Waugh, and N. Smith, “Generalized diagram revision tools with automatic marking”, ITiCSE '09 Proceedings of the 14th annual ACM SIGCSE conference on Innovation and technology in computer science education, 2009, p. 318–322.

H. Simanjuntak, “Proposed Framework for Automatic Entity Relationship Diagram Grading System”, ICITEE 2015 IEEE Proceedings of the 7th International Conference on information Technology and Electrical Engineering, 2015, p. 141-146.

H. Simanjuntak, D. hutajulu, E. manurung, and B. Hutagaol, “Similarity Assesment of UML Class Diagram Using Tree Edit Distance Algorithm”, Advanced Science Letters, vol. 21 no. 11, pp. 3577-3582, Nov. 2015.

(2015) W3C website. [Online]. Available:

H. Kaur, M. Kaur, “Detecting Clones in Class Diagrams Using Suffix Array”, International Journal of Engineering and Advanced Technology, vol. 3, pp. 243–246, April 2014.

J. Tekli, R. Chbeir, and K. Yetongnon, “An overview on XML similarity: background, current trends and future directions”, Elsevier Computer Science Review, vol. 3, pp. 151-173, August 2009.

(2016) ExamDiff Pro Website. [Online]. Available:

T. Akutsu, “Tree Edit Distance Problems: Algorithm and Applications to Bioinformatics”, IEICE Transactions on Information and Systems, vol. E93-D, pp. 208-218, February 2010.

K. Zhang, D. Shasha, “Simple fast algorithms for the editing distance between trees and related problems”, SIAM Journal on Computing, vol. 18, pp. 1245-1262, December 1989.

(2016) Tree Edit Distance Website. [Online]. Available:

H. Edelsbrunner, Z. Gu, “Design and Analysis of Algorithms”, Durham: Duke University, 2008.

J. Tekli, R. Chbeir, “A novel XML document structure comparison framework based-on sub-tree commonalities and label semantics”, Journal Web Semantics: Science, Services and Agents on the World Wide Web, vol. 11, pp. 14-40, March 2012.



  • There are currently no refbacks.

Copyright (c) 2017 Jurnal Nasional Teknik Elektro dan Teknologi Informasi (JNTETI)

JNTETI (Jurnal Nasional Teknik Elektro dan Teknologi Informasi)

Departemen Teknik Elektro dan Teknologi Informasi, Fakultas Teknik Universitas Gadjah Mada
Jl. Grafika No 2. Kampus UGM Yogyakarta 55281
+62 274 552305