Semantic schema refinements for multilevel schema integration

Within the database field, schema refinements have been proved useful for documentation and maintenance purposes; moreover, schemata describing the reality of interest at different levels of abstraction are extensively used in Computer Aided Software Engineering tools and visual query languages. So, much effort has been spent in analyzing schema transformations and schema refinements. Till now, however, while the syntaxof schema transformations has been deeply investigated, the semantics has been very often neglected. In this paper we present a full formal framework, supporting both the syntax and the semantics of schema refinements. Such a formal framework is used to support a methodology able to merge a set of schemata and the top-down chains of refinement planes produced during their design. The result of this kind of integration, that we call multilevel integration, is an integrated schema plus an associated top-down chain of schemata. The integrated schema and the chain are related to the input schemata by interesting properties, giving rise to a two-dimensional structure useful for exploring the data content of complex information systems.     

Model correspondence as a basis for schema domination

Conceptual schemata each representing some component of a system in the making, can be integrated in a variety of ways. Herein, we explore some fundamental notions of this. In particular, we examine some ways in which integration using correspondence assertions affects the interrelationship of two component schemata. Our analysis of the logic leads us to reject the commonly asserted requirement of constraining correspondence assertions to single predicates from a source schema. Much previous work has focussed on dominance with regard to preservation of information capacity as a primary integration criterion. However, even though it is desirable that the information capacity of a combined schema dominate one or both of its constituent schemata, we here discuss some aspects of why domination based on information capacity alone is insufficient for the integration to be semantically satisfactory, and we provide a framework for detecting mappings that prevent schema domination.     

An Order-Based Theory of Updates for Closed Database Views

The fundamental problem in the design of update strategies for views of database schemata is that of selecting how the view update is to be reflected back to the base schema. This work presents a solution to this problem, based upon the dual philosophies of closed update strategies and order-based database mappings. A closed update strategy is one in which the entire set of updates exhibit natural closure properties, including transitivity and reversibility. The order-based paradigm is a natural one; most database formalisms endow the database states with a natural order structure, under which update by insertion is an increasing operation, and update by deletion is decreasing. Upon augmenting the original constant-complement strategy of Bancilhon and Spyratos – which is an early version of a closed update strategy – with compatible order-based notions, the reflection to the base schema of any update to the view schema which is an insertion, a deletion, or a modification which is realizable as a sequence of insertions and deletions is shown to be unique and independent of the choice of complement. In addition to this uniqueness characterization, the paper also develops a theory which identifies conditions under which a natural, maximal, update strategy exists for a view. This theory is then applied to a ubiquitous example – single-relational schemata constrained by equality-generating dependencies. Within this framework it is shown that for a view defined as a projection of the main relation, the only possibility is that the complement defining the update process is also a projection, and that the reconstruction is based upon functional dependencies.     

Una classe di schemi ricorsivi non-deterministici paralleli

The paper introduces a class of recursive non-deterministic schemata, whose expressive power overcomes the capability of the recursive non-deterministic schemata defined so far. This class is a proper extension of Kowalski“s Predicate Logic, since our formalism allows a procedure declaration schema to have a conjunction rather than a single atomic formula in its left-hand side. It is worth noting that only introducing this feature it becomes possible to express, in a purely syntactic way, complex control structures related both to parallelism (cooperation, synchronization, coroutining, etc.) and to artificial intelligence problems (control of non-determinism via contexts, evaluation strategies, «continuation point» dealing, etc.). Finally the paper shows that the expressive power of the program schemata defined above is maximum.     

Global extensional assertions and local integrity constraints in federated schemata

