Please use this identifier to cite or link to this item:
Title: Non-linear Prefixes in Query Languages
Authors: Badia, Antonio
Vansummeren, Stijn 
Issue Date: 2007
Publisher: ACM Press
Source: Libkin, Leonid (Ed.) Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. p. 185-194.
Abstract: In first order logic there are two main extensions to quantification: generalized quantifiers and non-linear prefixes. While generalized quantifiers have been explored from a database perspective, non-linear prefixes have not -- most likely because of complexity concerns. In this paper we first illustrate the usefulness of non-linear prefixes in query languages by means of example queries. We then introduce the subject formally, distinguishing between two forms of non-linearity: branching and cumulation. To escape complexity concerns, we focus on monadic quantifiers. In this context, we show that branching does not extend the expressive power of first order logic when it is interpreted over finite models, while cumulation does not extend the expressive power when it is interpreted over bounded models. Branching and cumulation do, however, allow us to formulate some queries in a succinct and elegant manner. When branching and cumulation are interpreted over infinite models, we show that the resulting language can be embedded in an infinitary logic proposed by Libkin. We also discuss non-linear prefixes from an algorithmic point of view.
Keywords: Computer science, generalized quantifiers, non-linear prefixes, branching, cumulation
Document URI:
Link to publication:
ISBN: 978-1-59593-685-1
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
pods174-badia.pdfPreprint244.81 kBAdobe PDFView/Open
Show full item record

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.