The theory of functional and subset dependencies over relational expressions

A formal system for reasoning about functional dependencies (FDs) and subset dependencies (SDs) defined over relational expressions is described. An FD e:X → Y indicates that Y is functionally dependent on X in the relation denoted by expression e; an SD e ? f indicates that the relation denoted by e is a subset of that denoted by f. The system is shown to be sound and complete by resorting to the analytic tableaux method. Applications of the system include the problem of determining if a constraint of a subschema is implied by the constraints of the base schema and the development of database design methodologies similar to normalization.     

Group decision-making procedure based on incomplete reciprocal relations

Xu (Int J Approx Reason 36:261–270, 2004) introduced the concepts of incomplete reciprocal relation and additive consistent incomplete reciprocal relation. The aim of this paper is to develop a novel procedure for group decision making with incomplete reciprocal relations. The procedure utilizes each given incomplete reciprocal relation to construct an auxiliary reciprocal relation based on additive transitivity, and then aggregates directly these auxiliary reciprocal relations into a collective auxiliary reciprocal relation. After that, based on the collective auxiliary reciprocal relation, a simple linear system of equations is established for ranking alternatives. Finally, a numerical example is given to illustrate the developed procedure.     

Membership problems for data dependencies in relational expressions

In relational databases, a query can be formulated in terms of a relational algebra expression using projection, selection, restriction, cross product and union. In this paper, we consider a problem, called the membership problem, of determining whether a given dependency d is valid in a given relational expression E over a given database scheme R that is, whether every instance of the view scheme defined by E satisfies d (assuming that the underlying constraints in R are always satisfied).Consider the case where each relation scheme in R is associated with functional dependencies (FDs) as constraints, and d is an FD. Then the complement of the membership problem is NP-complete. However, if E contains no union, then the membership problem can be solved in polynomial time. Furthermore, if E contains neither a union nor a projection, then we can construct in polynomial time a cover for valid FDs in E, that is, a set of FDs which implies every valid FD in E.Consider the case where each relation scheme in R is associated with multivalued dependencies (MVDs) as well as FDs, and d is an FD or an MVD. Even if E consists of selections and cross products only, the membership problem is NP-hard. However, if E contains no union, and each relation scheme name in R occurs in E at most once, then the membership problem can be solved in polynomial time. As a corollary of this result, it can be determined in polynomial time whether a given FD or MVD is valid in $\text{R}{}_1\text{???R}{}_{\mathrm{s}}$, where R₁,…,R_s are relation schemes with FDs and MVDs, and $\text{R}{}_{\mathrm{i}}\text{?R}{}_{\mathrm{j}}$ is the natural join of R_i and R_j.     

Functional dependencies among Boolean dependencies

In this paper, we consider functional dependencies among Boolean dependencies (BDs, for short). Armstrong relations are defined for BDs (called BD-Armstrong relations). For BDs, two necessary and sufficient conditions for the existence of BD-Armstrong relations are given. A necessary and sufficient condition for the existence of Armstrong relations for functional dependencies (FDs, for short) is given, which in some sense is more convenient than the condition given in [3]. We give an algorithm that solves the problem of deciding if two BDs imply the same set of functional dependencies. If the BDs are given in perfect disjunctive normal form, then the algorithm requires only polynomial time. Although Mannila and Räihä have shown that for some relations exponential time is needed for computing any cover of the set of FDs defined in this relation, as a consequence, we show that the problem of deciding if two relations satisfy the same set of FDs can be solved in polynomial time. Another consequence is a new correspondence of the families of functional dependencies to the families of Sperner systems. By this correspondence, the estimate of the number of databases given previously in [6] is improved. It is shown that there is a one-to-one correspondence between the closure of the FDs that hold in a BD and its so-calledbasic cover. As applications of basic covers, we obtain a representation of a key, the family of minimal keys and a representation of canonical covers.This research was supported by the Hungarian Foundation for Scientific Research, Grant Nos. OTKA 2575, 2149.     

Fast in-place verification of data dependencies

