Article

Types for path correctness of XML queries

Authors:

Giorgio Ghelli,

Carlo SartianiAuthors Info & Claims

ICFP '04: Proceedings of the ninth ACM SIGPLAN international conference on Functional programming

Pages 126 - 137

https://doi.org/10.1145/1016850.1016869

Published: 19 September 2004 Publication History

Abstract

If a subexpression in a query will never contribute data to the query answer, this should be regarded as an error. This principle has been recently accepted into mainstream XML query languages, but was still waiting for a complete treatment. We provide here a precise definition for this class of errors, and define a type system that is sound and complete, in its search for such errors, for a core language, under mild restrictions on the use of recursion in type definitions. In the process, we describe a dichotomy among existential and universal type systems, which is useful to understand some unusual features of our type system.

References

[1]

S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel Query Language for Semistuctured Data. Journal of Digital Libraries, 1(1), pages 68--88, April 1997.

[2]

N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. Type-checking XML Views of Relational Databases. In Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 16-19 June 2001, Boston, Massachusetts, USA, Proceedings. IEEE Computer Society, 2001, pages 421--430, 2001.

Digital Library

[3]

N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. XML with Data Values: Typechecking Revisited. In Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 21-23, 2001, Santa Barbara, California, USA, 2001.

Digital Library

[4]

V. Benzaken, G. Castagna, and A. Frisch. CDuce: an XML-centric general-purpose language. In Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, pages 51--63. ACM Press, 2003.

Digital Library

[5]

V. Benzaken, G. Castagna, and C. Miachon. CQL: a Pattern-based Query Language for XML. In Proceedings of 20th Bases de Données Avancées (BDA) (2004), 2004.

[6]

S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu, J. Robie, and J. Siméon. XQuery 1.0: An XML Query Language. Technical report, World Wide Web Consortium, May 2003. W3C Working Draft.

[7]

P. Buneman, S. Davidson, and D. Suciu. Programming constructs for unstructured data. In Proceedings of 5th International Workshop on Database Programming Languages, Gubbio, Italy, September 1995.

Digital Library

[8]

D. Chamberlin, P. Fankhauser, D. Florescu, M. Marchiori, and J. Robie. XML Query Use Cases. Technical report, World Wide Web Consortium, Nov 2003. W3C Working Draft.

[9]

D. Colazzo. Path Correctness for XML Queries: Characterization and Static Type Checking. PhD thesis, Dipartimento di Informatica, Università di Pisa, 2004.

[10]

D. Colazzo, G. Ghelli, P. Manghi, and C. Sartiani. Types For Correctness of Queries Over Semistructured Data. In Proceedings of the Fifth International Workshop on the Web and Databases (WebDB 2002), Madison, Wisconsin, June 6-7, 2002, 2002.

[11]

H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree Automata Techniques and Applications. Available on: http://www.grappa.univ-lille3.fr/tata, 1997. release October, 1rst 2002.

[12]

D. Draper, P. Fankhauser, M. Fernandez, A. Malhotra, K. Rose, M. Rys, J. Siméon, and P. Wadler. XQuery 1.0 and XPath 2.0 Formal Semantics. Technical report, World Wide Web Consortium, Aug. 2003. W3C Working Draft.

[13]

M. Fernandez, D. Florescu, A. Levy, and D. Suciu. A query language for a Web-site management system. SIG-MOD Record (ACM Special Interest Group on Management of Data), 26(3):4--11, September 1997.

Digital Library

[14]

H. Hosoya and B. C. Pierce. XDuce: An XML Processing Language, 1999. Preliminary Report.

[15]

D. Lee, M. Mani, and M. Murata. Reasoning about XML Schema Languages using Formal Language Theory. Technical report, IBM Almaden Research, 2000. Technical Report -IBM Almaden Research.

[16]

T. Milo, D. Suciu, and V. Vianu. Typechecking for XML Transformers. In Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 11--22. ACM Press, 2000.

Digital Library

[17]

H. S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML Schema Part 1: Structures. Technical report, World Wide Web Consortium, May 2002. W3C Recommendation.

[18]

F. Yergeau, T. Bray, J. Paoli, C. M. Sperberg-McQueen, and E. Maler. Extensible Markup Language (XML) 1.0 (Third Edition). Technical report, World Wide Web Consortium, Feb 2004. W3C Recommendation.

Cited By