Integrated access to multiple data sources requires a homogeneous interface provided by a federated schema. Such a federated schema should correctly reflect the semantics of the component schemata of which it is composed. Since the semantics of a database schema is also determined by a set of semantic integrity constraints, a correct schema integration has to deal with integrity constraints existing in the different component schemata. Traditionally, most schema integration approaches solely concentrate on the structural integration of given database schemata. Local integrity constraints are often simply neglected. Their relationship to global extensional assertions, which form the basic integration constraints, are even ignored completely. In this paper, we discuss the impact of global extensional assertions and local integrity constraints on federated schemata. In particular, we point out the correspondence between local integrity constraints and global extensional assertions. The knowledge about the correspondences between the given integrity constraints and extensional assertions can then be utilized for an augmented schema integration process.     

A self-organizing knowledge representation scheme for extensibleheterogeneous information environment

The self-organizing knowledge representation aspects in heterogeneous information environments involving object-oriented databases, relational databases, and rulebases are investigated. The authors consider a facet of self-organizability which sustains the structural semantic integrity of an integrated schemea regardless of the dynamic nature of local schemata. To achieve this objective, they propose an overall scheme for schema translation and schema integration with an object-oriented data model as common data model, and it is shown that integrated schemata can be maintained effortlessly by propagating updates in local schemata to integrated schemata unambiguously     

A class of parallelizing transformations

The paper considers the correctness of a parametric family of parallelizing transformations. The proposed transformations are based on static detection of parallelism and are intended for MIMD computer systems with local memory and data exchanges.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 90–98, September–October, 1991.     

Reducing the search space for conceptual schema transformation

In this paper we focus on the transformation of a conceptual schema into an internal schema. For a given conceptual schema, quite a number of internal schemata can be derived. This number can be reduced by imposing restrictions on internal schemata.

We present a transformation algorithm that can generate internal schemata of several types (including the relational model and the NF² model). Guidance parameters are used to impose further restrictions.

We harmonise the different types of schemata by extending the conceptual language, such that both the conceptual and the internal models can be represented within the same language.     

A Methodology for Data Schema Integration in the Entity Relationship Model

The conceptual design of databases is usually seen as divided into two steps: view modeling, during which user requirements are formally expressed by means of several user oriented conceptual schemata, and schema integration, whose goal is to merge such schemata into a unique global conceptual schema. This paper is devoted to describe a methodology for schema integration. An enriched entity relationship model is chosen as the data model. The integration process consists of three steps: first, several types of conflicts between the different user schemata are checked and solved; second, schemata are merged into a draft integrated schema, that is, third, enriched and restructured according to specific goals.     

Automatic generation of probabilistic relationships for improving schema matching

Schema matching is the problem of finding relationships among concepts across data sources that are heterogeneous in format and in structure. Starting from the “hidden meaning” associated with schema labels (i.e. class/attribute names), it is possible to discover lexical relationships among the elements of different schemata. In this work, we propose an automatic method aimed at discovering probabilistic lexical relationships in the environment of data integration “on the fly”. Our method is based on a probabilistic lexical annotation technique, which automatically associates one or more meanings with schema elements w.r.t. a thesaurus/lexical resource. However, the accuracy of automatic lexical annotation methods on real-world schemata suffers from the abundance of non-dictionary words such as compound nouns and abbreviations. We address this problem by including a method to perform schema label normalization which increases the number of comparable labels. From the annotated schemata, we derive the probabilistic lexical relationships to be collected in the Probabilistic Common Thesaurus. The method is applied within the MOMIS data integration system but can easily be generalized to other data integration systems.     

A comprehensive database schema integration method based on the theory of formal concepts

Integrating heterogeneous database schemata is a major task in federated database design where preexisting and heterogeneous database systems need to be integrated virtually by providing a homogenization database interface. Most proposed schema integration methods suffer from very complex result schemata and insufficient handling of extensional relations, i.e. in the way how redundant data of the input systems are dealt with. Redundancy among the input systems may thus remain undetected and, hence, remains uncontrolled.Our GIM (Generic Integration Model) method is based on the elegant and mathematically founded theory of formal concept analysis (FCA). The main idea is to integrate schemata into one formal context which is a binary relation between a set of attributes and a set of base extensions (set of potential objects). From that context we apply an FCA-algorithm to semi-automatically derive a concept lattice which we interpret as an inheritance hierarchy of classes for a homogenized schema. Thus, the integration task following our method can be supported by tools.     

