Please use this identifier to cite or link to this item:
|Title:||Non-linear Prefixes in Query Languages||Authors:||Badia, Antonio
|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:||http://hdl.handle.net/1942/7738||Link to publication:||http://doi.acm.org/10.1145/1265530.1265556||ISBN:||978-1-59593-685-1||Category:||C1||Type:||Proceedings Paper|
|Appears in Collections:||Research publications|
Show full item record
Files in This Item:
|pods174-badia.pdf||Preprint||244.81 kB||Adobe PDF||View/Open|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.