PODS

Scientific applications are infrequent users of commercial database management systems. We feel that a key reason is they do not offer good support for ordered data structures, such as multidimensional arrays, that are needed for natural representation ...

In reflective programming languages it is possible for a program to generate code that is integrated into the program's own execution. We introduce a reflective version of the relational algebra. Reflection is achieved by storing and manipulating ...

Strong normalization results are obtained for a general language for collection types. An induced normal form for sets and bags is then used to show that the class of functions whose input has height (that is, the maximal depth of nestings of sets/bags/...

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 ...

Bags, i.e. sets with duplicates, are often used to implement relations in database systems. In this paper we study the expressive power of algebras for manipulating bags. The algebra we present is a simple extension of the nested relation algebra. Our ...

Katsuno and Mendelzon divide theory change, the problem of adding new information to a logical theory, into two types: revision and update. We propose a third type of theory change: arbitration. The key idea is the following: the new information is ...

The Extended Commitment Ordering (ECO) property of transaction histories (schedules) generalizes the Commitment Ordering (CO) property defined in [Raz 90]. In a multi resource manager (RM) environment ECO guarantees global serializability when supported ...

We consider the problems of equivalence, satisfiability and query-reachability for datalog programs with negation and dense-order constraints. These problems are important for optimizing datalog programs. We show that both query-reachability and ...

We study applying the magic-sets transformation technique to Datalog programs with negation that may not have 2-valued well-founded models. In this general setting we encounter the problem that the well-founded model of the original program does not ...

In this paper, we study the ability of data-independent conjunctive expressions (envelopes) to approximate fixpoint of Datalog predicates. We show that no effective procedure exists for finding envelopes that best approximate the fix-point (tight ...

Two main approaches have been followed in the literature to give a semantics to non-Horn databases. The first one is based on considering the set of rules composing the programs as inference rules and interpreting the negation in the body as failure to ...

This paper addresses complexity issues for important problems arising with disjunctive databases. In particular, the complexity of inference of a literal and a formula from a propositional disjunctive database under a variety of well-known disjunctive ...

SLD resolution with negation as finite failure (or SLDNF) reflects the procedural interpretation of Horn-clause predicate logic as a programming language and forms the computational basis for prolog systems. Despite its advantages in memory management, ...

A model is described to estimate the size of intermediate relations produced by large relational algebra expressions, in particular, those containing several equi-joins. The intended application is within query optimization searches, where fast ...

We compare the performance of sampling-based procedures for estimation of the selectivity of an equijoin. While some of the procedures have been proposed in the database sampling literature, their relative performance has never been analyzed. A main ...

We analyze the computational feasibility of checking temporal integrity constraints formulated in some sublanguages of first-order temporal logic. Our results illustrate the impact of the quantification on the complexity of this problem. The presence of ...

In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them. For each model, we characterize the efficiency of spatial data structures in terms of the expected number of data bucket ...

In this paper, we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of ...

We examine I/O-efficient data structures that provide indexing support for new data models. The database languages of these models include concepts from constraint programming (e.g., relational tuples are generalized to conjunctions of constraints) and ...

We consider infinite recursive (i.e., computable) relational data bases. Since the set of computable queries on such data bases is not closed under even simple relational operations, one must either make do with a very humble class of queries or ...

The expressiveness of various object-oriented languages is investigated with respect to their ability to create new objects. We focus on database method schemas (dms), a model capturing the data manipulation capabilities of a large class of ...

The expressiveness of various object-oriented languages is investigated with respect to their ability to create new objects. We focus on database method schemas (dms), a model capturing the data manipulation capabilities of a large class of ...