More Web Proxy on the site http://driver.im/

column

Cardinality estimation for the optimization of queries on ontologies

Authors:

E. Patrick Shironoshita,

Michael T. Ryan,

Mansur R. KabukaAuthors Info & Claims

ACM SIGMOD Record, Volume 36, Issue 2

Pages 13 - 18

https://doi.org/10.1145/1328854.1328856

Published: 01 June 2007 Publication History

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]

Chauduri S. An Overview of Query Optimization in Relational Systems. Proc. of the 17^th ACM Symp on Principles of Database Systems, Seattle, WA, USA, 1998:34--43.

Digital Library

[2]

Chong El, Das S, Eadon G, Srinivasan J. An efficient SQL-based RDF querying scheme. Proc. of the 31st Intl. Conf. on Very Large Data Bases, Trondheim, Norway. 2005:1216--1227.

Digital Library

[3]

Frasincar F, Houben G-J, Vdovjak R, Barna P. RAL: An algebra for querying RDF. World Wide Web 2004;7(1):93--109.

Digital Library

[4]

Freire J, Haritsa JR, Ramanath M, Roy P, Siméon J. StatiX: Making XML Count. Proc. ACM SIGMOD, 2002 Jun 4-6, Madison, WI, USA.

Digital Library

[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]

Ives ZG, Halevy AY, Weld DS. Adapting to source properties in processing data integration queries. Proc ACM SIGMOD Intl Conf on Mgmt of Data. 2004:395--406.

Digital Library

[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]

Markl V, Raman V, Simmen D, Lohman G, Pirahesh H, Cilimdzic M. Robust query processing through progressive optimization. Proc ACM SIGMOD Intl Conf on Mgmt of Data. 2004:659--670.

Digital Library

[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]

Rodriguez MA, Egenhofer MJ. Determining Semantic Similarity among Entity Classes from Different Ontologies. IEEE Trans on Knowledge and Data Eng, 2003 15(2):442--456.

Digital Library

[13]

Sattler K-U, Geist I, Schallehn E. Concept-based querying in mediator systems. The VLDB Journal. 2005;14(1):97--111.

Digital Library

[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.

Digital Library

Cited By

Schwabe TAcosta M(2024)Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural NetworksProceedings of the ACM on Management of Data10.1145/36392992:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639299
Alipourlangouri MMansfield AChiang FWu Y(2023)Inconsistency Detection with Temporal Graph Functional Dependencies2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00042(464-476)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00042
Guzel Kalayci EKalayci TBirant D(2015)An ant colony optimisation approach for optimising SPARQL queries by reordering triple patternsInformation Systems10.1016/j.is.2015.01.01350:C(51-68)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1016/j.is.2015.01.013
Show More Cited By

Index Terms

Cardinality estimation for the optimization of queries on ontologies

Recommendations

ROSIE: Runtime Optimization of SPARQL Queries over RDF Using Incremental Evaluation
Knowledge Science, Engineering and Management
Abstract
RDF (Resource Description Framework) is a proposed standard for knowledge representation, with relational databases wildly adopted in RDF data management. For efficient evaluation of SPARQL queries over RDF data, the legacy query optimizer needs ...
Selectivity Estimation of Correlated Properties in RDF Data for SPARQL Query Optimization
SKG '09: Proceedings of the 2009 Fifth International Conference on Semantics, Knowledge and Grid

Nowadays mainstream RDF Repository Systems are based on RDBMS. The SPARQL query engine translates a SPARQL query into a SQL one, and then the RDBMS executes the SQL query. However the RDBMS optimizers, which usually assume that columns are statistically ...
FactorJoin: A New Cardinality Estimation Framework for Join Queries
PACMMOD

Cardinality estimation is one of the most fundamental and challenging problems in query optimization. Neither classical nor learning-based methods yield satisfactory performance when estimating the cardinality of the join queries. They either rely on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 36, Issue 2

June 2007

38 pages

ISSN:0163-5808

DOI:10.1145/1328854

Issue’s Table of Contents

Copyright © 2007 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2007

Published in SIGMOD Volume 36, Issue 2

Check for updates

Author Tags

Qualifiers

Column

Funding Sources

National Institutes of Health

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
330
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schwabe TAcosta M(2024)Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural NetworksProceedings of the ACM on Management of Data10.1145/36392992:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639299
Alipourlangouri MMansfield AChiang FWu Y(2023)Inconsistency Detection with Temporal Graph Functional Dependencies2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00042(464-476)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00042
Guzel Kalayci EKalayci TBirant D(2015)An ant colony optimisation approach for optimising SPARQL queries by reordering triple patternsInformation Systems10.1016/j.is.2015.01.01350:C(51-68)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1016/j.is.2015.01.013
Zhang WZhang K(2011)The comparison between histogram method and index method in selectivity estimationProceedings of the 7th international conference on Advanced Intelligent Computing Theories and Applications: with aspects of artificial intelligence10.1007/978-3-642-25944-9_46(357-362)Online publication date: 11-Aug-2011
https://dl.acm.org/doi/10.1007/978-3-642-25944-9_46
Kaoudi ZKyzirakos KKoubarakis M(2010)SPARQL query optimization on top of DHTsProceedings of the 9th international semantic web conference on The semantic web - Volume Part I10.5555/1940281.1940309(418-435)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/1940281.1940309
Kaoudi ZKyzirakos KKoubarakis M(2010)SPARQL Query Optimization on Top of DHTsThe Semantic Web – ISWC 201010.1007/978-3-642-17746-0_27(418-435)Online publication date: 2010
https://doi.org/10.1007/978-3-642-17746-0_27
DU XWANG YLÜ B(2009)Research and Development on Semantic Web Data ManagementJournal of Software10.3724/SP.J.1001.2009.0367820:11(2950-2964)Online publication date: 30-Nov-2009
https://doi.org/10.3724/SP.J.1001.2009.03678
Shironoshita EJean-Mary YBradley RKabuka M(2009)semQAIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2008.9121:3(401-414)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1109/TKDE.2008.91
Lv BDu XWang Y(2009)Selectivity Estimation of Correlated Properties in RDF Data for SPARQL Query OptimizationProceedings of the 2009 Fifth International Conference on Semantics, Knowledge and Grid10.1109/SKG.2009.49(176-183)Online publication date: 12-Oct-2009
https://dl.acm.org/doi/10.1109/SKG.2009.49

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents