Abstract
Graphs have become increasingly used for modelling complicated data such as: chemical compounds, protein interactions and social networks. Retrieving related graphs containing a query graph from a large graph database is a fundamental performance issue in any graph-based application. Relational database management systems (RDBMSs) have repeatedly shown their success and efficiency in hosting types of data which have formerly not been anticipated to live inside relational databases such as: complex objects and XML data. The big advantages of relational database systems are its well-known maturity and its high scalability to handle vast amounts of data very efficiently. In this paper, we investigate the efficiency of different proposed schemes for storing and querying various kind of graphs using the relational infrastructure. Moreover, we investigate how existing relational query optimization techniques could be effectively utilized to improve the processing times of relational-based processing of graph queries. Finally, we have qualitatively evaluated our proposed approaches using an extensive set of experiments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
DBLP XML Records, http://dblp.uni-trier.de/xml/
Aboulnaga, A., Alameldeen, A., Naughton, J.: Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. In: VLDB (2001)
Zhang, S., et al.: TreePi: A Novel Graph Indexing Method. In: ICDE (2007)
Cai, D., Shao, Z., He, X., Yan, X., Han, J.: Community Mining from Multi-relational Networks. In: Jorge, A.M., Torgo, L., Brazdil, P.B., Camacho, R., Gama, J. (eds.) PKDD 2005. LNCS (LNAI), vol. 3721, pp. 445–452. Springer, Heidelberg (2005)
Huan, J., et al.: Mining protein family specific residue packing patterns from protein structure graphs. In: Computational Molecular Biology (2004)
Yoshikawa, M., et al.: XRel: a path-based approach to storage and retrieval of XML documents using relational databases. TOIT 1(1) (2001)
Zhao, P., et al.: Graph indexing: tree + delta = graph. In: VLDB (2007)
Cohen, S., et al.: Scientific formats for object-relational database systems: a study of suitability and performance. SIGMOD Record 35(2) (2006)
Botea, V., et al.: PIST: An Efficient and Practical Indexing Technique for Historical Spatio-Temporal Point Data. GeoInformatica 12(2) (2008)
Giugno, R., Shasha, D.: GraphGrep: A Fast and Universal Method for Querying Graphs. In: International Conference in Pattern recognition (2002)
Graefe, G.: Sorting And Indexing With Partitioned B-Trees. In: CIDR (2003)
Grust, T., Rittinger, J., Teubner, J.: Why Off-The-Shelf RDBMSs are Better at XPath Than You Might Expect. In: SIGMOD (2007)
Grust, T., Sakr, S., Teubner, J.: XQuery on SQL Hosts. In: VLDB (2004)
Klinger, S., Austin, J.: Chemical similarity searching using a neural graph matcher. In: European Symposium on Artificial Neural Networks (2005)
Yan, X., Yu, P., Han, J.: Graph indexing: a frequent structure-based approach. In: SIGMOD (2004)
Zhang, N., Özsu, T., Ilyas, I., Aboulnaga, A.: FIX: Feature-based Indexing Technique for XML Documents. In: VLDB (2006)
Zou, L., Chen, L., Xu Yu, J., Lu, Y.: GString: A novel spectral coding in a large graph database. In: EDBT (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sakr, S. (2009). Storing and Querying Graph Data Using Efficient Relational Processing Techniques. In: Yang, J., Ginige, A., Mayr, H.C., Kutsche, RD. (eds) Information Systems: Modeling, Development, and Integration. UNISCON 2009. Lecture Notes in Business Information Processing, vol 20. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01112-2_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-01112-2_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01111-5
Online ISBN: 978-3-642-01112-2
eBook Packages: Computer ScienceComputer Science (R0)