Safety, domain independence and generalized quantification

摘要

We define QLGQ, a query language with generalized quantifiers, which uses only conjuction to combine formulas, the rest of its expressive power coming from generalized quantification. However, the language is not safe. A safe (and domain independent) sublanguage (SQLGQ) is defined; the definition uses properties of generalized quantifiers as well as (minimal) syntax limitations on formulas, and is motivated on semantical grounds, unlike most past approaches which are purely syntactic. We prove that SQLGQ subsumes RC/S*, one of the largest classes of safe languages proposed in the literature. Given these results, we propose that the most useful type of quantification for query languages is relativized quantification, in which the scope of the quantifier is made explicit as part of the query, and give this idea a technical form using generalized quantifiers. Finally, we extend work by Hull and Su on alternative semantics for first-order logic (FOL) to this new framework and propose some open questions for further research.