Justification for inclusion dependency normal form

Functional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. In this paper, we address the issue of normalization in the presence of FDs and INDs and, in particular, the semantic justification for an inclusion dependency normal form (IDNF), which combines the Boyce-Codd normal form with the restriction on the INDs that they be noncircular and key-based. We motivate and formalize three goals of database design in the presence of FDs and INDs: noninteraction between FDs and INDs, elimination of redundancy and update anomalies, and preservation of entity integrity. We show that (as for FDs), in the presence of INDs, being free of redundancy is equivalent to being free of update anomalies. Then, for each of these properties, we derive equivalent syntactic conditions on the database design. Individually, each of these syntactic conditions is weaker than IDNF and the restriction that an FD is not embedded in the right-hand side of an IND is common to three of the conditions. However, we also show that, for these three goals of database design to be satisfied simultaneously, IDNF is both a necessary and a sufficient condition     

Characterizations for the regular prefix codes and related families

Intrinsic characterizations by means of analogues of regular expressions are given for six families of regular languages related to the prefix codes, namely their reversals and their closure under union, the right and left ideals, and their complements. First, a characterization for the regular prefix codes is obtained, which is then used to characterize the other families. Characterizations by finite automata are also presented.This research has been sponsored in part by FINEP, CNPq and Canadian NRC.     

Repairing XML functional dependency violations

We study the problem of repairing XML functional dependency violations by making the smallest modifications in terms of repair cost. Our cost model assigns a weight to each leaf node in the XML document, and the cost of a repair is measured by the total weight of the modified nodes. We define an optimum repair as the repair with the minimum cost among all of the repairs. We prove lower and upper bounds for the optimum XML repair problem. We show that, in practice, it is beyond reach to find the optimum repairs; this problem is already NP-complete for a setting with a fixed DTD, a fixed set of functional dependencies, and equal weights for all of the nodes in the XML document. Instead, we provide an efficient two-step heuristic method to repair XML functional dependency violations. First, the initial violations are captured and fixed by leveraging the conflict hypergraph. Second, the remaining conflicts are resolved by modifying the violating nodes and their related nodes called determinants in a way that guarantees no new violations. We implement our method and evaluate it on synthetic and real-life data. The experimental results demonstrate that our algorithm scales well and is effective at improving data quality.     

Some characterizations of finitely specifiable implicational dependency families

Let r be a relation for the relation scheme R(A₁,A₂,…,A_n); then we define Dom(r) to be Dom_r(A₁)×Dom_r(A₂)×…×Dom_r(A_n), where Dom_r(A_i) for each i is the set of all ith coordinates of tuples of r. A relation s is said to be a substructure of the relation r if and only if Dom(s)∩r = s.The following theorems analogous to Tarski-Fraisse-Vaught's characterizations of universal classes are proved: (i) An implicational dependency family (ID-family) F over the relation scheme R is finitely specifiable if and only if there exists a finite number of relations r₁,r₂,…,r_m for R such that r ∈ F if and only if no r_i is isomorphic to a substructure of r. (ii) F is finitely specifiable if and only if there exists a natural number k such that r ∈ F whenever F contains all substructures of r with at most k elements.We shall use these characterizations to obtain a new proof for Hull's (1984) characterization of finitely specifiable ID-families.     

Characterizations of transductions defined by abstract families of transducers

Two characterizations of transductions defined by abstract families of transducers are presented. The first characterization is in terms of languages defined by acceptors derived from the transducers when the output structure is removed. The second characterization is in terms of sets of pairs of words satisfying certain closure operations.     

从合取范式到析取范式的转换研究

为了解决粗糙集分辨函数的计算、概念格中内涵缩减的计算、逻辑程序设计的规则简化等问题,抽象出了从合取范式到析取范式转换这一核心问题。提出了利用极小覆盖来实现从合取范式到析取范式的转换,给出了一个增量式的算法。为了扩大范式转换的使用范围,定义了伪合取范式,并给出伪合取范式到析取范式的转换方法。     

