Author name cluster

Catriel Beeri

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TCS Journal 1993 Journal Article

Algebraic optimization of object-oriented query languages

Catriel Beeri
Yoram Kornatzky

Advanced database applications demand new data modeling constructs beyond those available in relational databases. These include both new data structures, e. g. arrays and quadtrees, and an integration with the object-oriented programming paradigm. Declarative object-oriented query languages transfer the burden of choosing an efficient execution plan to the database query optimizer. The lack of a generally accepted object-oriented data model and the trend towards extensible systems demand an extensible framework for object-oriented query optimization. We suggest such an algebraic optimization framework which is based on the computational metaphor of processing bulk data. Bulk data are defined using an abstract definition of the notion of data collection which includes familiar and novel types of bulk data. In particular, we integrate neatly object-oriented notions such as object identity and user-defined methods. To obtain generally applicable results, we use an FP-like language in which programs are constructed from primitive functions using a fixed set of functional forms. The latter abstract common patterns of processing data collections. The resulting algebra of programs generalizes for any data collection the known laws for transforming relational queries. We go beyond FP by allowing data structures containing functions, thus supporting the optimization of programs required in database programming environments.

Details DOI

TCS Journal 1985 Journal Article

Formal systems for join dependencies

Catriel Beeri
Moshe Y. Vardi

We investigate whether a sound and complete formal system for join dependencies can be found. We present a system that is sound and complete for tuple generating dependencies and is strong enough to derive join dependencies from join dependencies using only generalized join dependencies in the derivation. We also present a system that sound and complete for tuple generating dependencies and is complete for extended join dependencies (which are a special case of generalized join dependencies). Finally, we construct a Gentzen-style system that is sound and complete for join dependencies. The last two systems have unbounded inference rules.

Details DOI

STOC Conference 1981 Conference Paper

Properties of Acyclic Database Schemes

Catriel Beeri
Ronald Fagin
David Maier 0001
Alberto O. Mendelzon
Jeffrey D. Ullman
Mihalis Yannakakis

There is a class of database descriptions, involving one “acyclic” join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. Further, this class has many desirable properties. Some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. Other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. It is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. This paper is intended to summarize the results that will appear in more detail in [FMU] and [BFMY].

Details

STOC Conference 1979 Conference Paper

Equivalence of Relational Database Schemes

Catriel Beeri
Alberto O. Mendelzon
Yehoshua Sagiv
Jeffrey D. Ullman

We investigate the question of when two database schemes embody the same information. We argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. When data dependencies are given, we need only consider those fixed points that satisfy the dependencies. A polynomial algorithm to test the equivalence of database schemes, when there are no dependencies, is given. We also provide an exponential algorithm to handle the case where there are functional and/or multivalued dependencies. Furthermore, we give a polynomial time test to determine whether a project-join mapping preserves a set of functional dependencies, and a polynomial time algorithm for equivalence of database schemes whose project-join mappings do preserve the given set of functional dependencies. Lastly, we introduce the “update sets” approach to database design as an application of these results.

Details

FOCS Conference 1977 Conference Paper

The Theory of Joins in Relational Data Bases (Extended Abstract)

Alfred V. Aho
Catriel Beeri
Jeffrey D. Ullman

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, not all joins are semantically meaningful. This paper gives an efficient algorithm to determine whether the join of several relations is semantically meaningful (lossless) and an efficient algorithm to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. Similar techniques also apply to the case where data dependencies are multivalued.

Details

FOCS Conference 1975 Conference Paper

An Improvement of Valiant's Decision Procedure for Equivalence of Deterministic Finite-Turn Pushdown Automata

Catriel Beeri

In this paper Valiant's decision procedure for equivalence of deterministic finite-turn pushdown machines is improved upon. The improved equivalence test is: Given two mahcines, one constructs a pushdown machine that simulates them simultaneously and accepts a string iff it is accepted by exactly one of them. The given machines are equivalent iff the simulating pda accepts the empty language. The simulating machine uses its pushdown store to hold the contents of the stores of the two simulated machines. In order ot prevent the tops of the two stores to get too far apart the simulating machine sometimes replaces the contents of one of the stores. Valiant 1, 2 has proved the existence of a suitable function which determines the replacements. The crux of this paper is an algorithm for constructing such a function. The existence of such an algorithm enables us to calculate an upper bound on the time complexity of the improved algorithm. We obtain the results that equivalence of deterministic finite-turn pushdown automata can be tested in super-exponential time and equivalence of deterministic two-tape automata can be tested in exponential time.

Details