NDLI: Containment and equivalence for an XPath fragment

Please wait, while we are loading the content...

Models and issues in data stream systems

Monadic datalog and the expressive power of languages for web information extraction

Algorithmics and applications of tree and graph searching

Validating streaming XML documents

Conjunctive selection conditions in main memory

On the computation of relational view complements

OLAP dimension constraints

Knowledge compilation = query rewriting + view synthesis

Data integration: a theoretical perspective

Lossless regular views

On the complexity of approximate query optimization

From discrepancy to declustering: near-optimal multidimensional declustering strategies for range queries

Containment and equivalence for an XPath fragment

Efficient aggregation over objects with extent

On propagation of deletions and annotations through views

Fast algorithms for hierarchical range histogram construction

Answering queries using views with arithmetic comparisons

On verifying consistency of XML specifications

Least expected cost query optimization: what can we expect?

On the power of walking for querying tree-structured data

How to evaluate multiple range-sum queries progressively

The view-selection problem has an exponential-time lower bound for conjunctive queries and views

On moving object queries: (extended abstract)

Characterizing memory requirements for queries over continuous data streams

Labeling dynamic XML trees

A normal form for XML documents

Distributed computation of web queries using automata

Containment and equivalence for an XPath fragment

Content Provider	ACM Digital Library
Author	Miklau, Gerome Suciu, Dan
Abstract	XPath is a simple language for navigating an XML document and selecting a set of element nodes. XPath expressions are used to query XML data, describe key constraints, express transformations, and reference elements in remote documents. This paper studies the containment and equivalence problems for a fragment of the XPath query language, with applications in all these contexts.In particular, we study a class of XPath queries that contain branching, label wildcards and can express descendant relationships between nodes. Prior work has shown that languages which combine any two of these three features have efficient containment algorithms. However, we show that for the combination of features, containment is coNP-complete. We provide a sound and complete EXPTIME algorithm for containment, and study parameterized PTIME special cases. While we identify two parameterized classes of queries for which containment can be decided efficiently, we also show that even with some bounded parameters, containment is coNP-complete. In response to these negative results, we describe a sound algorithm which is efficient for all queries, but may return false negatives in some cases.
Starting Page	65
Ending Page	76
Page Count	12
File Format	PDF
ISBN	1581135076
DOI	10.1145/543613.543623
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-06-03
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in