Differential relational calculus for integrity maintenance

A differential calculus for first-order logic is developed to enforce database integrity. Formal differentiation of first-order sentences is useful in maintaining database integrity, since once a database constraint is expressed as a first-order sentence, its derivative with respect to a transaction provides the necessary and sufficient condition for maintaining integrity. The derivative is often much simpler to test than the original constraint since it maintains integrity differentially by assuming Integrity before the transaction, and testing only for new violations. The formal differentiation requires no resolution search, only substitution. It is more efficient than resolution-based approaches; and it provides a considerably more general solution than previous substitution-based methods since it is valid for all first-order sentences and with all transactions involving arbitrary collections of atomic changes to the database. It also produces a large number of sufficient conditions that are often less strict than those of the previous approaches; and it can be extended to accommodate many dynamic constraints     

A logic-based mechanism for integrity maintenance of engineering databases

The semantics of engineering data can be represented in terms of constraints and can be maintained via constraint checking and enforcement. Conventional databases (e.g. Relational Databases) are inadequate for maintaining engineering data semantics because they have no effective means for representing and checking/enforcing constrains. As an extension of relational databases, deductive databases overcome this inadequacy by enabling constraint representation and checking. However, they too lack the constraint enforcement ability. a logic-based mechanism for enforcing constrainst in deductive databases is presented in this paper. The mechanism is composed of two operators: a truth enforcement operator and a falsity enforcement operator. The mechanics of these operators and their use for integrity enfocement are described herein.     

Building a tuple space on structured peer-to-peer networks

Research on peer-to-peer (P2P) networks has attracted much attention recently. A key factor is their ability to handle dynamics in the system in a distributed fashion, including ad hoc and dynamic join and departure of the peers and dynamic changes in the underlying network environment. As more and more innovating P2P applications appear, the need to support intuitive communication and synchronization among the peers in the P2P system becomes imperative. In this paper, we discuss how to build a tuple space on top of P2P systems and use on-line games as a target application. A simple API is supported for accessing the data stored in the tuple space and communicating between the peers. Through experiments and a demonstration game, we show that our system can facilitate the development of network games in a fully distributed environment.

一种基于SQL的元组集随机抽取算法

提出了一种基于SQL语句的从数据库中随机读取随机记录集合的算法。该算法摒弃了贯用的通过复杂的客户端编程实现随机过程的做法,通过对SQL语言中的伪随机函数和反转函数进行组合,只用一条SQL语句就可以实现随机过程,算法实现简单,资源占有率低、效率高,具有很强的通用性和实用性。     

A tuple channel-based coordination model for parallel and distributed programming

This paper presents tuple channel model (TCM), a new coordination model for parallel and distributed programming. Our proposal is based on the use of tuple channels (TCs) to model the communication and synchronization of different activities. TCs are multi-point channels that allow complex data structures to be communicated among multiple producers and consumers. This communication model allows incremental and backward communication to be expressed, providing an elegant way of implicit and direct communication and reactive control. TCs can be dynamically interconnected through the use of user-defined connectors, providing great flexibility for the definition of complex and dynamic interaction protocols. TCM also provides a simple service management mechanism, by means of which open systems can be implemented in an appropriate way. The suitability, expressiveness and programming techniques of the model are presented by means of some illustrative examples. In addition, some implementation details of the developed prototypes are sketched and we show the preliminary results demonstrating the efficiency of the proposal.     

元组容器在C++中的设计与实现

C 是一种静态类型语言,这就使实现可以容纳不同种类型元素的容器——元组变得十分困难。C 的标准容器库STL虽然提供了丰富的容器,但其都只能容纳相同类型的元素,没有提供对元组容器的支持。其实C 的模板机制为它的静态类型系统增加了很大的灵活性,再使用一些其它的技巧,使得实现元组容器成为可能。wyf::tuple就是如此实现的一个元组容器的程序库。wyf::tuple不但可以保证类型安全,并且是高效的。测试数据表明,它要比一些动态语言如Python中的类似容器高效得多。     

A graph-based approach for rule integrity and maintainability in expert system maintenance

