Abstract
Web queries have been and will remain an essential tool for accessing, processing, and, ultimately, reasoning with data on the Web. With the vast data size on the Web and Semantic Web, reducing costs of data transfer and query evaluation for Web queries is crucial. To reduce costs, it is necessary to narrow the data candidates to query, simplify complex queries and reduce intermediate results.
This article describes a static approach to optimization of web queries. We introduce a set of rules which achieves the desired optimization by schema and type based query rewriting. The approach consists in using schema information for removing incompleteness (as expressed by ‘descendant’ constructs and disjunctions) from queries. The approach is presented on the query language Xcerpt, though applicable to other query languages like XQuery. The approach is an application of rules in many aspects—query rules are optimized using rewriting rules based on schema or type information specified in grammar rules.
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
Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann Publishers Inc. San Francisco (2000)
Berger, S.: An Automaton Model for Xcerpt Type Checking and XML Schema Validation. REWERSE-TR-2007-01, Inst. for Computer Science, Univ. of Munich, Germany (2007)
Berger, S., Bry, F.: Towards Static Type Checking of Web Query Language. In: Proc. Workshop über Grundlagen von Datenbanken (GvD) (2005)
Berger, S., Coquery, E., Drabent, W., Wilk, A.: Descriptive Typing Rules for Xcerpt. In: PPSWR 2005. LNCS, vol. 3703, Springer, Heidelberg (2005)
Boncz, P., Grust, T., van Keulen, M., Manegold, S., Rittinger, J., Teubner, J.: MonetDB/XQuery: a fast XQuery Processor powered by a Relational Engine. In: SIGMOD (2006)
Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets. HKUST-TCSC-2001-0, Hongkong Univ. of Science and Tech. (2001)
Bry, F., Schaffert, S.: Towards a Declarative Query and Transformation Language for XML and Semistructured Data: Simulation Unification. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol. 2401, Springer, Heidelberg (2002)
Chamberlin, D., Frankhauser, P., Florescu, D., Marchiori, M., Robie, J.: XML Query Use Cases. Working draft, W3C (2005)
Che, D., Aberer, K., Özsu, T.: Query Optimization in XML Structured-document Databases. The VLDB Journal 15(3), 263–289 (2006)
Common, H., Dauchet, M., Gilleron, R., Lugiez, F.J.D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1999), http://www.grappa.univ-lille3.fr/tata
Fernandez, M.F., Suciu, D.: Optimizing Regular Path Expressions Using Graph Schemas. In: Proc. Int’l. Conf. on Data Engineering (ICDE) (1998)
Koch, C.: On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values. In: Proc. ACM Symp. on Principles of Database Sys. (PODS) (2005)
Olteanu, D.: SPEX: Streamed and Progressive Evaluation of XPath. IEEE Transactions on Knowledge and Data Engineering (2007)
Olteanu, D., Meuss, H., Furche, T., Bry, F.: XPath: Looking Forward. In: Chaudhri, A.B., Unland, R., Djeraba, C., Lindner, W. (eds.) EDBT 2002. LNCS, vol. 2490, Springer, Heidelberg (2002)
Schaffert, S., Bry, F.: Querying the Web Reconsidered: A Practical Introduction to Xcerpt. In: Proc. Extreme Markup Languages (2004)
Schwentick, T.: XPath Query Containment. SIGMOD Record 33(1), 101–109 (2004)
Su, H., Rundensteiner, E.A., Mani, M.: Semantic Query Optimization for XQuery over XML Streams. In: Proc. Int’l. Conf. on Very Large Data Bases (VLDB) (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Berger, S., Bry, F., Furche, T., Häusler, A.J. (2007). Completing Queries: Rewriting of Incomplete Web Queries Under Schema Constraints. In: Marchiori, M., Pan, J.Z., Marie, C.d.S. (eds) Web Reasoning and Rule Systems. RR 2007. Lecture Notes in Computer Science, vol 4524. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72982-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-72982-2_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72981-5
Online ISBN: 978-3-540-72982-2
eBook Packages: Computer ScienceComputer Science (R0)