The complexity of embedded axiomatization for a class of closed database views

It is well known that the complexity of testing the correctness of an arbitrary update to a database view can be far greater than the complexity of testing a corresponding update to the main schema. However, views are generally managed according to some protocol which limits the admissible updates to a subset of all possible changes. The question thus arises as to whether there is a more tractable relationship between these two complexities in the presence of such a protocol. In this paper, this question is addressed for closed update strategies, which are based upon the constant-complement approach of Bancilhon and Spyratos. The approach is to address a more general question – that of characterizing the complexity of axiomatization of views, relative to the complexity of axiomatization of the main schema. For schemata constrained by denial or consistency constraints, that is, statements which rule out certain situations, such as the equality-generating dependencies (EGDs) or, more specifically, the functional dependencies (FDs) of the relational model, a broad and comprehensive result is obtained in a very general framework which is not tied to the relational model in any way. It states that every such schema is governed by an equivalent set of constraints which embed into the component views, and which are no more complex than the original set. For schemata constrained by generating dependencies, of which tuple-generating dependencies (TGDs) in general and, more specifically, both join dependencies (JDs) and inclusion dependencies (INDs) are examples within the relational model, a similar result is obtained, but only within a context known as meet-uniform decompositions, which fails to recapture some important situations. To address the all-important case of relational schemata constrained by both FDs and INDs, a hybrid approach is also developed, in which the general theory regarding denial constraints is blended with a focused analysis of a special but very practical subset of the INDs known as fanout-free unary inclusion dependencies (fanout-free UINDs), to obtain results parallel to the above-mentioned cases: every such schema is governed by an equivalent set of constraints which embed into the component views, and which are no more complex than the original set. In all cases, the question of view update complexity is then answered via a corollary to this main result. Parts of this paper are based upon work reported in [21].     

Information-based distance measures and the canonical reflection of view updates

For the problem of reflecting an update on a database view to the main schema, the constant-complement strategies are precisely those which avoid all update anomalies, and so define the gold standard for well-behaved solutions to the problem. However, the families of view updates which are supported under such strategies are limited, so it is sometimes necessary to go beyond them, albeit in a systematic fashion. In this work, an investigation of such extended strategies is initiated for relational schemata. The approach is to characterize the information content of a database instance, and then require that the optimal reflection of a view update to the main schema embody the least possible change of information. The key property is identified to be strong monotonicity of the view, meaning that view insertions may always be reflected as insertions to the main schema, and likewise for deletions. In that context it is shown that for insertions and deletions, an optimal update, entailing the least change of information, exists and is unique up to isomorphism for wide classes of constraints.     

Parallel operator schemata over variable arrays and the maximal parallelism problem

Conclusions We have introduced a certain universal class of schemata and proven a theorem which can be used to study parallelism transformations of various subclasses of schemata. The results can be generalized by introducing multidimensional arrays, removing the restrictions on the power of the sets Db and Rb, and in other directions. Of particular interest is the case of parallelism in indeterminate schemata, since in numerous problems indeterminacy is inherent to the program and its preservation under equivalent transformations is not less desirable than the preservation of parallelism. The proposed construction of maximally parallel schemata for the indeterminate case gives a determinate schema which computes the intersection of the outcomes of all computations in a given interpretation. To obtain a schema with the same indeterminacy level as the orginal schema, the look-ahead function should be updated.Translated from Kibernetika, No. 5, pp. 52–63, September–October, 1979.     

Exploring into programs for the recovery of data dependenciesdesigned

Data dependencies play an important role in the design of a database. Many legacy database applications have been developed on old generation database management systems and conventional file systems. As a result, most of the data dependencies in legacy databases are not enforced in the database management systems. As such, they are not explicitly defined in database schema and are enforced in the transactions, which update the databases. It is very difficult and time consuming to find out the designed data dependencies manually during the maintenance and reengineering of database applications. In software engineering, program analysis has long been developed and proven as a useful aid in many areas. With the use of program analysis, this paper proposes a novel approach for the recovery of common data dependencies, i.e., functional dependencies, key constraints, inclusion dependencies, referential constraints, and sum dependencies, designed in a database from the behavior of transactions, which update the database. The approach is based on detecting program path patterns for implementing most commonly used methods to enforce these data dependencies     

Formulating global integrity constraints during derivation of global schema