基于模式组合的粒子群优化测试用例生成方法

适应度函数的设计在基于搜索的测试用例生成技术中占据重要的位置,然而在某些特殊的程序中,如存在嵌套、非结构性跳转或因return,break等语句跳出循环的程序,已有的适应度函数无法评价到所有的分支.目前的方法是修改程序的源代码,以使每个分支得到评价.但修改源代码不但可能影响程序的原有结构、引入错误,而且很难实现自动化.针对这一问题,提出一种基于模式组合的粒子群优化测试用例生成方法.首先,将分支条件定义为"模式",即,一类具有相同特征且能提高适应度值的个体集合,并改变其分支函数的插桩方式,可解决分支条件不完全评价的问题;然后,设计一种新的交叉算子,寻找到所有使模式的分支函数值最小的个体,将这些个体中含有模式的部分通过交叉算子组合到一个个体上,既可防止模式在进化过程中被破坏,又可因多种模式的组合而提高个体的适应度值;最后,使用局部搜索策略对种群中的最优个体进行搜索,提高粒子群优化算法的局部搜索精度,进一步提高测试用例生成效率.为了评价该方法的有效性,基于一组基准程序和开源程序进行实验.实验结果表明:对于含有模式的程序,该测试用例生成方法与已有方法相比,在覆盖率和平均进化代数上均有明显优势.     

Generalised Coinduction

We introduce the λ-coiteration schema for a distributive law λ of a functor T over a functor F. Under certain conditions it can be shown to uniquely characterise functions into the carrier of a final F-coalgebra, generalising the basic coiteration schema as given by finality. The duals of primitive recursion and course-of-value iteration, which are known extensions of coiteration, arise as instances of our framework. One can furthermore obtain schemata justifying recursive specifications that involve operators such as addition of power series, regular operators on languages, or parallel and sequential composition of processes.Next, the same type of distributive law λ is used to generalise coinductive proof techniques. To this end, we introduce the notion of a λ-bisimulation relation. It specialises to what could be called bisimulation up-to-equality or bisimulation up-to-context for contexts built from operators of the type mentioned above. We state that every such relation is contained in some larger conventional bisimulation and demonstrate that this principle leads to simpler bisimilarity proofs using less complex relations.     

进化算法中的模式定理及建筑块

探讨了进化算法中的模式定理及建筑块理论．通过引入模式进化、模式进化能力、适度模式等概念，以标准遗传算法为例，证明了在变异算子独立的条件下，进化算法中模式的构成与多点交叉和变异的顺序无关，然后证明了具有强进化能力的模式，将以指数阶增长．该文的模式理论有别于Holland等人提出的模式理论，特别是在交叉算子上采用了多点交叉算子，给出了相应的公式；并从这一推导过程论证了建筑块假设的合理性，可以称之为建筑块理论．     

Properties of stochastic syntax-directed translation schemata

Stochastic syntax-directed translation schemata describe both the syntactic structure and the probability distribution of stochastic mappings between contextfree languages. The relationship between stochastic syntax-directed translation schemata and stochastic grammars and automata are presented by proving that a stochastic pushdown transducer can be constructed to define the same translations as a simple schema, and that the simple schema are characterized by stochastic contextfree grammars. Asymptotic properties of linear schemata are established by the theory of Markov chains. Since stochastic translations contain both input and output strings, their information content can be described. Equations are developed for both the information content and the rate of stochastic translations.     

Specification and synthesis of hybrid automata for physics-based animation

