Search

This paper addresses the problem of representing the set of repairs of a possibly inconsistent database by means of a disjunctive database. Specifically, the class of denial constraints is considered. We show that, given a database and a set of denial constraints, there exists a (unique) disjunctive database, called canonical, which represents the repairs of the database w.r.t. the constraints and is contained in any other disjunctive database with the same set of minimal models. We propose an algorithm for computing the canonical disjunctive database. Finally, we study the size of the canonical disjunctive database in the presence of functional dependencies for both subset-based repairs and cardinality-based repairs.

We will consider the following problem in this paper: Assume that there are $$n$$ numerical data $$\{x_1,x_2,\ldots,x_n\}$$ (like salaries of $$n$$ individuals) stored in a database and some subsums of these numbers are made public or just available for persons not eligible to learn the original data. Our motivating question is: At most how many of these subsums may be disclosed such that none of the numbers $$x_1,x_2,\ldots,x_n$$ can be uniquely determined from these sums. These types of problems arise in the cases when certain tasks concerning a database are done by subcontractors who are not eligible to learn the elements of the database, but naturally should be given some data to fulfill there task. In database theory such examples are called statistical databases as they are used for statistical purposes and no individual data are supposed to be obtained using a restricted list of SUM queries. This problem was originally introduced by [1], originally solved by Miller et al. [7] and revisited by Griggs [4, 5]. It was shown in [7] that no more than $${n\choose n/2}$$ subsums of a given set of secure data may be disclosed without disclosing at least one of the data, which upper bound is sharp as well. To calculate a subsum, it might need some operations whose number is limited. This is why it is natural to assume that the disclosed subsums of the original elements of the database will contain only a limited number of elements, say at most $$k$$ . The goal of the present paper is to determine the maximum number of subsums of size at most $$k$$ which can be disclosed without making possible to calculate any of the individual data $$x_i$$ . The maximum is exactly determined for the case when the number of data is much larger than the size restriction $$k$$ .

We say, that a subset K of the columns of a matrix is called a key, if every two rows that agree in the columns of K agree also in all columns of the matrix. A matrix represents a Sperner system K, if the system of minimal keys is exactly K. It is known, that such a representation always exists. In this paper we show, that the maximum of the minimum number of rows, that are needed to represent a Sperner system of only two element sets is 3(n/3+o(n)). We consider this problem for other classes of Sperner systems (e.g., for the class of trees, i.e. each minimal key has cardinality two, and the keys form a tree), too. The concept of keys plays an important role in database theory.

In this article, we characterize in terms of analytic tableaux the repairs of inconsistent relational databases, that is databases that do not satisfy a given set of integrity constraints. For this purpose we provide closing and opening criteria for branches in tableaux that are built for database instances and their integrity constraints. We use the tableaux based characterization as a basis for consistent query answering, that is for retrieving from the database answers to queries that are consistent with respect to the integrity constraints.

We present a data model for spatio-temporal databases. In this model spatio-temporal data is represented as a finite union of objects described by means of a spatial reference object, a temporal object and a geometric transformation function that determines the change or movement of the reference object in time. We define a number of practically relevant classes of spatio-temporal objects, and give complete results concerning closure under Boolean set operators for these classes. Since only few classes are closed under all set operators, we suggest an extension of the model, which leads to better closure properties, and therefore increased practical applicability. We also discuss a normal form for this extended data model.

An operation for restricting deductive databases represented as logic programs is introduced. The constraints are coded in a separate database, and the operator puts the two databases together in order to provide a restricted view of the original database. The operator is given a semantics in terms of the immediate consequence operator. Then a transformational implementation is given and its correctness is proved with respect to the abstract semantics. The approach is presented at first for positive programs and it is then extended to take negation as failure into account.

While non-determinism has long been established as a key concept in logic pro-gramming, its importance in the context of deductive databases was recognized only recently. This paper provides an overview of recent results on this topic with the aim of providing an introduction to the theory and practice of non-determinism in deductive databases. In particular we (i) recall the main results linking non-deterministic constructs in database languages to the theory of data complexity and the expressibility hierarchy of query languages; (ii) provide a reasoned introduction to effective programming with non-deterministic constructs; (iii) compare the usage of non-deterministic constructs in languages such as LDL++ to that of traditional logic programming languages; (iv) discuss the link between the semantics of logic programs with non-deterministic constructs and the stable-model semantics of logic programs with negation.

The logical theory of database integrity is developed as an application of deontic logic. After a brief introduction to database theory and Kripke semantics, a deontic operator X, denoting “what should hold, non-trivially, given a set of constraints”, is defined and axiomatized. The theory is applied to updates, to dynamic constraints and to databases extended with nulls.

Database design methodologies should facilitate database modeling, effectively support database processing, and transform a conceptual schema of the database to a high-performance database schema in the model of the corresponding DBMS. The Entity-Relationship Model is extended to theHigher-orderEntity-RelationshipModel (HERM) which can be used as a high-level, simple and comprehensive database design model for the complete database information on the structure, operations, static and dynamic semantics. The model has the expressive power of semantic models and possesses the simplicity of the entity-relationship model. The paper shows that the model has a well-founded semantics. Several semantical constraints are considered for this model.

We investigate the complexity of query processing in databases which have both incompletely specified data and deductive rules. The paper is divided into two parts: in the first we consider databases in which incompletely specified data occurs only in the database intension; in the second we consider databases in which incomplete information is represented only in database extension. We prove that, in general, the query processing problem for databases with incomplete intensions is undecidable. A number of classes of rules for which all conjunctive queries can be processed in polynomial time is then characterized. For databases with incomplete extensions we prove a number of CoNP completeness results. For instance, we demonstrate that processing disjunctions which are restricted to individual columns of database predicates can, in general, be as bad as processing arbitrary disjunctions (i.e. CoNP-complete). This falsifies the conjecture that such limited disjunctions could be computationally beneficial. We also show two simple examples of situations in which query processing is guaranteed to be polynomial. These situations are linked to certain assumptions about database updates.