In a heterogeneous distributed database environment, each component database is characterized by its own logical schema and its own set of integrity constraints. The task of generating a global schema from a constituent local schemata has been addressed by many researchers. The complementary problem of using multiple sets of integrity constraints to create a new set of global integrity constraints is examined in this paper. These global integrity constraints facilitate both query optimization and update validation tasks.     

A methodology for integration of heterogeneous databases

The transformation of existing local databases to meet diverse application needs at the global level is performed through a four-layered procedure that stresses total schema integration and virtual integration of local databases. The proposed methodology covers both schema integration and database integration, and uses a four-layered schema architecture (local schemata, local object schemata, global schema, and global view schemata) with each layer presenting an integrated view of the concepts that characterize the layer below. Mechanisms for accomplishing this objective are presented in theoretical terms, along with a running example. Object equivalence classes, property equivalence classes, and other related concepts are discussed in the context of logical integration of heterogeneous schemata, while object instance equivalence classes and property instance equivalence classes, and other related concepts are discussed for data integration purposes. The proposed methodology resolves naming conflicts, scaling conflicts, type conflicts, and level of abstraction, and other types of conflicts during schema integration, and data inconsistencies during data integration     

A multiagent update process in a database with temporal datadependencies and schema versioning

Temporal data dependencies are high-level linguistic constructs that define relationships among values of data-elements in temporal databases. These constructs enable the support of schema versioning as well as the definition of consistency requirements for a single time-point and among values in different time-points. In this paper, we present a multiagent update process in a database with temporal data dependencies and schema versioning. The update process supports the evolution of dependencies over time and the use of temporal operators within temporal data dependencies. The temporal dependency language is presented, along with the temporal dependency graph-which serves as the executable data structure. A thorough discussion of the feasibility, performance, and consistency of the presented model is provided     

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 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.     

基于频繁闭项集挖掘的增量式维护算法

为了能够随着数据库的增加、删除和修改而快速有效地挖掘出频繁闭项集,根据CHARM算法提出了一种基于频繁闭项集挖掘的增量式维护算法。该算法采取分类处理的策略对变化数据进行挖掘,运用IT对的特性从已挖掘出的结果中快速过滤出仍然有效的信息,实现频繁闭项集的更新。实验结果表明该算法是快速有效的。     

A compensation-based approach for view maintenance in distributed environments

Data integration over multiple heterogeneous data sources has become increasingly important for modern applications. The integrated data is usually stored as materialized views to allow better access, performance, and high availability. In loosely coupled environments, such as the data grid, the data sources are autonomous. Hence, tie source updates can be concurrent and cause erroneous results during view maintenance. State-of-the-art maintenance strategies apply compensating queries to correct such errors, making the restricting assumption that all source schemata remain static over time. However, in such dynamic environments, the data sources may change not only their data but also their schema. Consequently, either the maintenance queres or the compensating queries may fail. In this paper, we propose a novel framework called DyDa that overcomes these limitations and handles both source data updates and schema changes. We identify three types of maintenance anomalies, caused by either source data updates, data-preserving schema changes, or non-data-preserving schema changes. We propose a compensation algorithm to solve the first two types of anomalies. We show that the third type of anomaly is caused by the violation of dependencies between maintenance processes. Then, we propose dependency detection and correction algorithms to identify and resolve the violations. Put together, DyDa extends prior maintenance solutions to solve all types of view maintenance anomalies. The experimental results show that DyDa imposes a minimal overhead on data update processing while allowing for the extended functionality to handle concurrent schema changes.     

XML模式中隐式冗余不存在的充要条件

XML数据库模式规范化设计是产生一组相关联的、能表示数据间依赖关系、而且消除了冗余的XML模式或DTD,以更好地进行信息检索.XML数据库模式中某些数据依赖的存在是冗余存在的原因,因此在XML数据库模式中数据依赖与冗余的关联是其规范化设计研究的关键问题,但对这一问题目前还没有专门的研究.XML数据库模式的数据依赖包括属性间数据依赖和元素间的数据依赖,给出综合了属性间和元素间数据依赖的XML数据库模式数据依赖的定义,分析与之关联的隐式冗余,并论证XML模式中隐式冗余不存在当且仅当该XML模式是规范的,为XML数据库模式规范化设计更深一层的研究奠定理论基础.     

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.     

MEER—An EER model enhanced with structure methods