Generalized normal form for rewriting P systems

P systems, introduced by Gh. Păun [9] as a new theoretical model for molecular computations, are based on the notion of membrane structure. Several variants of P systems have been proposed and shown to be computationally universal. One of such variant is the rewriting P systems, where we consider string-objects and process them using rewriting rules. Particular cases of normal forms for rewriting P systems were proposed in [11–13]. In this work we introduce the generalized normal form for rewriting P systems which take into consideration the depth of the membrane structure and the number of rewriting rules present in each membrane. Such generalized normal forms are given for rewriting P systems with priorities, and for partially parallel rewriting P systems. In this way, several results from the literature are generalized and improved. Received: 14 March 2002 / 5 June 2002     

Observability quadratic normal form for discrete-time systems

This note deals with quadratic observability normal form for nonlinear discrete-time single-input-single-output (SISO) system. First of all, the main concept of quadratic equivalence with respect to the observability property, is introduced for discrete-time systems. Subsequently, normal form structure for discrete time system is developed for system with unobservable linear approximation in one direction. Finally, the effect of the so-called resonant terms on the observer design and synchronization of chaotic systems is pointed out in an illustrative example.     

A normal form theorem for label grammars

We characterize the images of Szilard languages under decreasing homomorphisms using so-called label grammars and show that each -free label language is in fact the coding of some Szilard language. This result shows that decreasing homomorphisms do not have more generating power on Szilard languages than codings, except that they generate the empty word. Label grammars naturally define a subclass of labelled Petri nets for which, unlike in the general case, it is now possible to eliminate -labelled transitions.     

Two normal form theorems for CSP programs

We define two normal forms for CSP programs. In the First Normal Form, each process contains only one I/O repetitive command and all its I/O commands appear as guards of this command. In the Second Normal Form, all guards of this I/O repetitive command are I/O guards. We describe an inductive method that transforms any CSP program into an equivalent program in first or second normal form. The notion of equivalence is discussed. It is shown that no transformation into second normal form can preserve deadlock freedom.     

A sampled normal form for feedback linearization

This paper discusses the problem of preserving approximated feedback linearization under digital control. Starting from a partially feedback linearizable affine continuous-time dynamics, a digital control procedure which maintains the dimension of the maximally feedback linearizable part up to any order of approximation with respect to the sampling period is proposed. The result is based on the introduction of a sampled normal form, a canonical structure which naturally appears when studying feedback linearization.This work was supported by an Italian 40% M.U.R.S.T. grant and a French M.E.N.-D.R.E.D. grant.     

基于条件函数依赖的隐私保护模型

数据拥有者发布的数据中如果包含条件函数依赖会导致数据的隐私受到攻击,由条件函数依赖产生的属性间的关联会带来潜在的隐私泄露问题。针对现有的隐私保护方法均无法保护包含条件函数依赖的数据的隐私,形式化地定义了基于条件函数依赖的隐私攻击,提出了隐私保护模型l-deduction来对包含条件函数依赖的数据进行隐私保护;并设计了相应的匿名算法来实现l-deduction模型。理论分析和实验结果表明,该方法既能保护包含条件函数依赖的数据的隐私,又具有较小的信息损失度。     

基于依赖结构的功能测试集排序方法

为解决依赖结构优先级在测试用例权值相等时存在的问题,针对流行的深度优先搜索算法进行改进。通过结合测试用例之间的功能依赖和测试用例的代码覆盖率,推导出有向无环图和算法流程图;利用推导出的有向无环图和流程图,使用权值和代码覆盖率算出最长路径作为测试集,以达到缩减测试集,同时保证代码覆盖率的目的。结合实例,将依赖结构优先级和现存的技术进行对比,验证了依赖结构优先级技术在提高错误检测率方面的可行性和实用性。     

Sampling from repairs of conditional functional dependency violations

