Reasoning with examples: propositional formulae and database dependencies

For humans, looking at how concrete examples behave is an intuitive way of deriving conclusions. The drawback with this method is that it does not necessarily give the correct results. However, under certain conditions example-based deduction can be used to obtain a correct and complete inference procedure. This is the case for Boolean formulae (reasoning with models) and for certain types of database integrity constraints (the use of Armstrong relations). We show that these approaches are closely related, and use the relationship to prove new results about the existence and size of Armstrong relations for Boolean dependencies. Furthermore, we exhibit close relations between the questions of finding keys in relational databases and that of finding abductive explanations. Further applications of the correspondence between these two approaches are also discussed. Received: 19 June 1995 / 31 August 1998     

Discovering context-aware conditional functional dependencies

Conditional functional dependencies(CFDs) are important techniques for data consistency. However, CFDs are limited to 1) provide the reasonable values for consistency repairing and 2) detect potential errors. This paper presents context-aware conditional functional dependencies(CCFDs) which contribute to provide reasonable values and detect potential errors. Especially, we focus on automatically discovering minimal CCFDs. In this paper, we present context relativity to measure the relationship of CFDs. The overlap of the related CFDs can provide reasonable values which result in more accuracy consistency repairing, and some related CFDs are combined into CCFDs.Moreover,we prove that discovering minimal CCFDs is NP-complete and we design the precise method and the heuristic method. We also present the dominating value to facilitate the process in both the precise method and the heuristic method. Additionally, the context relativity of the CFDs affects the cleaning results. We will give an approximate threshold of context relativity according to data distribution for suggestion. The repairing results are approvedmore accuracy, even evidenced by our empirical evaluation.     

Mining functional dependencies from data

In this paper, we propose an efficient rule discovery algorithm, called FD_Mine, for mining functional dependencies from data. By exploiting Armstrong’s Axioms for functional dependencies, we identify equivalences among attributes, which can be used to reduce both the size of the dataset and the number of functional dependencies to be checked. We first describe four effective pruning rules that reduce the size of the search space. In particular, the number of functional dependencies to be checked is reduced by skipping the search for FDs that are logically implied by already discovered FDs. Then, we present the FD_Mine algorithm, which incorporates the four pruning rules into the mining process. We prove the correctness of FD_Mine, that is, we show that the pruning does not lead to the loss of useful information. We report the results of a series of experiments. These experiments show that the proposed algorithm is effective on 15 UCI datasets and synthetic data.     

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.     

基于内容感知发现XML条件函数依赖

针对XML函数依赖(XFD)不能充分检测XML局部数据源语义上的数据不一致,借鉴关系数据库中条件函数依赖(CFD)的概念,并根据XML自身结构和约束特性,提出了基于内容感知发现(CAD)XML条件函数依赖(XCFD),CAD使用隐藏在数据值中的内容发现局部XML文档的XCFDs,检测异构数据源中数据一致性,提高数据的质量,并给出了详细的算法,同时引入修剪规则集减少搜索点阵和候选的XCFD的数量,提高算法的效率,使得XCFD无冗余、最小化.通过案例研究表明,基于CAD方法发现的XCFD比现有XFD发现更多的函数依赖和语义约束.     

The theory of functional and template dependencies

Template dependencies were introduced by Sadri and Ullman [17] to generalize existing forms of data dependencies. It was hoped that by studying a large and natural class of dependencies, we could solve the inference problem for these dependencies, while that problem was elusive for restricted subsets of the template dependencies, such as embedded multivalued dependencies. At about the same time, other generalizations of known dependency forms were developed, such as the implicational dependencies of Fagin [11] and the algebraic dependencies of Yannakakis and Papadimitriou [20]. Unlike the template dependencies, the latter forms include the functional dependencies as special cases. In this paper we show that no nontrivial functional dependency follows from template dependencies, and we characterize those template dependencies that follow from functional dependencies. We then give a complete set of axioms for reasoning about combinations of functional and template dependencies. As a result, template dependencies augmented by functional dependencies can serve as a substitute for the more general implicational or algebraic dependencies, providing the same ability to represent those dependencies that appear ‘in nature’, while providing a somewhat simpler notation and set of axioms than the more general classes.     

On PAC learnability of functional dependencies

