移动数据库的依赖性研究

分析基本数据库的依赖关系。数据库及其环境的复杂程度决定了依赖关系的复杂程度。当一个数据库被移到一个新的服务器环境中,原有的依赖关系必须相应地移过去,并与新的数据库结合成一个整体,这样才能保证新的数据库系统不会因为环境的变化引起依赖关系的断裂式消失,从而使其不能正常工作。     

Null Inclusion Dependencies in Relational Databases

Functional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. We introduce null inclusion dependencies (NINDs) to cater for the situation when a database is incomplete and contains null values. We show that the implication problem for NINDs is the same as that for INDs. We then present a sound and complete axiom system for null functional dependencies (NFDs) and NINDs, and prove that the implication problem for NFDs and NINDs is decidable and EXPTIME-complete. By contrast, when no nulls are allowed, this implication problem is undecidable. This undecidability result has motivated several researchers to restrict their attention to FDs and noncircular INDs in which case the implication problem was shown to be EXPTIME- complete. Our results imply that when considering nulls in relational database design we need not assume that NINDs are noncircular.     

Weakly independent database schemes

Independent database schemes are best known to have constraints enforced globally by enforcing them locally in individual relations, and therefore are highly desirable in an updates-busy and distributed environment. However, independence excludes all database schemes with interrelational functional dependencies and therefore is too strong a condition. In this paper, a natural generalization of independent schemes along this line, called weakly independent schemes, is defined. A database scheme is weakly independent with respect to a set of embedded functional dependencies if the constraints can be enforced globally by enforcing local as well as interrelational functional dependencies. (a) A characterization of the weak independence and an exponential time test (in the number of functional dependencies) are presented. (b) Two polynomial time conditions are also presented, one is necessary and the other is sufficient for a database scheme to be weakly independent. (c) It is shown that a certain acyclicity of the database scheme implies weak independence. Extension to the case of embedded functional dependencies plus the join dependency is also considered. Received: 18 July 1991 / 28 September 1995     

A top-down proof procedure for generalized data dependencies

Data dependencies are well known in the context of relational database. They aim to specify constraints that the data must satisfy to model correctly the part of the world under consideration. The implication problem for dependencies is to decide whether a given dependency is logically implied by a given set of dependencies. A proof procedure for the implication problem, called “chase”, has already been studied in the generalized case of tuple-generating and equality-generating dependencies. The chase is a bottom-up procedure: from hypotheses to conclusion, and thus is not goal-directed. It also entails in the case of TGDs the dynamic creation of new constants, which can turn out to be a costly operation. This paper introduces a new proof procedure which is top-down: from conclusion to hypothesis, that is goal-directed. The originality of this procedure is that it does not act as classical theorem proving procedures, which require a special form of expressions, such as clausal form, obtained after Skolemization. We show, with our procedure, that this step is useless, and that the notion of piece allows infering directly on dependencies, thus saving the cost of Skolemizing the dependencies set and, morever, that the inference can be performed without dynamically creating new constants. Although top-down approaches are known to be less efficient in time than bottom-up ones, the notion of piece cuts down irrelevant goals usually generated, leading to a usable top-down method. With the more recent introduction of constrained and ordered dependencies, some interesting perspectives also arise. Received: 16 October 2000 / 11 May 2002     

On the finite controllability of conjunctive query answering in databases under open-world assumption

In this paper we study queries over relational databases with integrity constraints (ICs). The main problem we analyze is OWA query answering, i.e., query answering over a database with ICs under open-world assumption. The kinds of ICs that we consider are inclusion dependencies and functional dependencies, in particular key dependencies; the query languages we consider are conjunctive queries and unions of conjunctive queries. We present results about the decidability of OWA query answering under ICs. In particular, we study OWA query answering both over finite databases and over unrestricted databases, and identify the cases in which such a problem is finitely controllable, i.e., when OWA query answering over finite databases coincides with OWA query answering over unrestricted databases. Moreover, we are able to easily turn the above results into new results about implication of ICs and query containment under ICs, due to the deep relationship between OWA query answering and these two classical problems in database theory. In particular, we close two long-standing open problems in query containment, since we prove finite controllability of containment of conjunctive queries both under arbitrary inclusion dependencies and under key and foreign key dependencies. The results of our investigation are very relevant in many research areas which have recently dealt with databases under an incomplete information assumption: e.g., data integration, data exchange, view-based information access, ontology-based information systems, and peer data management systems.     