Several fast and space-optimal sequential and parallel algorithms for solving the satisfaction problem of functional and multivalued dependencies (FDs and MVDs) are presented. Two frameworks to verify an MVD for a relation and their implementation by exploring the existing fast space-optimal sorting techniques are described. The space optimality means that only a constant amount of extra memory space is needed for the sequential implementations, and O(M) amount of extra memory space for parallel algorithms that use M processors. This feature makes the algorithms attractive whenever space is a critical resource and I/O transfers should be reduced to the minimal, as is often the case for relational database systems. The time requirements for in-place FD and MVD verification are given in terms of M and of N, which is the number of tuples in a relation. The effect of relation modification on FD and MVD verification is examined     

Incomplete interval-valued intuitionistic fuzzy preference relations

The aim of this paper is to investigate decision making problems with interval-valued intuitionistic fuzzy preference information, in which the preferences provided by the decision maker over alternatives are incomplete or uncertain. We define some new preference relations, including additive consistent incomplete interval-valued intuitionistic fuzzy preference relation, multiplicative consistent incomplete interval-valued intuitionistic fuzzy preference relation and acceptable incomplete interval-valued intuitionistic fuzzy preference relation. Based on the arithmetic average and the geometric mean, respectively, we give two procedures for extending the acceptable incomplete interval-valued intuitionistic fuzzy preference relations to the complete interval-valued intuitionistic fuzzy preference relations. Then, by using the interval-valued intuitionistic fuzzy averaging operator or the interval-valued intuitionistic fuzzy geometric operator, an approach is given to decision making based on the incomplete interval-valued intuitionistic fuzzy preference relation, and the developed approach is applied to a practical problem. It is worth pointing out that if the interval-valued intuitionistic fuzzy preference relation is reduced to the real-valued intuitionistic fuzzy preference relation, then all the above results are also reduced to the counterparts, which can be applied to solve the decision making problems with incomplete intuitionistic fuzzy preference information.     

A note on group decision-making procedure based on incomplete reciprocal relations

In a very recent paper by Xu and Chen (Soft Comput 12:515–521, 2008), a novel procedure for group decision making with incomplete reciprocal relations was developed. In this note, we examine the function between the fuzzy preference relation and its corresponding priority vector developed by Xu and Chen with a numerical example and show that the function does not hold in general cases. Then, we deduce an exact function between the additive transitivity fuzzy preference relation and its corresponding priority vector. Based on this, we develop a procedure for the decision making with an incomplete reciprocal relation and also develop a procedure for the group decision making with incomplete reciprocal relations. In order to compare the performances of our method with Xu and Chen’s method in fitting the reciprocal relation, we introduce some criteria. Theoretical analysis and numerical examples have shown that the function deduced by us is more reasonable and effective than Xu and Chen’s.     

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     

Multi-criteria group decision making with incomplete hesitant fuzzy preference relations

In order to simulate the hesitancy and uncertainty associated with impression or vagueness, a decision maker may give her/his judgments by means of hesitant fuzzy preference relations in the process of decision making. The study of their consistency becomes a very important aspect to avoid a misleading solution. This paper defines the concept of additive consistent hesitant fuzzy preference relations. The characterizations of additive consistent hesitant fuzzy preference relations are studied in detail. Owing to the limitations of the experts’ professional knowledge and experience, the provided preferences in a hesitant fuzzy preference relation are usually incomplete. Consequently, this paper introduces the concepts of incomplete hesitant fuzzy preference relation, acceptable incomplete hesitant fuzzy preference relation, and additive consistent incomplete hesitant fuzzy preference relation. Then, two estimation procedures are developed to estimate the missing information in an expert's incomplete hesitant fuzzy preference relation. The first procedure is used to construct an additive consistent hesitant fuzzy preference relation from the lowest possible number, (n − 1), of pairwise comparisons. The second one is designed for the estimation of missing elements of the acceptable incomplete hesitant fuzzy preference relations with more known judgments. Moreover, an algorithm is given to solve the multi-criteria group decision making problem with incomplete hesitant fuzzy preference relations. Finally, a numerical example is provided to illustrate the solution processes of the developed algorithm and to verify its effectiveness and practicality.     

On utilizing variables for specifying FDs in data-centric XML documents

