In this work the focus is on algorithms that allow the evaluation of queries over large databases that use bottom-up techniques.
A new abstract data structure, called model tree, was developed for the storage and evaluation of disjunctive information and queries. This data structure reduces the amount of space needed for the database by allowing the sharing of data between different minimal models of the database.
With respect to evaluating queries that involve negation, we define algorithms that cover the cases of disjunctive stratified and normal deductive databases under the stable model semantics. We also treat the case of databases using the weak generalized closed world assumption.
A new translation for disjunctive normal databases under the stable model semantics was introduced that uses integrity constraints as the means to recognize and discard models that are not stable. This translation, used for the bottom-up evaluation of stable databases, has been the key for the development of top-down proof procedures for first order theories under the stable model semantics. New fixpoint characterizations for disjunctive, disjunctive stratified and disjunctive normal deductive databases were defined. The new fixpoint characterization has clarified the relationships between stratified and stable semantics both for deductive and disjunctive deductive theories.
This work also investigates the problem of updating databases containing disjunctive information and disjunctive rules of deduction. In particular an extension of previous results that use disjunctive facts as the way to perform view updates is presented. In the extended framework, not only can the extended database contain indefinite information, but disjunctive rules and integrity constraints are allowed. Update operations under this framework are more expressive than the traditional insert and delete operations present in traditional databases.