NDLI: Certain and possible XPath answers

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

A personal perspective on keyword search over data graphs

A theory of pricing private data

Fast learning of restricted regular expressions and DTDs

Structural tractability of counting of solutions to conjunctive queries

Walk logic as a framework for path query languages on graph databases

Algebraic structures for capturing the provenance of SPARQL queries

Schema mappings and data exchange for graph databases

Using the crowd for top-k and group-by queries

On optimal differentially private mechanisms for count-range queries

The DNA query language DNAQL

Which DTDs are streaming bounded repairable?

Recursive queries on trees and data trees

Querying graph databases with XPath

A propagation model for provenance views of public/private workflows

Containment of pattern-based queries over data trees

Certain and possible XPath answers

Optimal error of query sets under the differentially-private matrix mechanism

Enumerating with constant delay the answers to a query

XML compression via DAGs

On optimum left-to-right strategies for active context-free games

Definability problems for graph query languages

Annotations are relative

Access patterns and integrity constraints revisited

Extracting minimum-weight tree patterns from a schema with neighborhood constraints

Private decayed predicate sums on streams

Certain and possible XPath answers

Content Provider	ACM Digital Library
Author	Weiss, Yaacov Y. Cohen, Sara
Abstract	Formulating an XPath query over an XML document is a difficult chore for a non-expert user. This paper introduces a novel approach to ease the querying process. Instead of specifying a query, the user simply marks positive examples $χ^{+}$ of nodes that fit her information need. She may also mark negative examples $χ^{™}$ of undesirable nodes. A deductive method, to suggest additional nodes that will interest the user, is developed in this paper. To be precise, a node y is a certain answer if every query returning all positive examples $χ^{+},$ and not returning any negative example from $χ^{™},$ must also return y. Similarly, y is a possible answer if there exists a query returning $χ^{+}$ and y, while not returning any node in $χ^{™}.$ Thus, y is likely to be of interest to the user if y is a certain answer, and unlikely to be of interest if y is not even a possible answer. The complexity of finding certain and possible answers, with respect to various classes of XPath, is studied. It is shown that for a wide variety of XPath queries (including child and descendant axes, wildcards, branching and attribute constraints), certain and possible answers can be found efficiently, provided that $χ^{+}$ and $χ^{™}$ are of bounded size. To prove this result a novel algorithm is developed.
Starting Page	237
Ending Page	248
Page Count	12
File Format	PDF
ISBN	9781450315982
DOI	10.1145/2448496.2448525
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-03-18
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

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

When is naive evaluation possible?

MSO queries on trees: enumerating answers under updates

Towards Reconciling SPARQL and Certain Answers

Certain answers for XML queries

Incomplete information and certain answers in general data models

Computing possible and certain answers over order-incomplete data

Querying Incomplete Numerical Data: Between Certain and Possible Answers

Computing Possible and Certain Answers over Order-Incomplete Data

Possible and Certain Answers for Queries over Order-Incomplete Data

Certain and possible XPath answers

Similar Documents

When is naive evaluation possible?

MSO queries on trees: enumerating answers under updates

Towards Reconciling SPARQL and Certain Answers

Certain answers for XML queries

Incomplete information and certain answers in general data models

Computing possible and certain answers over order-incomplete data

Querying Incomplete Numerical Data: Between Certain and Possible Answers

Computing Possible and Certain Answers over Order-Incomplete Data

Possible and Certain Answers for Queries over Order-Incomplete Data

Certain and possible XPath answers