Nondeterministic databases store disjunctive data using OR-objects. For example, data such as "Part#1 is implementable using Nickel or Cobalt" is stored as Implement(Part#1, o/sub 1/) where Dom(o/sub 1/)={Nickel, Cobalt} is the domain of the OR-object o/sub 1/. A possible world of a database is obtained by replacing every OR-object by a member from its domain, and it is said to be conforming if it satisfies all the FDs (functional dependencies) associated with the database. A database D is said to fully incorporate a set F of FDs if every possible world of D is conforming. This paper studies the problem of preprocessing databases to achieve full incorporation, and also the problem of incrementally maintaining a database fully incorporated under insertions and deletions. We first define a certain property called goodness of a class D of databases for a set F of FDs; goodness can be tested efficiently and enforced easily at schema design time. For any class D of databases that is good for F, we present: 1) a quadratic time algorithm for fully incorporating F; 2) efficient algorithms for maintaining full incorporation under updates; and 3) lower-bounds for the algorithms of (1) and (2). Next, we show that, for classes of databases that are not good, the problem of full incorporation is, in general, coNP-complete. We also examine the complexity when OR-objects are restricted to have no more than two members, and obtain some interesting tractable algorithms, and intractability results.

This paper describes the environment, the issues and the progress made in developing a database management system for managing data generated by fracture study experiments in polymers and materials engineering. The experiment data produced by materials engineers is large and has several data types that include summary data, image data, spatial data, and temporal data obtained by applying differing amounts of multiaxial stresses to materials at different times. The types of queries on the experiment data include statistical queries, matching queries, mapping queries, and spatiotemporal queries. We discuss the data model, query language, and spatial data structure issues associated with our environment, and how they translate into specific research problems. We also briefly summarize the progress made in each area.>

Since the development of QBE, over fifty visual query languages have been proposed to facilitate easy database access. Although these languages have introduced some very useful paradigms, a number of these have some severe limitations, such as: (a) not extending beyond the relational model (b) not considering negation and safety, formally (c) using ad hoc constructs, with no analysis of expressivity or complexity done, etc. Note that visual database access is an important issue being revisted, with the emergence of different flavors of object-oriented databases. We believe that there is a need for developing a unified visual query language.

We are motivated by applications within design, planning in an object-oriented setting, and provide a complexity characterization for our queries.

If ground disjunctive facts are admitted into a database the data complexity of conjunctive queries grows from PTIME into CoNP with some simple examples of CoNP-Complete conjunctive queries. A natural question which arises in this context is whether it is possible to syntactically characterize those queries which are “bad” (i.e. CoNP-Complete) from those that are “good” (i.e. with PTIME data complexity) given a predefined 'pattern” of disjunctions in the database. In this paper, we study the data complexity of conjunctive queries. We give a complete syntactic characterization of CoNP-Complete conjunctive queries for a class of disjunctive databases called OR-Databases. Our results can be used in complexity tailored design where design decisions are motivated by complexity of query processing. Also, we establish that a similar complete syntactic characterization for disjunctive queries, with negation allowed only on base predicates, would answer the open problem “Does Graph Isomorphism belong to PTIME or is it NP-Complete?”.