skip to main content
10.1145/1376916.1376951acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
research-article

XPath evaluation in linear time

Published: 09 June 2008 Publication History

Abstract

We consider a fragment of XPath where attribute values can only be tested for equality. We show that for any fixed unary query in this fragment, the set of nodes that satisfy the query can be calculated in time linear in the document size.

References

[1]
M. Bojańczyk, C. David, A. Muscholl, T. Schwentick, and L. Segoufin. Two-variable logic on data trees and XML reasoning. In Principles of Database Systems, pages 10 -- 19, 2006.
[2]
T. Colcombet. A combinatorial theorem for trees. In ICALP'07, Lecture Notes in Computer Science. Springer-Verlag, 2007.
[3]
T. Colcombet. Factorisation forests for infinite words. In FCT'07, 2007.
[4]
T. Colcombet. On Factorization Forests. Technical Report hal-00125047, Irisa Rennes, 2007.
[5]
R. Pichler G. Gottlob, C. Koch. Xpath query evaluation: Improving time and space efficiency. In ICDE'03, pages 379--390, 2003.
[6]
R. Pichler G. Gottlob, C. Koch. Efficient algorithms for processing XPath queries. ACM Transactions on Database Systems, 30(2):444--491, 2005.
[7]
C. Koch M. Benedikt. XPath leashed. ACM Computing Surveys.
[8]
F. Neven. Automata theory for XML researchers. SIGMOD Record, 31(3), 2002.
[9]
I. Simon. Factorization forests of finite height. Theoretical Computer Science, 72:65 -- 94, 1990.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2008
330 pages
ISBN:9781605581521
DOI:10.1145/1376916
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: 09 June 2008

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

SIGMOD/PODS '08
Sponsor:

Acceptance Rates

PODS '08 Paper Acceptance Rate 28 of 159 submissions, 18%;
Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)Deciding Twig-definability of Node Selecting Tree AutomataTheory of Computing Systems10.1007/s00224-015-9623-757:4(967-1007)Online publication date: 1-Nov-2015
  • (2013)XPath fragments on XML in columnsInternational Journal of Web Information Systems10.1108/IJWIS-05-2013-00179:4(317-329)Online publication date: 18-Nov-2013
  • (2012)XPath fragments on XML in columnsProceedings of the 14th International Conference on Information Integration and Web-based Applications & Services10.1145/2428736.2428790(307-310)Online publication date: 3-Dec-2012
  • (2012)Regular path queries on graphs with dataProceedings of the 15th International Conference on Database Theory10.1145/2274576.2274585(74-85)Online publication date: 26-Mar-2012
  • (2012)Regular expressions for data wordsProceedings of the 18th international conference on Logic for Programming, Artificial Intelligence, and Reasoning10.1007/978-3-642-28717-6_22(274-288)Online publication date: 11-Mar-2012
  • (2012)Foundations of XML based on logic and automataProceedings of the 7th international conference on Foundations of Information and Knowledge Systems10.1007/978-3-642-28472-4_2(23-33)Online publication date: 5-Mar-2012
  • (2011)Schema-less XML in columnsProceedings of the Twenty-Second Australasian Database Conference - Volume 11510.5555/2460396.2460401(17-26)Online publication date: 17-Jan-2011
  • (2011)Mixing bottom-up and top-down XPath query evaluationProceedings of the 15th international conference on Advances in databases and information systems10.5555/2041746.2041751(27-41)Online publication date: 20-Sep-2011
  • (2011)XPath evaluation in linear timeJournal of the ACM10.1145/1989727.198973158:4(1-33)Online publication date: 20-Jul-2011
  • (2011)Efficient evaluation for a temporal logic on changing XML documentsProceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1989284.1989317(259-270)Online publication date: 13-Jun-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media