NDLI: From XQuery to relational logics

Content Provider	ACM Digital Library
Author	Benedikt, Michael Koch, Christoph
Copyright Year	2009
Abstract	Predicate logic has long been seen as a good foundation for querying relational data. This is embodied in the correspondence between relational calculus and first-order logic, and can also be seen in mappings from fragments of the standard relational query language SQL to extensions of first-order logic (e.g. with counting). A key question is what is the analog to this correspondence for querying tree-structured data, as seen, for example, in XML documents. We formalize this as the question of the appropriate logical query language for defining transformations on tree-structured data. The predominant practitioner paradigm for defining such transformations is top-down tree building. This is embodied by the XQuery query language, which builds the output tree in parallel starting at the root, based on variable bindings and nodeset queries in the XPath language. The goal of this article is to compare the expressiveness of top-down tree-building languages based on a benchmark of predicate logic. We start by giving a formalized XQuery $\textit{XQ}$ that can serve as a representative of the top-down approach. We show that all queries in $\textit{XQ}$ with only atomic equality are equivalent to first-order interpretations, an analog to first-order logic (FO) in the setting of transformations of tree-structured data. We then consider fragments of atomic $\textit{XQ}.$ We identify a fragment that maps efficiently into first-order, a fragment that maps into existential first-order logic, and a fragment that maps into the navigationally two-variable fragment of first-order logic—an analog of two-variable logic in the setting where data values are unbounded. When $\textit{XQ}$ is considered with deep equality, we find that queries can be translated into FO with counting $(\textit{FO}(Cnt)).$ Translations from $\textit{XQ}$ to logical languages on relations have a number of consequences. We use them to derive complexity bounds for $\textit{XQ}$ fragments, and to bound the Boolean expressiveness of $\textit{XQ}$ fragments.
Starting Page	1
Ending Page	48
Page Count	48
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/1620585.1620592
Volume Number	34
Issue Number	4
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-12-14
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Information Systems

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

SilkRoute: A framework for publishing relational data in XML

On the complexity of nonrecursive XQuery and functional query languages on complex values

XQuery layers

Translation with optimization from relational calculus to relational algebra having aggregate functions

Projective Distribution of XQuery with Updates

An early look at XQuery

XQuery 3.0 is nearing completion

XQuery 1.0 is nearing completion

Fixpoint logics, relational machines, and computational complexity

From XQuery to relational logics

Similar Documents

SilkRoute: A framework for publishing relational data in XML

On the complexity of nonrecursive XQuery and functional query languages on complex values

XQuery layers

Translation with optimization from relational calculus to relational algebra having aggregate functions

Projective Distribution of XQuery with Updates

An early look at XQuery

XQuery 3.0 is nearing completion

XQuery 1.0 is nearing completion

Fixpoint logics, relational machines, and computational complexity

From XQuery to relational logics