Just as conventional software systems have maintenance costs far exceeding development costs, so too do rule-based expert systems. They are frequently developed by an incremental and iterative method, where knowledge and decision rules are extracted and added to the system in a piecemeal manner throughout system evolution. Thus, ensuring the correctness and consistency of the rule base (RB) becomes an important, though challenging task. However, most research work in expert systems has focused on building and validating rule bases, leaving the maintenance issue unexplored. We propose a graph-based approach, called the object classification model (OCM), as a methodology for RB maintenance. An experiment was conducted to compare the OCM with traditional RB maintenance methods. The results show that the OCM helps knowledge engineers retain rule-base integrity and, thus, increase rule-base maintainability.     

On the collective sort problem for distributed tuple spaces

In systems coordinated with a distributed set of tuple spaces, it is crucial to assist agents in retrieving the tuples they are interested in. This can be achieved by sorting techniques that group similar tuples together in the same tuple space, so that the position of a tuple can be inferred by similarity. Accordingly, we formulate the collective sort problem for distributed tuple spaces, where a set of agents is in charge of moving tuples up to a complete sort has been reached, namely, each of the N tuple spaces aggregate tuples belonging to one of the N kinds available. After pointing out the requirements for effectively tackling this problem, we propose a self-organizing solution resembling brood sorting performed by ants. This is based on simple agents that perform partial observations and accordingly take decisions on tuple movement. Convergence is addressed by a fully adaptive method for simulated annealing, based on noise tuples inserted and removed by agents on a need basis so as to avoid sub-optimal sorting. Emergence of sorting properties and scalability are evaluated through stochastic simulations.     

Implementing temporal integrity constraints using an active DBMS

The paper proposes a general architecture for implementing temporal integrity constraints by compiling them into a set of active DBMS rules. The modularity of the design allows easy adaptation to different environments. Both differences in the specification languages and in the target rule systems can be easily accommodated. The advantages of this architecture are demonstrated on a particular temporal constraint compiler. This compiler allows automatic translation of integrity constraints formulated in Past Temporal Logic into rules of an active DBMS (in the current version of the compiler two active DBMS are supported: Starburst and INGRES). During the compilation the set of constraints is checked for the safe evaluation property. The result is a set of SQL statements that includes all the necessary rules needed for enforcing the original constraints. The rules are optimized to reduce the space overhead introduced by the integrity checking mechanism. There is no need for an additional runtime constraint monitor. When the rules are activated, all updates to the database that violate any of the constraints are automatically rejected (i.e., the corresponding transaction is aborted). In addition to straightforward implementation, this approach offers a clean separation of application programs and the integrity checking code     

消息分发系统中的元组空间分解算法研究

为解决分布式环境下消息分发系统中的按需通信,在对Gelemter元组空间模型进行改进的基础上,对消息分发系统中的元组空间通信进行了结构设计,定义了元组空间的特征模型,并基于局部性原理提出一种元组空间通信的空间分解算法.该算法依据在实际通信中不同元组不同元素的匹配频度的差异,将元组空间分解为依赖特征空间、特征元组和特征元素之间抽象关系的一组缓冲子空间,通信进程在进行匹配操作时可直接从缓冲子空间中获取匹配元组,从而降低通信的计算成本.     

孔板流量计的使用与维护

孔板流量计是一种广泛使用的容积式流量计,本文简要叙述了孔板流量计的工作原理,对孔板流量计的计量误差及原因进行了分析并提出了相应的措施,给工程技术人员提供一定的帮助。     

File maintenance using a line editor

A small suite of programs has been developed which, when used in conjunction with a computer manufacturer's line editing program, may be used for the maintenance and updating of files where the number of data cards for each subject is not necessarily constant. The programs may also be used when there is only one card for each subject.     

Database maintenance efficiency using differential files

Severance and Lohman[1] proposed that all database amendments (i.e. additions, deletions and updates) are localized into a relatively small storage area, called a differential file. When the differential file grows sufficiently large, a reorganization incorporates all changes into a new generation of the database. This paper proposes a modification of the differential file approach in that the differential file only stores record additions. It is also concerned with the selection of the optimum reorganization points for both the original and the modified differential file approaches.     

Efficient audio integrity verification algorithm using discrete cosine transform