XML函数依赖研究综述

函数依赖作为数据库规范化的基础在关系理论中起着重要的作用。近年来，XML得到广泛应用并已成为互联网上数据传输和交换的标准。由于XML半结构化的特性，使得如何定义XML函数依赖使其具有更强的描述能力，以及如何解决相应的逻辑蕴涵问题成为当今学术界所面临的挑战。针对这些问题，系统地描述了目前关于XML函数依赖的研究现状，特别是把分析的重点放在如何定义函数依赖、判断其蕴涵关系以及从XML文档中发现函数依赖等问题上。最后讨论了诸如类型化函数依赖关系等一些相关的研究方向。     

Armstrong databases for functional and inclusion dependencies

An Armstrong database is a database that obeys precisely a given set of sentences (and their logical consequences) and no other sentences of a given type. It is shown that if the sentences of interest are inclusion dependencies and standard functional dependencies (functional dependencies for which the left-hand side is nonempty), then there is always an Armstrong database for each set of sentences. (An example of an inclusion dependency is the sentence that says that every $\text{MANAGER}$ is an $\text{EMPLOYEE}$.) If, however, the sentences of interest are inclusion dependencies and unrestricted functional dependencies, then there need not exist an Armstrong database. This result holds even if we allow only ‘full’ inclusion dependencies. Thus, a fairly sharp line is drawn, in a case of interest, as to when an Armstrong database must exist. These results hold whether we restrict our attention to finite databases (databases with a finite number of tuples), or whether we allow unrestricted databases.     

The implication problem for ‘closest node’ functional dependencies in complete XML documents

With the growing use of XML as a format for the permanent storage of data, the study of functional dependencies in XML (XFDs) is of fundamental importance in a number of areas such as understanding how to effectively design XML databases without redundancy or update problems, and data integration. In this article we investigate a particular type of XFD, called a weak ‘closest node’ XFD, that has been shown to extend the classical notion of a functional dependency in relational databases. More specifically, we investigate the implication problem for weak ‘closest node’ XFDs in the context of XML documents with no missing information. The implication problem is the most important one in dependency theory, and is the problem of determining if a set of dependencies logically implies another dependency. Our first, and main, contribution is to provide an axiom system for XFD implication. We prove that our axiom system is both sound and complete, and we then use this result to develop a sound and complete quadratic time closure algorithm for XFD implication. Our second contribution is to investigate the implication problem for XFDs in the presence of a Document Type Definition (DTD). We show that for a class of DTDs called structured DTDs, the implication problem for a set of XFDs and a structured DTD can be converted to the implication problem for a set of XFDs alone, and so is axiomatizable and efficiently solvable by the first contribution. We do this by augmenting the original set of XFDs with additional XFDs generated from the structure of the DTD.     

Discovering branching and fractional dependencies in databases

The discovery of dependencies between attributes in databases is an important problem in data mining, and can be applied to facilitate future decision-making. In the present paper some properties of the branching dependencies are examined. We define a minimal branching dependency and we propose an algorithm for finding all minimal branching dependencies between a given set of attributes and a given attribute in a relation of a database. Our examination of the branching dependencies is motivated by their application in a database storing realized sales of products. For example, finding out that arbitrary p products have totally attracted at most q new users can prove to be crucial in supporting the decision making.In addition, we also consider the fractional and the fractional branching dependencies. Some properties of these dependencies are examined. An algorithm for finding all fractional dependencies between a given set of attributes and a given attribute in a database relation is proposed. We examine the general case of an arbitrary relation, as well as a particular case where the problem of discovering the fractional dependencies is considerably simplified.     

