Cardinality estimation for the optimization of queries on ontologies

ABSTRACT

An effective, accurate algorithm for cardinality estimation of queries on ontology models of data is presented. The algorithm relies on the decomposition of queries into query pattern paths, where each path produces a set of values for each variable within the result form of the query. In order to estimate the total number of result set parameters for each path, a set of statistics is compiled on the properties of the ontology. Experimental analysis has shown that the algorithm produces estimates with high accuracy and with high correlation to actual values. Thus, this algorithm can be used as the cornerstone of an effective optimization strategy for queries on diverse, heterogeneous data sources modeled as ontologies.

REFERENCES

• 1: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 2: Eugene Inseok Chong , Souripriya Das , George Eadon , Jagannathan Srinivasan, An efficient SQL-based RDF querying scheme, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Flavius Frasincar , Geert-Jan Houben , Richard Vdovjak , Peter Barna, RAL: An Algebra for Querying RDF, World Wide Web, v.7 n.1, p.83-109, March 2004 [doi>10.1023/B:WWWJ.0000015866.43076.06]
• 4: Juliana Freire , Jayant R. Haritsa , Maya Ramanath , Prasan Roy , Jérôme Siméon, StatiX: making XML count, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564713]
• 5: Gruber TR. Toward principles for the design of ontologies used for knowledge sharing. Technical report KSL 93-04, Knowledge Systems Laboratory, Stanford University, Available from: ftp.ksl.stanford.edu/pub/KSL_Reports/KSL-93-04.ps.gz.
• 6: Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Adapting to source properties in processing data integration queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007613]
• 7: Kohler J, Philippi S, Lange M. SEMEDA: ontology based semantic integration of biological databases. Bioinformatics. 2003 Dec 12;19(18):2420--2427.
• 8: Manola F, Miller E, editors. RDF Primer. W3C Recommendation {updated 2004 Feb 10, accessed 2006 Mar 21}. Available from: http://www.w3.org/TR/rdf-primer/.
• 9: Volker Markl , Vijayshankar Raman , David Simmen , Guy Lohman , Hamid Pirahesh , Miso Cilimdzic, Robust query processing through progressive optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007642]
• 10: Pérez de Laborda C, Conrad S. Querying Relational Databases with RDQL. Berliner XML Tage 2005. {Accessed 2006 Mar 21}. Available from: http://dbs.cs.uniduesseldorf.de/~perezdel/pdf/05PeCob.pdf.
• 11: Prud'hommeaux E, Seaborne A, editors. SPARQL Query Language for RDF, W3C Working Draft {updated 2007 Mar 26, accessed 2007 Jun 11}. Available from: http://www.w3.org/TR/rdf-sparql-query/.
• 12: M. Andrea Rodríguez , Max J. Egenhofer, Determining Semantic Similarity among Entity Classes from Different Ontologies, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.442-456, February 2003 [doi>10.1109/TKDE.2003.1185844]
• 13: Kai-Uwe Sattler , Ingolf Geist , Eike Schallehn, Concept-based querying in mediator systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.1, p.97-111, March 2005 [doi>10.1007/s00778-003-0118-9]
• 14: Smith MK, Welty C, McGuiness DL editors. OWL Web Ontology Language Guide, W3C Recommendation {updated 2004 Feb 10, accessed 2006 Mar 21}. Available from: http://www.w3.org/TR/owl-guide/.
• 15: Taylor TJ, Kabuka MR, Shironoshita EP, Ryan MT, Younis AA, John, NM, et.al. Viability of Mental Health Assessment Software in Diverse Settings. 45th Annual NCDEU (New Clinical Drug Evaluation Unit), Boca Raton, FL, USA. June 6--9, 2005.
• 16: Wu Y, Patel JM, Jagadish HV. Structural Join Order Selection for XML Query Optimization. Proc. of the 19th Intl Conf on Data Engineering. 2003 Mar 5-8: 443--454.
• 17: Zhang N, Ozsu MT, Aboulnaga A, Ilyas IF. XSeed: accurate and fast cardinality estimation for XPath queries. {Accessed 2006 Mar 21}. Available from: http://www.cs.uwaterloo.ca/~ilyas/papers/synopsis.pdf.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Semantic networks; Representations (procedural and rule-based)

General Terms:
Algorithms, Performance, Standardization

Keywords:
OWL, SPARQL, cardinality estimation, ontology, query optimization, semantic query