Semantic Representations and Query Languages for Or-Sets

Or-sets were introduced by Imielinski, Naqvi, and Vadaparty for dealing with limited forms of disjunctive information in database queries. Independently, Rounds used a similar notion for representing disjunctive and conjunctive information in the context of situation theory. In this paper we formulate a query language with adequate expressive power for or-sets. Using the notion of normalization of or-sets, queries at the “structural” and “conceptual” levels are distinguished. Losslessness of normalization is established for a large class of queries. We obtain upper bounds for the cost of normalization. An approach related to that of Rounds is used to provide semantics for or-sets. We also treat or-sets in the context of partial information in databases.