This paper proposes a kind of probably approximately correct (PAC) learning framework for inferring a set of functional dependencies (FDs) from example tuples. A simple algorithm is considered that outputs a set of all FDs which hold in a set of example tuples. Letr be a relation (a set of tuples). We define the error for a set of FDsFS as the minimum Σ _t∈ν; where ν (ν ⊂r) is a set such thatFS holds inr − ν, andP(t) denotes the probability that tuplet is picked fromr. Our attention is focused on the sample complexity, and we show that the number of example tuples required to infer a set of FDs whose error does not exceed ω with probability at least 1 − δ under an arbitrary probability distribution is. Tatsuya Akutsu, Ph. D.: He is an associate professor of Department of Computer Science, Gunma University. He received the B. E. degree in 1984, the M. E. degree in 1986 and the Dr. Eng. degree in 1989 from The University of Tokyo. From 1989 to 1994, he was with Mechanical Engineering Laboratory, MITI, Japan. His research interests are design and analysis of algorithms, computational learning theory and bioinformatics.     

Interval-based temporal functional dependencies: specification and verification

In the temporal database literature, every fact stored in a database may be equipped with two temporal dimensions: the valid time, which describes the time when the fact is true in the modeled reality, and the transaction time, which describes the time when the fact is current in the database and can be retrieved. Temporal functional dependencies (TFDs) add valid time to classical functional dependencies (FDs) in order to express database integrity constraints over the flow of time. Currently, proposals dealing with TFDs adopt a point-based approach, where tuples hold at specific time points, to express integrity constraints such as “for each month, the salary of an employee depends only on his role”. To the best of our knowledge, there are no proposals dealing with interval-based temporal functional dependencies (ITFDs), where the associated valid time is represented by an interval and there is the need of representing both point-based and interval-based data dependencies. In this paper, we propose ITFDs based on Allen’s interval relations and discuss their expressive power with respect to other TFDs proposed in the literature: ITFDs allow us to express interval-based data dependencies, which cannot be expressed through the existing point-based TFDs. ITFDs allow one to express constraints such as “employees starting to work the same day with the same role get the same salary” or “employees with a given role working on a project cannot start to work with the same role on another project that will end before the first one”. Furthermore, we propose new algorithms based on B-trees to efficiently verify the satisfaction of ITFDs in a temporal database. These algorithms guarantee that, starting from a relation satisfying a set of ITFDs, the updated relation still satisfies the given ITFDs.     

Independent database schemes under functional and inclusion dependencies

In a context considering in a unique framework all the relations in a database, by means of the notion of global consistency, independent database schemes allow enforcement of constraints to be performed locally, thus providing independent updatability of the various relations. Independent schemes have hitherto been studied in the presence of functional and join dependencies. In this paper the definition is extended and some characterizations are given for schemes whose sets of constraints contain functional and inclusion dependencies.An extended abstract of this paper appears in the Proceedings of the Thirteenth International Conference on Very Large Data Bases, Brighton, England, 1–4 September 1987, pp. 159–166. The work of the first author was supported byMinistero dell'Università e della Ricerca Scientifica e Tecnologica, within the Project Metodi formali e strumenti per basi di dati evolute and the work of the second author by the Natural Sciences and Engineering Research Council of Canada. Part of this work was performed when the first author was with IASI-CNR and then with Università di Napoli.     

Reasoning about programs

This paper describes a theorem prover that embodies knowledge about programming constructs, such as numbers, arrays, lists, and expressions. The program can reason about these concepts and is used as part of a program verification system that uses the Floyd-Naur explication of program semantics. It is implemented in the qa4 language; the qa4 system allows many pieces of strategic knowledge, each expressed as a small program, to be coordinated so that a program stands forward when it is relevant to the problem at hand. The language allows clear, concise representation of this sort of knowledge. The qa4 system also has special facilities for dealing with commutative functions, ordering relations, and equivalence relations; these features are heavily used in this deductive system. The program interrogates the user and asks his advice in the course of a proof. Verifications have been found for Hoare's FIND program, a real-number division algorithm, and some sort programs, as well as for many simpler algorithms. Additional theorems have been proved about a pattern matcher and a version of Robinson's unification algorithm. The appendix contains a complete, annotated listing of the deductive system and annotated traces of several of the deductions performed by the system.     

Reasoning about equality

This note contains a set of six theorems that can be used to assess the ability of a theorem-proving system to reason about equality. The six theorems are graduated in terms of difficulty: they range from fairly trivial to quite difficult. They do not cover all aspects of equality reasoning, but they have proved useful to us in developing our system.This work was supported in part by National Science Foundation grant MCS82-07496 and in part by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.     

Exploiting functional dependencies in declarative problem specifications