Physics-based animation programs can often be modeled in terms of hybrid automata. A hybrid automaton includes both discrete and continuous dynamical variables. The discrete variables define the automaton’s modes of behavior. The continuous variables are governed by mode-dependent differential equations. This paper describes a system for specifying and automatically synthesizing physics-based animation programs based on hybrid automata. The system presents a program developer with a family of parameterized specification schemata. Each schema describes a pattern of behavior as a hybrid automaton passes through a sequence of modes. The developer specifies a program by selecting one or more schemata and supplying application-specific instantiation parameters for each of them. Each schema is associated with a set of axioms in a logic of hybrid automata. The axioms serve to document the semantics of the specification schema. Each schema is also associated with a set of implementation rules. The rules synthesize program components implementing the specification in a general physics-based animation architecture. The system allows animation programs to be developed and tested in an incremental manner. The system itself can be extended to incorporate additional schemata for specifying new patterns of behavior, along with new sets of axioms and implementation rules. It has been implemented and tested on over a dozen examples. We believe this research is a significant step toward a specification and synthesis system that is flexible enough to handle a wide variety of animation programs, yet restricted enough to permit programs to be synthesized automatically.     

Schema theory for genetic programming with one-point crossover and point mutation

We review the main results obtained in the theory of schemata in genetic programming (GP), emphasizing their strengths and weaknesses. Then we propose a new, simpler definition of the concept of schema for GP, which is closer to the original concept of schema in genetic algorithms (GAs). Along with a new form of crossover, one-point crossover, and point mutation, this concept of schema has been used to derive an improved schema theorem for GP that describes the propagation of schemata from one generation to the next. We discuss this result and show that our schema theorem is the natural counterpart for GP of the schema theorem for GAs, to which it asymptotically converges.     

Schema design and mapping strategies for persistent object models

A formal model is presented for a conceptual schema of persistent object models that support a strong notion of object identity. The object constructors in the model are sets, tuples, and disjunct. The databases that correspond to such schemata are graph-structured object spaces. These conceptual object spaces are mapped onto physical object spaces, which are typically forests of trees. The characteristics of the physical schemata are discussed and an algorithm to transform a conceptual schema into a physical schema is given.     

Semantic schema theory for genetic programming

Schema theory is the most well-known model of evolutionary algorithms. Imitating from genetic algorithms (GA), nearly all schemata defined for genetic programming (GP) refer to a set of points in the search space that share some syntactic characteristics. In GP, syntactically similar individuals do not necessarily have similar semantics. The instances of a syntactic schema do not behave similarly, hence the corresponding schema theory becomes unreliable. Therefore, these theories have been rarely used to improve the performance of GP. The main objective of this study is to propose a schema theory which could be a more realistic model for GP and could be potentially employed for improving GP in practice. To achieve this aim, the concept of semantic schema is introduced. This schema partitions the search space according to semantics of trees, regardless of their syntactic variety. We interpret the semantics of a tree in terms of the mutual information between its output and the target. The semantic schema is characterized by a set of semantic building blocks and their joint probability distribution. After introducing the semantic building blocks, an algorithm for finding them in a given population is presented. An extraction method that looks for the most significant schema of the population is provided. Moreover, an exact microscopic schema theorem is suggested that predicts the expected number of schema samples in the next generation. Experimental results demonstrate the capability of the proposed schema definition in representing the semantics of the schema instances. It is also revealed that the semantic schema theorem estimation is more realistic than previously defined schemata.     

Exploiting multilevel parallelism on a many-core system for the application of hyperheuristics to a molecular docking problem

The solution of Protein–Ligand Docking Problems can be approached through metaheuristics, and satisfactory metaheuristics can be obtained with hyperheuristics searching in the space of metaheuristics implemented inside a parameterized schema. These hyperheuristics apply several metaheuristics, resulting in high computational costs. To reduce execution times, a shared-memory schema of hyperheuristics is used with four levels of parallelism, two for the hyperheuristic and two for the metaheuristics. The parallel schema is executed in a many-core system in “native mode,” and the four-level parallelism allows us to take full advantage of the massive parallelism offered by this architecture and obtain satisfactory fitness and an important reduction in the execution time.