Flint SKeshk ADyer RBagheri H(2025)How do developers use type inference: an exploratory study in KotlinEmpirical Software Engineering10.1007/s10664-024-10585-y30:2Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10664-024-10585-y
Genevès PGesbert N(2015)XQuery and static typing: tackling the problem of backward axesACM SIGPLAN Notices10.1145/2858949.278474650:9(88-100)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2858949.2784746
Genevès PGesbert NFisher KReppy J(2015)XQuery and static typing: tackling the problem of backward axesProceedings of the 20th ACM SIGPLAN International Conference on Functional Programming10.1145/2784731.2784746(88-100)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2784731.2784746
Show More Cited By

Index Terms

Types for path correctness of XML queries
1. Information systems
  1. Data management systems
    1. Query languages

Recommendations

Types for path correctness of XML queries
ICFP '04

If a subexpression in a query will never contribute data to the query answer, this should be regarded as an error. This principle has been recently accepted into mainstream XML query languages, but was still waiting for a complete treatment. We provide ...
Towards a comprehensive assessment for selectivity estimation approaches of XML queries

Estimating the sizes of query results and intermediate results is a crucial part of any effective query optimisation process. Due to several reasons, the selectivity estimation problem in the XML domain is more complicated than that in the relational ...
Static analysis for path correctness of XML queries

A part of a query that will never contribute data to the query answer should be regarded as an error. This principle has been recently accepted into mainstream XML query languages, but was still waiting for a complete treatment. We provide here a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '04: Proceedings of the ninth ACM SIGPLAN international conference on Functional programming

September 2004

264 pages

ISBN:1581139055

DOI:10.1145/1016850

General Chair:
Chris Okasaki
United States Military Academy, West Point
,
Program Chair:
Kathleen Fisher
AT&T Labs Research

ACM SIGPLAN Notices Volume 39, Issue 9
ICFP '04
September 2004
254 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1016848
Issue’s Table of Contents

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 September 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICFP04

Sponsor:

ICFP04: ACM SIGPLAN International Conference on Functional Programming

September 19 - 21, 2004

UT, Snow Bird, USA

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
305
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Flint SKeshk ADyer RBagheri H(2025)How do developers use type inference: an exploratory study in KotlinEmpirical Software Engineering10.1007/s10664-024-10585-y30:2Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10664-024-10585-y
Genevès PGesbert N(2015)XQuery and static typing: tackling the problem of backward axesACM SIGPLAN Notices10.1145/2858949.278474650:9(88-100)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2858949.2784746
Genevès PGesbert NFisher KReppy J(2015)XQuery and static typing: tackling the problem of backward axesProceedings of the 20th ACM SIGPLAN International Conference on Functional Programming10.1145/2784731.2784746(88-100)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2784731.2784746
Colazzo DSartiani CSchneider-Kamp PHanus M(2011)Precision and complexity of XQuery type inferenceProceedings of the 13th international ACM SIGPLAN symposium on Principles and practices of declarative programming10.1145/2003476.2003490(89-100)Online publication date: 20-Jul-2011
https://dl.acm.org/doi/10.1145/2003476.2003490
Genevès PLayaïda NQuint V(2011)Impact of XML Schema EvolutionACM Transactions on Internet Technology10.1145/1993083.199308711:1(1-27)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1145/1993083.1993087
Zinn DBowers SLudascher B(2010)XML-based computation for scientific workflows2010 IEEE 26th International Conference on Data Engineering (ICDE 2010)10.1109/ICDE.2010.5447884(812-815)Online publication date: Mar-2010
https://doi.org/10.1109/ICDE.2010.5447884
Genevès PLayaïda NQuint V(2009)Identifying query incompatibilities with evolving XML schemasACM SIGPLAN Notices10.1145/1631687.159658344:9(221-230)Online publication date: 31-Aug-2009
https://dl.acm.org/doi/10.1145/1631687.1596583
Genevès PLayaïda NQuint VHutton GTolmach A(2009)Identifying query incompatibilities with evolving XML schemasProceedings of the 14th ACM SIGPLAN international conference on Functional programming10.1145/1596550.1596583(221-230)Online publication date: 31-Aug-2009
https://dl.acm.org/doi/10.1145/1596550.1596583
Colazzo DSartiani C(2009)Detection of corrupted schema mappings in XML data integration systemsACM Transactions on Internet Technology (TOIT)10.1145/1592446.15924489:4(1-53)Online publication date: 14-Oct-2009
https://dl.acm.org/doi/10.1145/1592446.1592448
Lämmel RHofmann MFelleisen M(2007)Scrap your boilerplate with XPath-like combinatorsProceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1190216.1190240(137-142)Online publication date: 17-Jan-2007
https://dl.acm.org/doi/10.1145/1190216.1190240
Show More Cited By

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 Table of Conten