Audio recordings have been used as evidence for long times. Multimedia processing advancement makes it difficult to be completely sure about what is heard is the truth. This paper presents a promising approach for integrity verification of recorded audio signals using discrete cosine transform. This approach is based on self embedding concept which embeds block-based marks extracted from the same audio signal after being transformed into 2-D format into other blocks according to a specific algorithm. After the self-embedding process, the data is converted back into 1-D style which represents a marked audio signal. The 1-D audio signal is converted into a 2-D format and then converted back into a 1-D format using the popular lexicographic ordering scheme utilized in image processing. Reverse processes are executed to extract the verification marks from the audio signal throughout the integrity verification process. Based on the extracted audio signal properties, the integrity of the marked audio signal is evaluated. Different audio processing tasks and attacks are implemented to examine the suitability of the proposed algorithm for verifying the integrity of high-confidentiality recorded audio data. The results show that the efficient ability of the proposed approach to verify integrity and detect attacks.     

Combining intensional with extensional query evaluation in tuple independent probabilistic databases

In this paper, we prove that a query plan is safe in tuple independent probabilistic databases if and only if its every answer tuple is tree structured in probabilistic graphical models. We classify hierarchical queries into core and non-core hierarchical queries and show that the existing methods can only generate safe plans for core hierarchical queries. Inspired by the bucket elimination framework, we give the sufficient and necessary conditions for the answer relation of every candidate sub-query to be used as a base relation. Finally, the proposed algorithm generates safe plans for extensional query evaluation on non-boolean hierarchical queries and invokes the SPROUT algorithm [24] for intensional query evaluation on boolean queries. A case study on the TPC-H benchmark reveals that the safe plans of Q7 and Q8 can be evaluated efficiently. Furthermore, extensive experiments show that safe plans generated by the proposed algorithm scale well.     

Facilitating resource discovery in grid environments with peer-to-peer structured tuple spaces

The computational grid is rapidly evolving into a large-scale computing infrastructure that facilitates resource sharing and problem solving over the Internet. Information services play a crucial role in grid environments for discovery of resources. The dynamic nature and the large-scale of a grid pose many challenges to information services in terms of scalability and resilience. This paper presents RDSpace which can be used as a substrate for resource discovery in grid environments. RDSpace builds a shared tuple space on top of a structured peer-to-peer overlay to achieve high scalability in dealing with a large number of computing nodes and to support range queries in discovery of resources. Another novelty of RDSpace lies in its capability to handle churn situations where nodes may join or leave the space frequently. RDSpace is evaluated from the aspects of scalability and churn handling, and the evaluation results are also presented in this paper.     

On the undecidability of the equivalence of second-order tuple generating dependencies

Second-order tuple generating dependencies (SO tgds) were introduced by Fagin et al. to capture the composition of simple schema mappings. Testing the equivalence of SO tgds would be important for applications like model management and mapping optimization. However, we prove the undecidability of the logical equivalence of SO tgds. Moreover, under weak additional assumptions, we also show the undecidability of a relaxed notion of equivalence between two SO tgds, namely the so-called conjunctive query equivalence.     

基于元组向量折叠的大规模规则库包分类算法

基于元组空间提出了一种适用于多维大规则库的包分类算法——元组向量折叠算法。与基本元组空间算法和基于元组的位并行包分类算击相比较,该算法在空间复杂度和时间复杂度上都取得了较好的性能。     

Rewriting queries using views with access patterns under integrity constraints

We study the problem of rewriting queries using views in the presence of access patterns, integrity constraints, disjunction and negation. We provide asymptotically optimal algorithms for (1) finding minimally containing and (2) maximally contained rewritings respecting the access patterns (which we call executable) and for (3) deciding whether an exact executable rewriting exists. We show that rewriting queries using views in this case reduces (a) to rewriting queries with access patterns and constraints without views and also (b) to rewriting queries using views under constraints without access patterns. We show how to solve (a) directly and how to reduce (b) to rewriting queries under constraints only (semantic optimization). These reductions provide two separate routes to a unified solution for problems 1, 2 and 3 based on an extension of the relational chase theory to queries and constraints with disjunction and negation. We also handle equality and arithmetic comparisons. We also show that in an information integration setting, maximally contained rewritings are given by the certain answers (under the usual semantics) for a set of constraints derived from the binding patterns. That is, except for defining the appropriate constraints, binding patterns do not need special treatment. Finally, we show that if there is an exact executable rewriting, there is an executable rewriting which is a union of conjunctive queries with negation.