Violet

Violet is an easy-to-use theorem prover based on locking resolution, with integrated equality extensions that use term rewriting and Knuth–Bendix completion. Violet participated in the CADE-13 ATP System Competition.     

Enhanced abstract data types in object-relational databases

The explosion in complex multimedia content makes it crucial for database systems to support such data efficiently. This paper argues that the “blackbox” ADTs used in current object-relational systems inhibit their performance, thereby limiting their use in emerging applications. Instead, the next generation of object-relational database systems should be based on enhanced abstract data type (E-ADT) technology. An (E-ADT) can expose the semantics of its methods to the database system, thereby permitting advanced query optimizations. Fundamental architectural changes are required to build a database system with E-ADTs; the added functionality should not compromise the modularity of data types and the extensibility of the type system. The implementation issues have been explored through the development of E-ADTs in Predator. Initial performance results demonstrate an order of magnitude in performance improvements. Received January 1, 1998 / Accepted May 27, 1998     

基于查询方式的模糊Petri网的推理算法

提出利用数据库的查询技术来实现模糊Petri网的推理。把模糊Petri网模型映射到关系数据模型上，用两个数据表结构来表示一个模糊Petri网模型。推理算法中应用的是一些基本的数据库技术，推理算法简单、高效、通用。尤其适合较大规模的FPN模型的推理运算。     

基于Web数据库的图形报表技术研究

分析了基于Web平台数据库图形报表系统的实现技术并提出了基于Web平台图形报表系统的架构，阐述了Java Servlet技术、Formula One组件技术，基于前面所述架构和Servlet、Formula One等技术给出了制作图形报表的方法和实现技术。研究了对Web应用极具前途的XML数据库的模式及查询，得出了初步的结果。     

基于GM(1,1)模型的压缩域图像表示与检索技术

在讨论基于灰色模型GM(1，1)和Hilbert空间填充曲线的图像压缩算法的基础上，提出了一种新的彩色图像表示与检索技术。它使用GM(1，1)对图像的像素值进行模型化处理，并且在变换域中对这些模型参数进行分析与处理，据此抽取出一种新的图像特征。这种压缩域特征描述了图像的局部细节变化，这种特点正是全局检索方法(例如颜色直方图方法)所小具备的。实验结果表明，这种压缩域图像检索技术能获得较满意的检索质量与性能，其检索结果能较好地同人们的视觉感知结果保持一致。     

基于XML数据的通用路径表达式的查询

查询重写是数据库研究的一个基本问题,它和查询优化、数据仓库、数据集成、语义缓存等数据库问题密切相关。同时,查询重写也是在关系数据库中存储和查询XML数据的关键问题。由于XML数据是元素嵌套和元素引用的,嵌套层数可以任意,并且模式和数据混合,因此XML的查询会涉及到广义路径表达式(GPE)。文中着重研究了如何解决XML数据的查询重写的方案,把含有广义路径表达式的XML查询语句重写为含有简单路径表达式(SPE)的XML查询语句,再转化为基于关系数据库的SQL语句。     

Towards an algebraic theory of information integration

Information integration systems provide uniform interfaces to varieties of heterogeneous information sources. For query answering in such systems, the current generation of query answering algorithms in local-as-view (source-centric) information integration systems all produce what has been thought of as “the best obtainable” answer, given the circumstances that the source-centric approach introduces incomplete information into the virtual global relations. However, this “best obtainable” answer does not include all information that can be extracted from the sources because it does not allow partial information. Neither does the “best obtainable” answer allow for composition of queries, meaning that querying a result of a previous query will not be equivalentto the composition of the two queries. In this paper, we provide a foundation for information integration, based on the algebraic theory of incomplete information. Our framework allows us to define the semantics of partial facts and introduce the notion of the exact answer—that is the answer that includes partial facts. We show that querying under the exact answer semantics is compositional. We also present two methods for actually computing the exact answer. The first method is tableau-based, and it is a generalization of the “inverse-rules” approach. The second, much more efficient method, is a generalization of the rewriting approach, and it is based on partial containment mappings introduced in the paper.     

OWL-QL—a language for deductive query answering on the Semantic Web

This paper discusses the issues involved in designing a query language for the Semantic Web and presents the OWL query language (OWL-QL) as a candidate standard language and protocol for query–answering dialogues among Semantic Web computational agents using knowledge represented in the W3Cs ontology web language (OWL). OWL-QL is a formal language and precisely specifies the semantic relationships among a query, a query answer, and the knowledge base(s) used to produce the answer. Unlike standard database and Web query languages, OWL-QL supports query–answering dialogues in which the answering agent may use automated reasoning methods to derive answers to queries, as well as dialogues in which the knowledge to be used in answering a query may be in multiple knowledge bases on the Semantic Web, and/or where those knowledge bases are not specified by the querying agent. In this setting, the set of answers to a query may be of unpredictable size and may require an unpredictable amount of time to compute.     

Theory revision with queries: Horn, read-once, and parity formulas

A theory, in this context, is a Boolean formula; it is used to classify instances, or truth assignments. Theories can model real-world phenomena, and can do so more or less correctly. The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for Horn formulas and read-once formulas, where revision operators are restricted to deletions of variables or clauses, and for parity formulas, where revision operators include both deletions and additions of variables. We also show that the query complexity of the read-once revision algorithm is near-optimal.     

Syntactic compression codes at the zero entropy point

Syntactic compression codes compress the tree, which is the syntax of a binary source message. The ones considered here originate from image processing. The syntactic trees usedhave a constant valency and their binary labels distinguish whether the source substring derived from a node is completely zero or not. We compress them simply by deleting some redundant subtrees.

These codes fall into a theoretically new class of codes which is wider than the classical ones. They are here studied in the neighborhood of a zero of the binary entropy function. There, their behavior is close to that of an infinite run length encoding and the optimum valency is three. Finally, we open a problem, related with automata theory, which perhaps could provide a further link between Information Theory and Algorithmic Information Theory.