Entity relationship (ER) schemas include cardinality constraints, that restrict the dependencies among entities within a relationship type. The cardinality constraints have direct impact on the application maintenance, since insertions or deletions of entities or relationships might affect related entities. Indeed, maintenance of a system or of a database can be strengthened to enforce consistency with respect to the cardinality constraints in a schema. Yet, once an ER schema is translated into a logical database schema, or translated within a system, the direct correlation between the cardinality constraints and maintenance transactions is lost, since the components of the ER schema might be decomposed among those of the logical database schema or the target system.In this paper, a full solution to the enforcement of cardinality constraints in EER schemas is given. We extend the enhanced ER (EER) data model with structure-based update methods that are fully defined by the cardinality constraints. The structure methods are provably terminating and cardinality faithful, i.e., they do not insert new inconsistencies and can only decrease existing ones. A refined approach towards measuring the cardinality consistency of a database is introduced. The contribution of this paper is in the automatic creation of update methods, and in building the formal basis for proving their correctness.     

Schema Vacuuming in Temporal Databases

Temporal databases facilitate the support of historical information by providing functions for indicating the intervals during which a tuple was applicable (along one or more temporal dimensions). Because data are never deleted, only superceded, temporal databases are inherently append-only resulting, over time, in a large historical sequence of database states. Data vacuuming in temporal databases allows for this sequence to be shortened by strategically, and irrevocably, deleting obsolete data. Schema versioning allows users to maintain a history of database schemata without compromising the semantics of the data or the ability to view data through historical schemata. While the techniques required for data vacuuming in temporal databases have been relatively well covered, the associated area of vacuuming schemata has received less attention. This paper discusses this issue and proposes a mechanism that fits well with existing methods for data vacuuming and schema versioning.     

On the complexity of finding bounds for projection cardinalities in relational databases

We address the problem of deriving lower and upper bounds for the cardinality of the projections of a database relation, given a set of functional dependencies on the relation schema and measures of the cardinalities of the attributes in the schema. It is shown that deciding whether a given number is the least upper bound of a projection cardinality is an NP-complete problem, whereas determining whether the greatest lower bound and the least upper bound coincide can be easily solved in linear time.     

Gravitating to rigidity: Patterns of schema evolution – and its absence – in the lives of tables

Like all software maintenance, schema evolution is a process that can severely impact the lifecycle of a data-intensive software projects, as schema updates can drive depending applications crushing or delivering incorrect data to end users. In this paper, we study the schema evolution of eight databases that are part of larger open source projects, publicly available through open source repositories. In particular, the focus of our research was the understanding of which tables evolve and how. We report on our observations and patterns on how evolution related properties, like the possibility of deletion, or the amount of updates that a table undergoes, are related to observable table properties like the number of attributes or the time of birth of a table.A study of the update profile of tables, indicates that they are mostly rigid (without any updates to their schema at all) or quiet (with few updates), especially in databases that are more mature and heavily updated. Deletions are significantly outnumbered by table insertions, leading to schema expansion. Delving deeper, we can highlight four patterns of schema evolution. The Γ pattern indicating that tables with large schemata tend to have long durations and avoid removal, the Comet pattern indicating that the tables with most updates are the ones with medium schema size, the Inverse Γ pattern, indicating that tables with medium or small durations produce amounts of updates lower than expected, and, the Empty Triangle pattern indicating that deletions involve mostly early born, quiet tables with short lives, whereas older tables are unlikely to be removed. Overall, we believe that the observed evidence strongly indicates that databases are rigidity-prone rather than evolution-prone. We call the phenomenon gravitation to rigidity and we attribute it to the implied impact to the surrounding code that a modification to the schema of a database has.     

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.     

具有全序时态类型集时态函数依赖集的研究

好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异常.对于时态数据库,可以通过具有多时间粒度的时态函数依赖(TFDs)约束对时态数模式进行规范化.但是由于时间维的引入和多时间粒度的使用而给数据库设计带来巨大的复杂性.一般来说,系统所能处理的和相当多的应用所涉及到的时态类型集满足全序关系,并且具有全序时态类型集的TFD集的推导规则与传统函数依赖(FDs)的Armstrong公理有着紧密的联系.通过分析TFDs与FDs之间存在的联系,利用传统FD集的相应算法,提出了成员籍、有限属性闭包等TFD集的一些重要算法.这些算法是时态数据库进一步规范化的基础.     

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.