CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year Technical Reports
By Class By Topic By Year Technical Reports
login
A. Badia and S. Vansummeren. Non-Linear Prefixes in Query Languages. In Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS '07, pages 185-194. ACM Press, Beijing, China, June 2007.

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.


Updated: 2017-03-27