We are interested in specifying functional dependencies (FDs) for data-centric XML documents (XML documents that are used mainly for data storage). FDs are a natural constraint. Specifying FDs for XML documents is more difficult because unlike relational databases, XML documents do not have uniform structures. This paper introduces XML Template Functional Dependencies (XTFDs), which are able to specify FDs for XML documents. This paper also presents a necessary and sufficient condition for an XTFD to cause data redundancy in XML documents. Further, we propose Attribute Rule and Text String Rule as two procedures that can be repeatedly applied to remove redundancy caused by XTFDs. In addition, we prove that if an XML document has data redundancy with respect to an FD specified by using the tree tuple approach, it would have data redundancy with respect to an XTFD and show by example that XTFDs can specify some FDs for XML documents that the tree tuple approach cannot.     

Generic semantics of feature diagrams

Feature Diagrams (FDs) are a family of popular modelling languages used to address the feature interaction problem, particularly in software product lines, FDs were first introduced by Kang as part of the FODA (Feature-Oriented Domain Analysis) method back in 1990. Afterwards, various extensions of FODA FDs were introduced to compensate for a purported ambiguity and lack of precision and expressiveness. However, they never received a formal semantics, which is the hallmark of precision and unambiguity and a prerequisite for efficient and safe tool automation.The reported work is intended to contribute a more rigorous approach to the definition, understanding, evaluation, selection and implementation of FD languages. First, we provide a survey of FD variants. Then, we give them a formal semantics, thanks to a generic construction that we call Free Feature Diagrams (FFDs). This demonstrates that FDs can be precise and unambiguous. This also defines their expressiveness. Many variants are expressively complete, and thus the endless quest for extensions actually cannot be justified by expressiveness. A finer notion is thus needed to compare these expressively complete languages. Two solutions are well-established: succinctness and embeddability, that express the naturalness of a language. We show that the expressively complete FDs fall into two succinctness classes, of which we of course recommend the most succinct. Among the succinct expressively complete languages, we suggest a new, simple one that is not harmfully redundant: Varied FD (VFD). Finally, we study the execution time that tools will need to solve useful problems in these languages.     

Representation of 3D surfaces by two-variable Fourier descriptors

A method for generating two-variable 3D FDs directly from a striped lighting system is developed. An iterative algorithm is proposed to compute the two-variable 3D FDs for both axisymmetric and nonaxisymmetric objects and a formula for convergence test is derived. Experiments conducted for a set of 3D objects show that the iterative algorithm converges very quickly and the two-variable 3D FD representations are attained accurately     

Sample size calculations for a functional human motion analysis: Application to vehicle ingress discomfort prediction

The ease of entering a vehicle, known as ingress, is one of the important ergonomic factors that car manufacturers consider during the process of vehicle design. Manufacturers frequently conduct human subject tests to assess ingress discomfort for different vehicle designs. Using subject tests, manufacturers are able to estimate the proportion of participants that report that they are discomfortable entering a vehicle, referred to in this paper as fraction disaccommodated (FD). Manufacturers then conduct statistical tests in order to determine if the FD of two vehicle designs are significantly different, and to determine the required sample size in testing the FD difference between two vehicle designs under pre-specified testing power. Since conducting human subject tests is often expensive and time consuming, another alternative is to estimate the FD using simulated human motion data. Determining the number of simulations that is required is an important statistical question that is dependent on the prediction performance of the simulation analysis. In this paper, a dual bootstrap approach is proposed to obtain the standard deviation of the estimated FD based on functional predictors. This standard deviation is then used to calculate the power in testing the difference between two estimated FDs.     

XML schema refinement through redundancy detection and normalization

As XML becomes increasingly popular, XML schema design has become an increasingly important issue. One of the central objectives of good schema design is to avoid data redundancies: redundantly stored information can lead not just only to a higher data storage cost but also to increased costs for data transfer and data manipulation. Furthermore, such data redundancies can lead to potential update anomalies, rendering the database inconsistent. One strategy to avoid data redundancies is to design redundancy-free schema from the start on the basis of known functional dependencies. We observe that XML databases are often “casually designed” and XML FDs may not be determined in advance. Under such circumstances, discovering XML data redundancies from the data itself becomes necessary and is an integral part of the schema refinement (or re-design) process. We present the design and implementation of the first system, DiscoverXFD, for efficient discovery of XML data redundancies. It employs a novel XML data structure and introduces a new class of partition-based algorithms. The XML data redundancies are defined on the basis of a new notion of XML functional dependency (XML FD) that (1) extends previous notions by incorporating set elements into the XML FD specification, and (2) maintains tuple-based semantics through the novel concept of Generalized Tree Tuple (GTT). Using this comprehensive XML FD notion, we introduce a new normal form (GTT-XNF) for XML documents, and provide comprehensive comparisons with previous studies. Given the set of data redundancies (in the form of redundancy-indicating XML FDs) discovered by DiscoverXFD, we describe a normalization algorithm for converting any original XML schema into one in GTT-XNF.     