In this paper we tackle the issue of the automatic recognition of functional dependencies among guessed predicates in constraint problem specifications. Functional dependencies arise frequently in pure declarative specifications, because of the intermediate results that need to be computed in order to express some of the constraints, or due to precise modeling choices, e.g., to provide multiple viewpoints of the search space in order to increase constraint propagation. In either way, the recognition of dependencies greatly helps solvers, allowing them to avoid spending search on unfruitful branches, while maintaining the highest degree of declarativeness. By modeling constraint problem specifications as second-order formulae, we provide a characterization of functional dependencies in terms of semantic properties of first-order ones, and prove undecidability of the problem of their recognition. Despite such negative result, we advocate the (in many cases effective) possibility of using automated tools to mechanize this task. Additionally, we show how suitable search procedures can be automatically synthesized in order to exploit recognized dependencies. We present opl examples of various problems, taken from bio-informatics, planning and resource allocation, and show how in many cases opl greatly benefits from the addition of such search procedures. Moreover, we also give evidence that writing sophisticated ad-hoc search procedures that handle dependencies exploiting the peculiarities of the particular problem is a very difficult and error-prone task which in many cases does not seem to pay-off.     

Privacy-preserving publishing microdata with full functional dependencies

Data publishing has generated much concern on individual privacy. Recent work has shown that different background knowledge can bring various threats to the privacy of published data. In this paper, we study the privacy threat from the full functional dependency (FFD) that is used as part of adversary knowledge. We show that the cross-attribute correlations by FFDs (e.g., Phone → Zipcode) can bring potential vulnerability. Unfortunately, none of the existing anonymization principles (e.g., k-anonymity, ?-diversity, etc.) can effectively prevent against an FFD-based privacy attack. We formalize the FFD-based privacy attack and define the privacy model, (d,?)-inference, to combat the FD-based attack. We distinguish the safe FFDs that will not jeopardize privacy from the unsafe ones. We design robust algorithms that can efficiently anonymize the microdata with low information loss when the unsafe FFDs are present. The efficiency and effectiveness of our approach are demonstrated by the empirical study.     

Thinking about Reasoning about Knowledge

Minds and Machines -     

Mining frequent conjunctive queries using functional and inclusion dependencies

We address the issue of mining frequent conjunctive queries in a relational database, a problem known to be intractable even for conjunctive queries over a single table. In this article, we show that mining frequent projection-selection-join queries becomes tractable if joins are performed along keys and foreign keys, in a database satisfying functional and inclusion dependencies, under certain restrictions. We note that these restrictions cover most practical cases, including databases operating over star schemas, snow-flake schemas and constellation schemas. In our approach, we define an equivalence relation over queries using a pre-ordering with respect to which the support is shown to be anti-monotonic. We propose a level-wise algorithm for computing all frequent queries by exploiting the fact that equivalent queries have the same support. We report on experiments showing that, in our context, mining frequent projection-selection-join queries is indeed tractable, even for large data sets.     

Reasoning about action and change

Reasoning about change is a central issue in research on human and robot planning. We study an approach to reasoning about action and change in a dynamic logic setting and provide a solution to problems which are related to the Frame problem. Unlike most work on the frame problem the logic described in this paper is monotonic. It (implicitly) allows for the occurrence of actions of multiple agents by introducing non-stationary notions of waiting and test. The need to state a large number of frame axioms is alleviated by introducing a concept of chronological preservation to dynamic logic. As a side effect, this concept permits the encoding of temporal properties in a natural way. We compare the relative merits of our approach and non-monotonic approaches as regards different aspects of the frame problem. Technically, we show that the resulting extended systems of propositional dynamic logic preserve (weak) completeness, finite model property and decidability.     

Update operations in deductive databases with functional dependencies

We study the problem of updating intensional relations in the framework of deductive databases on which integrity constraints (specifically functional dependencies) are defined. First, a formalization of a model-theoretic semantics of updates is provided: the notions ofrepresentability, consistency anddeterminism are introduced to characterize the various cases. Then, a proof-theoretic approach, based on a variant of resolution integrated with the chase procedure, is defined, showing that the method exactly captures the above notions. It turns out that using functional dependencies it is possible to resolve potential ambiguities in several practical cases. Also, precomputations can be performed at definition time to execute update requests more efficiently.Work partially supported by Consiglio Nazionale delle Ricerche, within Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo, LRC Logidata+, and by System & Management S.p.A.A preliminary version of this paper appeared in [33].     

Axiomatizing functional dependencies in the Higher-Order Entity-Relationship Model

A finite axiomatization of functional dependencies on conceptual database schemata is presented which naturally generalizes the well-known Armstrong axioms. The underlying conceptual data model is the Higher-Order Entity-Relationship Model.