Violations of functional dependencies (FDs) and conditional functional dependencies (CFDs) are common in practice, often indicating deviations from the intended data semantics. These violations arise in many contexts such as data integration and Web data extraction. Resolving these violations is challenging for a variety of reasons, one of them being the exponential number of possible repairs. Most of the previous work has tackled this problem by producing a single repair that is nearly optimal with respect to some metric. In this paper, we propose a novel data cleaning approach that is not limited to finding a single repair, namely sampling from the space of possible repairs. We give several motivating scenarios where sampling from the space of CFD repairs is desirable, we propose a new class of useful repairs, and we present an algorithm that randomly samples from this space in an efficient way. We also show how to restrict the space of repairs based on constraints that reflect the accuracy of different parts of the database. We experimentally evaluate our algorithms against previous approaches to show the utility and efficiency of our approach.     

Partial orders and Jordan normal form

Consideration is given to the relation between the structure of the acyclic binary relation and the adjacency matrix of its corresponding graph. In this case, the existing methods for studying the binary relations and their corresponding graphs in terms of the spectrum, that is, the set of eigenvalues, of the adjacency matrix are inapplicable because for the acyclic relations this matrix is nilpotent and its spectrum is identically zero. Therefore, a more refined characteristic of the matrix is required. The present paper considers the Jordan normal form (JNF) as such.     

A solver for QBFs in negation normal form

Various problems in artificial intelligence can be solved by translating them into a quantified boolean formula (QBF) and evaluating the resulting encoding. In this approach, a QBF solver is used as a black box in a rapid implementation of a more general reasoning system. Most of the current solvers for QBFs require formulas in prenex conjunctive normal form as input, which makes a further translation necessary, since the encodings are usually not in a specific normal form. This additional step increases the number of variables in the formula or disrupts the formula’s structure. Moreover, the most important part of this transformation, prenexing, is not deterministic. In this paper, we focus on an alternative way to process QBFs without these drawbacks and describe a solver, $\ensuremath{\sf qpro}Various problems in artificial intelligence can be solved by translating them into a quantified boolean formula (QBF) and evaluating the resulting encoding. In this approach, a QBF solver is used as a black box in a rapid implementation of a more general reasoning system. Most of the current solvers for QBFs require formulas in prenex conjunctive normal form as input, which makes a further translation necessary, since the encodings are usually not in a specific normal form. This additional step increases the number of variables in the formula or disrupts the formula’s structure. Moreover, the most important part of this transformation, prenexing, is not deterministic. In this paper, we focus on an alternative way to process QBFs without these drawbacks and describe a solver, , which is able to handle arbitrary formulas. To this end, we extend algorithms for QBFs to the non-normal form case and compare with the leading normal form provers on several problems from the area of artificial intelligence. We prove properties of the algorithms generalized to non-clausal form by using a novel approach based on a sequent-style formulation of the calculus. This paper is based on an extended abstract presented at ECAI 2006 (see [16]). This work was supported by the Austrian Science Fund (FWF) under grant P18019, the Austrian Academic Exchange Service (?AD) under grant Amadée 2/2006, and by the Austrian Federal Ministry of Transport, Innovation and Technology BMVIT and the Austrian Research Promotion Agency FFG under grant FIT-IT-810806.     

A normal form for spider diagrams of order

We develop a reasoning system for an Euler diagram based visual logic, called spider diagrams of order. We define a normal form for spider diagrams of order and provide an algorithm, based on the reasoning system, for producing diagrams in our normal form. Normal forms for visual logics have been shown to assist in proving completeness of associated reasoning systems. We wish to use the reasoning system to allow future direct comparison of spider diagrams of order and linear temporal logic.     

A normal form algorithm for the Brieskorn lattice

This article describes a normal form algorithm for the Brieskorn lattice of an isolated hypersurface singularity. It is the basis of efficient algorithms to compute the Bernstein–Sato polynomial, the complex monodromy, and Hodge-theoretic invariants of the singularity such as the spectral pairs and good bases of the Brieskorn lattice. The algorithm is a variant of Buchberger’s normal form algorithm for power series rings using the idea of partial standard bases and adic convergence replacing termination.