Processing Queries Containing Generalized

Quantifiers

Sudhir Rao, Antonio Badia, and Dirk Van Gucht

Indiana University ?

Abstract
We considered the problem of processing queries that contain generalized quantifiers. We demonstrate that current relational systems are ill-equipped, both at the language and at the query processing level, to deal with such queries. We propose a boolean matrix approach which establishes the feasibility of building systems that can process queries with generalized quantifiers efficiently, and we provide insights into the intrinsic difficulties associated with processing such queries.

1 Introduction

Numerous existing query languages (SQL [25], OQL [6], CORAL [24], RC/S [23] etc.) allow queries with embedded sub-queries as well as sub-query comparison statements.1 It is often argued that these features enhance the declarativeness of the query language. In two recent papers, Hsu and Parker [17] and, independently, Badia, Van Gucht, and Gyssens [2], validated this argument by establishing a link between the phenomenon of sub-query syntax in query languages and the theory of generalized quantifiers as it was introduced by Barwise and Cooper [3] in linguistics.2

Taking as established that generalized quantifiers are crucial in query languages, it becomes vital to demonstrate that queries containing generalized quantifiers (GQ- queries) can be supported effectively. The present paper takes a step in this direction. As will become clear, however, it will be necessary to augment conventional languages, such as SQL, with appropriate mechanisms to allow the formulation of GQ-queries, and, it will be necessary to augment existing file organizations and access methods with appropriate data structures and algorithms to support critical operations necessary in the evaluation of GQ-queries.

We are of the opinion that, as long as query languages and query processors continue to offer limited support for GQ-queries, the database community can not claim to have solved the query processing problem in the decision support area.

The paper is organized as follows. In Section 2, we provide an introduction to generalized quantifiers. In Section 3, we demonstrate that GQ-queries are inadequately supported in current relational database management systems. There are

?CS Department, Bloomington, IN 47405. E-mail: fsrao, abadia, [email protected]. 1Several recent papers [7, 20] have pointed out that users commonly use these features. 2The authors of [2] took this validation a step further and postulated the conjunctive formulation thesis. This thesis states that real-world queries can be formulated most naturally as a conjunction of first-order-predicate statements and generalized-quantifier statements over sub-queries. [2] also introduced a query language, called QLGQ, which was designed in accordance with this thesis. (It is clear from Hsu and Parker's paper that SQL is designed in accordance with the conjunctive formulation thesis. The problem with SQL is that it stops short of taking full advantage of its inherently good design. In fact, original-SQL (SEQUEL/2) [5] was better than SQL in this regard.)