Full hierarchical dependencies in fixed and undetermined universes

Full hierarchical dependencies (FHDs) constitute a large class of relational dependencies. A relation exhibits an FHD precisely when it is the natural join over at least two of its projections that all share the same join attributes. Therefore, FHDs generalise multivalued dependencies (MVDs) in which case the number of these projections is precisely two. The implication of FHDs has originally been defined in the context of some fixed finite universe. This paper identifies a sound and complete set of inference rules for the implication of FHDs. This axiomatisation is very reminiscent of that for MVDs. Then, an alternative notion of FHD implication is introduced in which the underlying set of attributes is left undetermined. The first main result establishes a finite axiomatisation for FHD implication in undetermined universes. It is then formally clarified that the complementation rule is only a mere means for database normalisation. In fact, the second main result establishes a finite axiomatisation for FHD implication in fixed universes which allows to infer FHDs either without using the complementation rule at all or only in the very last step of the inference. This also characterises the expressiveness of an incomplete set of inference rules in fixed universes. The results extend previous work on MVDs by Biskup.     

A sound and complete chase procedure for constrained tuple-generating dependencies

We present a chase procedure for solving the implication problem of constrained tuple-generating dependencies (ctgds), a general class of database dependencies that is also able to handle data and predicates on interpreted domains. Current chase procedures for ctgds are sound but not complete, in the sense that they are unguaranteed to stop successfully whenever implication is true. The procedure we present is sound and complete, the first to our knowledge. It follows a linear reasoning over constraint domains that have the Independence of Negative Constraints property. We then soundly extend this procedure by a disjunctive reasoning over unrestricted constraint domains. To achieve these results, we used a different approach. Previous chases act like a closure operator, whereas we used a goal-directed design.     

条件依赖理论及其应用展望

介绍了条件函数依赖理论及如何用于检测不一致数据.首先介绍了条件函数依赖的概念及其推理系统,以及如何通过依赖传播实现视图的规范化;阐述了条件函数依赖的一致性和蕴含判定问题,并在此基础上介绍了基于条件函数依赖检测关系数据库数据一致性的技术;最后讨论了条件函数依赖的扩展及应用.     

Charting the completeness frontier of inference systems for multivalued dependencies

The implication of multivalued dependencies in relational databases has originally been defined in the context of some fixed finite universe. While axiomatisability and implication problems have been intensely studied with respect to this notion almost no research has been devoted towards the alternative notion of implication in which the underlying universe of attributes is left undetermined. Based on a set of common inference rules we establish all axiomatisations in undetermined universes, and all axiomatisations in fixed universes that indicate the role of the complementation rule as a means of database normalisation. This characterises the expressiveness of several incomplete sets of inference rules. We also establish relationships between axiomatisations in fixed and undetermined universes, and study the time complexity of the implication problem in undetermined universes. The results of this paper establish a foundation for reasoning about multivalued dependencies without the assumption of a fixed underlying universe.     

H∞ optimization with plant uncertainty and semidefinite programming

The fundamental H^∞ problem of control is that of finding the stable frequency response function that best fits worst case frequency domain specifications. This is a non-smooth optimization problem that underlies the frequency domain formulation of the H^∞ problem of control; it is the main optimization problem in qualitative feedback theory for example. It is shown in this article how the fundamental H^∞ optimization problem of control can be naturally treated with modern primal–dual interior point (PDIP) methods. The theory introduced here generalizes and unifies approaches to solving large classes of optimization problems involving matrix-valued functions, a subclass of which are commonly treated with linear matrix inequalities techniques. Also, in this article new optimality conditions for H^∞ optimization problems over matrix-valued functions are proved, and numerical experience on natural (PDIP) algorithms for these problems is reported. In experiments we find the algorithms exhibit (local) quadratic convergence rate in many instances. Finally, H^∞ optimization problems with an uncertainty parameter are considered. It is shown how to apply the theory developed here to obtain optimality conditions and derive algorithms. Numerical tests on simple examples are reported. © 1998 John Wiley & Sons, Ltd.     

