We formulate some natural conditions which should be satisfied in an extension of the relational algebra from the usual relations to tables with null values, and we explain the motivation behind these conditions. Roughly speaking, our conditions say that the extended algebra makes it possible to correctly compute the "true tuples" in the result of applying a relational expression (query) to tables with nulls (database state), and that the computation can be carried out recursively, following the structure of the expression. We prove that these conditions are exactly equivalent to other conditions proposed earlier by the author and T. Imieliński. We give a simple proof of the correctness of the "naive" extension of the relational algebra to tables with marked nulls, where the nulls are treated as if they were regular values, and which supports the operations of projection, positive selection, union, join and renaming of attributes. We also show that the result of the naive evaluation of such an expression (query) is equal to the response to the query as defined --- in a proof-theoretic framework --- by Reiter.

This paper concerns the semantics of Codd's relational model of data.Formulated are precise conditions that should be satisfied m a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with "null values" of various kinds allowed.These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by usmg a specified subset [l of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in fl are in fact derivable in this system.Two such systems of practical interest are shown.The first, based on the usual Codd's null values, supports projection and selection.The second, based on many different ("marked") null values or variables allowed to appear in a table, ~s shown to correctly support projection, posmve selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries.A very desirable property enjoyed by this system is that all relational t~perators on tables are performed in exactly the same way as in the case of the usual relations.A third system, mainly of theoretical interest, supporting projection, selection, union, join, and renaming, is also discussed.Under a so-called closed world assumption, it can also handle the operator of difference.It is based on a device called a condiUonal table and is crucial to the proof of the correctness of the second system.All systems considered allow for relational expressions contaming arbitrardy many different relation symbols, and no form of the universal relation assumption is required.

In this paper we show that any channel routing problem of density d involving only two-terminal nets can always be solved in the knock-knee mode in a channel of width equal to the density d with three conducting layers. An algorithm is described which produces in time O(n log n) (in its simplest implementation) a layout of n nets with the following properties: 1) it has minimal width d; 2) it can be realized with three layers; 3) it has at most 3n vias; 4) any two wires share at most four grid points. Without sacrificing any of the above properties (but possibly obtaining slightly longer wires), the layout algorithm can be modified to run in time θ(n).

Let f be a relational expression and let q be a relation. It appears, surprisingly enough, that the concept of the table introduced in order to represent incomplete information can be used as a tool for representing {r f(r) ⊇ q} for a class of relational expressions built up from projection, join and positive selection. This fact, together with some other known properties of tables has wide applications and leads to a new technique for expressing and solving many database problems, especially those concerned with views. This technique is, we believe, more natural and systematic than those previously used such as tableau techniques. Some applications, like view dependencies, translating states between views and the view equivalence problem are presented.

An incomplete information relational database combines two types of information about the real world modeled by the database: (a) the information represented by tables with null values ("value not known") allowed as entries, and (b) the data dependencies, which are known to be satisfied in the real world. We view the well known chase procedure as a process which transforms type (b) information into an "equivalent" type (a) form. Assuming that the data dependencies are arbitrary implicational dependencies, we show that this transformation is not quite equivalent, but the corruption of information introduced cannot be discovered if the query language uses the operations of projection, positive selection (i.e. no negation in selection condition), union, natural join and renaming of attributes. This result can be interpreted also as the new important property of chase.The influence of so-called view dependencies on the table with null values is also examined.

Abstract Let S be a set of n horizontal and vertical segments on the plane, and let s, t ∈ S. A Manhattan path (of length k) from s to t is an alternating sequence of horizontal and vertical segments s = r0, r1,…,rk = t where ri intersects ri+1, 0 ≤ i < k. An from all s ∈ S to t. Also given is a method to determine a maximum set of crossings (intersections of segments) with no two on the same segment, as well as a maximum set of nonintersecting segments, both in O(n3/2 log2 log2 n) time. The latter algorithm is applied to decomposing, in O(n3/2 log2 n) time, a hole‐free union of n rectangles with sides parallel to the coordinate axes into the minimal number of disjoint rectangles. All the algorithms require O(n log n) space, and for all of them the factor log2 n can be improved to log n log log n, at the cost of some complication of the basic data structure used.

In this paper we show that any channel routing problem of density d involving two-terminal nets can always be solved in the knock-knee mode in a channel of width equal the density d with three conducting layers. An algorithm is described which produces a layout of n nets with the following properties: (i) it has minimal width d; (ii) it can be realized with three layers; (iii) it has at most 3n vias; (iv) any two wires share at most four grid points.

In an attempt to eliminate motivational inconsistencies, we propose a new approach to relational database theory. Basically, a database schema is treated as a relational view defined over certain atomic, selfexplainable relations, constituting what we call a conceptual schema. In this new framework, we revisit some basic notions of the relational database theory, such as dependencies and schema equivalence. We point out a fundamental difference between functional dependencies, which we treat as constraints over the conceptual schema, and multivalued and join dependencies, which we treat as constraints over the database schema, and which are simply consequences of the way database relations are constructed from conceptual relations. The separation of the database schema from the conceptual schema makes it possible to give a clear definition of a semantics of a database state. It also provides a natural framework to consider equivalence of database schemata.

Consider two database schemata modeling the same reality. Given a state of the first schema, we can ask what information it provides about the state of the second schema. It turns out that this information can be represented by a table similar to a tableau of Aho, Sagiv and Ullman. We show a simple method to construct this table, by using results developed for tables of this type in the context of representing incomplete information in relational databases. We also consider a closely related notion of equivalence of database schemata, briefly sketching a method to test two schemata for equivalence.

Semantic and logical problems arising in an incomplete information database are investigated.A simple query language is described, and its semantics, which refers the queries to the information about reality contained in a database, rather than to reality itself, is defined.This approach, called the internal interpretation, is shown to lead in a natural way to the notions of a topological Boolean algebra and a modal logic related to $4 in the same way as referring queries directly to reality (external interpretation) leads to Boolean algebras and classical logic.An axiom system is given for equivalent (with respect to the internal interpretation) transformation of queries, which is then exploited as a basic tool in a method for computing the internal interpretation for a broad class of queries.An interesting special case of the problem of determining the internal interpretation amounts to deciding whether an assertion about reality (a "yes-no" query) is consistent with the incomplete information about reality contained in a database.A solution to this problem, which relies on the classical combinatorial problem of distinct representatives of subsets, is given.

Various approaches to interpreting queries in a database with incomplete information are discussed. A simple model of a database is described, based on attributes which can take values in specified attribute domains. Information incompleteness means that instead of having a single value of an attribute, we have a subset of the attribute domain, which represents our knowledge that the actual value, though unknown, is one of the values in this subset. This extends the idea of Codd's null value, corresponding to the case when this subset is the whole attribute domain. A simple query language to communicate with such a system is described and its various semantics are precisely defined. We emphasize the distinction between two different interpretations of the query language—the external one, which refers the queries directly to the real world modeled in an incomplete way by the system, and the internal one, under which the queries refer to the system's information about this world, rather than to the world itself. Both external and internal interpretations are provided with the corresponding sets of axioms which serve as a basis for equivalent transformations of queries. The technique of equivalent transformations of queries is then extensively exploited for evaluating the interpretation of (i.e. the response to) a query.