SEMANTIC REPRESENTATIONS AND QUERY LANGUAGES FOR OR-SETS

Or-sets were introduced by Imielinski, Naqvi, and Vadaparty for dealin g with limited forms of disjunctive information in database queries. I ndependently, Rounds used a similar notion for representing disjunctiv e and conjunctive information in the context of situation theory. In t his 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. Lossl essness of normalization is established for a large class of queries. We obtain upper bounds for the cost of normalization. An approach rela ted to that of Rounds is used to provide semantics for or-sets. We als o treat or-sets in the context of partial information in databases. (C ) 1996 Academic Press, Inc.