ON REPRESENTATION AND QUERYING INCOMPLETE INFORMATION IN DATABASES WITH BAGS

We extend the approach to representation of partial information based on orderings on objects from sets to multisets. We characterize orderi ngs arising under closed- and open-world assumptions and analyze their complexity. In contrast to the set case, where orderings are first-or der definable and are thus expressible in standard database query lang uages, the orderings on bags are not expressible in standard bag langu ages. We give an example of a query on nested relations whose inexpres sibility in the extension of relational algebra to nested objects cann ot be proved by reduction to the first-order case.