An algorithm for robust performance tests based on frequency-dependent LMIs

In this paper, an algorithm is introduced for feasibility problems associated with frequency-dependent, linear matrix inequalities — these problems correspond to H ₂ or H _∞ robust performance tests for a given controller, in the face of feedback perturbations. To this effect, an auxiliary H ₂ cost-functional is introduced and a sequence of H ₂ problems with a single linear constraint is considered in which the H ₂ cost-functional is kept unchanged while the linear constraints are iteratively modified. It is shown that, in each step, the auxiliary optimal solution moves closer (in the sense of a weighted quadratic norm) to the target feasible set. Conditions are also established under which the sequence of solutions to the auxiliary problems yields a solution to the original feasibility problem. The method is illustrated by a numerical example corresponding to a H _∞ robust performance test for a multivariable system.     

Losslessness and project-join constructibility in relational databases

Summary Checking a database scheme for the lossless join property with respect to a set, M, of multivalued dependencies (MVDs) is NP-hard. We prove that, for a class of MVDs that includes the set of projected full MVDs, this check can be performed in polynomial time. Even with a lossless database scheme and a consistent database, joining the set of relations in the database can take time and space that is exponential in the size of the relation finally obtained. Joining the set of relations of such a database can be performed in polynomial time if the database scheme is project-join constructible with respect to M. We prove that project-join constructibility, a stricter condition than the lossless join property, can be detected in a database scheme in polynomial time.     

Discovering interesting inclusion dependencies: application to logical database tuning

Inclusion dependencies together with functional dependencies form the most important data dependencies used in practice. Inclusion dependencies are important for various database applications such as database design and maintenance, semantic query optimization and efficient view maintenance of data warehouse. Existing approaches for discovering inclusion dependencies consist in producing the whole set of inclusion dependencies holding in a database, leaving the task of selecting the interesting ones to an expert user.In this paper, we take another look at the problem of discovering inclusion dependencies. We exploit the logical navigation, inherently available in relational databases through workloads of SQL statements, as a guess to automatically find out only interesting inclusion dependencies. This assumption leads us to devise a tractable algorithm for discovering interesting inclusion dependencies. Within this framework, approximate dependencies, i.e. inclusion dependencies which almost hold, are also considered.As an example, we present a novel application, namely self-tuning the logical database design, where the discovered inclusion dependencies can be used effectively.     

Minimal-change integrity maintenance using tuple deletions

We address the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases. We assume that integrity-restoration actions are limited to tuple deletions. We focus on two basic computational issues: repair checking (is a database instance a repair of a given database?) and consistent query answers [in: ACM Symposium on Principles of Database Systems (PODS), 1999, 68] (is a tuple an answer to a given query in every repair of a given database?). We study the computational complexity of both problems, delineating the boundary between the tractable and the intractable cases. We consider denial constraints, general functional and inclusion dependencies, as well as key and foreign key constraints. Our results shed light on the computational feasibility of minimal-change integrity maintenance. The tractable cases should lead to practical implementations. The intractability results highlight the inherent limitations of any integrity enforcement mechanism, e.g., triggers or referential constraint actions, as a way of performing minimal-change integrity maintenance.     

A comment on ‘ self-tuning pole/zero assignment regulators’

The generalized H ₂ optimal control problem for a linear time-invariant system is one in which the conventional H ₂ norm is replaced by an operator norm. The closed-loop system is described in terms of a mapping between the space of time-domain input disturbances in L ₂ and the space of time-domain regulated outputs in L _∞. A minimum of this norm is then sought over all stabilizing controllers. It is shown that optimal controllers for such problems have the structure of a Kalman filter with estimated state feedback, where the feedback gains are obtained from the solution to a weighted LQR problem. A computational algorithm is presented to determine the weights in this LQR problem, and examples are given which demonstrate various problems which may arise in obtaining the optimal weights. In particular, it is shown that the generalized H ₂ problem may involve the solution to a singular LQR problem.