Graph-Based Technique for Searching Structured Databases

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    This paper presents a graph-based technique for searching structured or relational databases using keyword queries in a similar wayto search text files using search engines. Our approach depends on identifying first the data within a database that are most likely to provide the useful result to the raised query and then search only the identified data. The proposed search algorithm uses an undirected weighted graph data structure for implementing the search process. To construct the graph, we introduced a modified function for computing edge weights which measure the connections among vertices in the graph. Experiments and the prototype implementation on real datasets prove that the proposed model is feasible and supports searching relational databases using keyword queries.


  • Keywords

    search, Relational Databases, Information Retrieval, Graph-Structured Data.

  • References

      [1] Agrawal S, Chaudhuri S & Das G, “DBXplorer: A System for Keyword-Based Search over Relational Databases”, in Proceedings of the 18th International Conference on Data Engineering, (2002), pp: 5-16.

      [2] Baid A, RaeI, Li J, Doan A & Naughton J, “Toward Scalable Keyword Search over Relational Data”, Proceedings of VLDB Endowment, Vol.3, No. 1-2, (2010), pp: 140-149.

      [3] D’zeroski S & Raedt L, “Multi-Relational Data Mining: a Workshop Report”, in Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-02), Vol. 4, No. 2, (2002), pp: 122-124.

      [4] Date C, an Introduction to Database Systems, Wesley, Publishing Company, 1994.

      [5] Dzeroskiand S & Lavrač N, Relational Data Mining, Springer-Verlag Berlin Heidelberg, 2001.

      [6] Feng J, Li G & Wang J, “Finding top-k answers in keyword search over relational databases using tuple units”, IEEE Trans Knowl Data Eng. Vol. 23, No.12, (2011), pp:1781-1794.

      [7] Goke A & Davies J, Information Retrieval: Searching in the 21st Century, John Wiley and Sons, (2009).

      [8] Hassan M, “Practical Free-Form Search over Relational Databases”, UACEE International Journal of Computer Science and its Applications, Vol. 2, No. 3, (2012), pp: 169-173.

      [9] He H, Wang H, Yang J & Yu P, “BLINKS: ranked keyword searches on graphs”, in Proceedings of SIGMOD 2007: ACM SIGMOD International Conference on Management of Data, (2007), pp: 305-316.

      [10] Hristidis V & Papakonstantinou Y, “Discover: keyword search in relational databases”, in Proceedings of the 28th international conference on Very Large Data Bases, (2002), pp: 670-681.

      [11] Hulgeri A, Nakhe C, Chakrabarti S & Sudarshan S, “Keyword searching and browsing in databases using BANKS”, in Proceedings of the 18th International Conference on Data Engineering,(2002), pp. 431-440.

      [12] Jia X, Hsu W & Lee M, “Target-Oriented Keyword Search over Temporal Databases”, in Proceedings of the 27th International Conference on Database and Expert Systems Applications, (2016), pp: 3-19.

      [13] Kanchan D & Paikrao R, “Survey paper on Generalized Inverted Index for Keyword Search”, International Journal of Engineering Research and Development, Vol. 10, No. 4, (2014) pp: 69-73.

      [14] Kargar M, An A, Cercone N, Godfrey P, Szlichta J & Yu X, “Meaningful Keyword Search in Relational Databases with Large and Complex Schema”, Proceedings of the IEEE 31st International Conference on Data Engineering ( ICDE), (2015), pp: 411-422.

      [15] Li G, Feng J. & Wang J, “Structure-aware indexing for keyword search in databases”, in Proceedings of ACM 18th International Conference on Information and Knowledge Management, (2009), pp. 1453-1456.

      [16] Manning C, Raghavan P & Schütze H, “Introduction to information retrieval”, Cambridge University press, 2008.

      [17] Mitha F, Herodotou H, Borisov N, Jiang C, Yoder J & Owzar K, “SNPpy-Database Management for SNP Data from Genome-Wide Association Studies”, PLOS ONE, 2011.

      [18] Neethu V & Rejimol R, “A Survey of Techniques For Answering Top-k Queries”, International Journal of Advances in Computer Science and Technology, Vol. 2, No. 2, (2013), pp: 7-13.

      [19] Su Q & Widom J, “Indexing relational database content offline for efficient keyword-based search”, in Proceedings of 9th International Database Engineering and Application Symposium, 2005, pp. 297-306.

      [20] Wang H & Aggarwal C, “A Survey of Algorithms for Keyword Search on Graph Data. Managing and Mining Graph Data. Advances in Database Systems“, Vol. 40. (2010), pp: 249-273.

      [21] Wang Y, Wang N & Zhou L, “Keyword Search in Large-Scale Databases with Topic Cluster Units”, Technical Gazette, Vol. 25, No. 3, pp: 748-758, June 2018.

      [22] Zeng J, Huang J & Yang S, “Top-k Keyword Search over Graphs Based On Backward Search”, in Proceedings of the 4th Annual International Conference on Information Technology and Applications (ITA), (2017), pp: 1-6.




Article ID: 27856
DOI: 10.14419/ijet.v7i4.16.27856

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.