Ordered functional dependencies in relational databases

We extend the relational data model to incorporate linear orderings into data domains, which we call the ordered relational model. The conventional Functional Dependencies (FDs) are examined in the context of ordered relational databases by using the notion of System Ordering Independence (SOI), which refers to the desirable scenario that the ordering of tuples in a relation is independent of the implementation of the underlying DBMS. We also extend Armstrong's axiom system for FDs to object relations, which are a subclass of ordered relations that allow us to view tuples as objects. We formally define Ordered Functional Dependencies (OFDs) for the extended model by means of two possible extensions of domains, pointwise-orderings and lexicographical orderings. We first present a sound and complete axiom system for OFDs in the case of pointwise-orderings and then establish a sound and complete set of chase rules for OFDs in the case of lexicographical orderings. Our main result shows that the implication problems for both cases of OFDs are decidable, and that it is linear time for the case of pointwise-orderings.     

LR最小替换集求解算法研究

文中对Ｄ．Ｍａｉｅｒ提出的关于关系数据库中的ＬＲ最小集的结构进行了分析，提出了一个比“ＬＲ最小集”更为简化的ＦＤ集的覆盖－ＬＲ最小替换集。给出了一个求ＬＲ最小替换集的多项式时间算法。修正了Ｄ．Ｍａｉｅｒ在其文中给出的一个ＦＤ集为最优覆盖的必要条件。     

Fractal texture analysis of perfusion lung scans.

The purpose of this study is to investigate if fractal texture analysis can assist in the diagnostic interpretation of perfusion lung scans. Forty-five perfusion scans were acquired from patients with clinical suspicion of acute pulmonary embolism (PE) who underwent pulmonary angiography for final diagnosis. Fractal texture analysis was performed on 270 regions of interest (ROIs) extracted from the posterior view of the lung scans. Specifically, there were 94 normally perfused ROIs and 176 abnormal ROIs representing various lung diseases including PE and obstructive pulmonary disease (OPD). The average fractal dimension (FD) of normal ROIs was statistically significantly higher than that of abnormal ROIs. Furthermore, the FDs of abnormal ROIs with PE were significantly lower than the FDs of ROIs with OPD present.     

Incomplete interval fuzzy preference relations and their applications

This paper investigates incomplete interval fuzzy preference relations. A characterization, which is proposed by Herrera-Viedma et al. (2004), of the additive consistency property of the fuzzy preference relations is extended to a more general case. This property is further generalized to interval fuzzy preference relations (IFPRs) based on additive transitivity. Subsequently, we examine how to characterize IFPR. Using these new characterizations, we propose a method to construct an additive consistent IFPR from a set of n − 1 preference data and an estimation algorithm for acceptable incomplete IFPRs with more known elements. Numerical examples are provided to illustrate the effectiveness and practicality of the solution process.     

An improved algorithm based on subset closures for synthesizing arelational database scheme

An algorithm for synthesizing a better relational database scheme in elementary key normal form (EKNF) is developed. This algorithm eliminates not only extraneous attributes and other redundancies, but also superfluities from a given set of functional dependences (FDs), based primarily on subset closures, Hamiltonian cycles of FDs, and equivalent subsets of attributes. Following this algorithm, a better LR-minimum FD covering is obtained. A more practical and efficient method for designing a relational database scheme in EKNF is then provided. The time complexity of the algorithm is polynomial     

Group decision making with incomplete fuzzy linguistic preference relations

The aim of this paper is to propose a procedure to estimate missing preference values when dealing with incomplete fuzzy linguistic preference relations assessed using a two‐tuple fuzzy linguistic approach. This procedure attempts to estimate the missing information in an individual incomplete fuzzy linguistic preference relation using only the preference values provided by the respective expert. It is guided by the additive consistency property to maintain experts' consistency levels. Additionally, we present a selection process of alternatives in group decision making with incomplete fuzzy linguistic preference relations and analyze the use of our estimation procedure in the decision process. © 2008 Wiley Periodicals, Inc.