Relational completeness of query languages for annotated databases

Annotated relational databases can be queried either by simply making the annotations explicitly available along the ordinary data, or by adapting the standard query operators so that they have an implicit effect also on the annotations. We compare the expressive power of these two approaches. As a formal model for the implicit approach we propose the color algebra, an adaptation of the relational algebra to deal with the annotations. We show that the color algebra is relationally complete: it is equivalent to the relational algebra on the explicit annotations. Our result extends a similar completeness result established for the query algebra of the MONDRIAN annotation system, from unions of conjunctive queries to the full relational algebra. We also show that the color algebra is nonredundant: no operator can be expressed in terms of the other operators. We also present a generalization of the color algebra that is relationally complete in the presence of built-in predicates on the annotations.     

Note on ideals of effect algebras

We show that in a lattice effect algebra, each lattice ideal is an effect algebra ideal if and only if the lattice effect algebra is an orthomodular lattice.     

一种泛逻辑代数系统

文[3]给出了理想状态(广义相关系数h=0.5,广义自相关系数k=0.5)下泛逻辑的形式演绎系统B,证明了此系统是可靠的。该文提出理想状态下(h=k=0.5)泛逻辑学对应的代数系统-UB代数,给出它的一系列性质。证明了UB代数是一个交换剩余半群;进一步证明了U B代数与M V代数、正规FI代数是等价的。     

Computational complexity of some problems involving congruences on algebras

We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.     

多粒化的粗糙集代数

众所周知,一个粗糙集代数是由一个集合代数加上一对近似算子构成的。一方面 ,在公理化的方法下对经典的多粒化粗糙集代数系统进行了讨论,可知经典的粗糙集代数没有很好的性质;另一方面,给出了单调等价关系的定义,并给出了基于单调等价关系的多粒化近似算子的概念,在此基础上讨论了粗糙集代数的性质,并得到了诸多结果。     

基于格结构的概念代数研究

近年来,概念格作为一种有效的概念分析、表示与应用模型,被越来越多的领域所应用。概念代数是在概念 格理论基础上提出的一种新的代数系统。目前,概念代数系统还只是雏形,很多方面的内容还需要扩展与进一步的研 究。基于格结构的概念代数研究分别对Nilsson概念代数、Wille概念代数和认知信息学中的概念代数的基本概念与 内容进行了介绍,对各方法进行了分析与比较,并证明Nilsson概念代数是一种广义概念代数,为进一步的应用与研 究提供支持。     

A dynamic programming method for building free algebras

We are interested in deciding if a given nonassociative polynomial h is an identity for a variety of nonassociative algebras. We present an algorithm for constructing a certain homomorphic image of a free nonassociative algebra which is sufficient to answer the question. The algorithm resembles dynamic programming in that the algebra is built by constructing a sequence of subspaces; the basis of each subspace is determined by the basis of previous subspaces. The number of arithmetic operations required to construct the algebra is bounded by a polynomial in the degree of h and the dimension of the resulting algebra.     

A data model and algebra for probabilistic complex values

We present a probabilistic data model for complex values. More precisely, we introduce probabilistic complex value relations, which combine the concept of probabilistic relations with the idea of complex values in a uniform framework. We elaborate a model-theoretic definition of probabilistic combination strategies, which has a rigorous foundation on probability theory. We then define an algebra for querying database instances, which comprises the operations of selection, projection, renaming, join, Cartesian product, union, intersection, and difference. We prove that our data model and algebra for probabilistic complex values generalizes the classical relational data model and algebra. Moreover, we show that under certain assumptions, all our algebraic operations are tractable. We finally show that most of the query equivalences of classical relational algebra carry over to our algebra on probabilistic complex value relations. Hence, query optimization techniques for classical relational algebra can easily be applied to optimize queries on probabilistic complex value relations.     

Intervals in generalized effect algebras

A significant property of a generalized effect algebra is that its every interval with inherited partial sum is an effect algebra. We show that in some sense the converse is also true. More precisely, we prove that a set with zero element is a generalized effect algebra if and only if all its intervals are effect algebras. We investigate inheritance of some properties from intervals to generalized effect algebras, e.g., the Riesz decomposition property, compatibility of every pair of elements, dense embedding into a complete effect algebra, to be a sub-(generalized) effect algebra, to be lattice ordered and others. The response to the Open Problem from Rie?anová and Zajac (2013) for generalized effect algebras and their sub-generalized effect algebras is given.     

Fuzzy maximal ideals of BCI and MV algebras

We consider fuzzy maximal ideals of BCI, BCK, and MV algebras, and show that such fuzzy ideals take only the values {0,1}, and have level ideals which are maximal ideals of the algebra. It is shown that fuzzy maximal ideals of commutative BCK algebras are fuzzy prime. We establish a correspondence between ideals and fuzzy ideals. In a bounded BCK algebra, this correspondence is one-to-one between maximal ideals and fuzzy maximal ideals. We also show how to construct fuzzy ideals which are not characteristic functions of ideals of an MV algebra.     

Continuity controlled hybrid automata

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation of hybrid automata as timed transition systems. We also relate the synchronized product operator on hybrid automata to the parallel composition operator of the process algebra. It turns out that the formalism of hybrid automata matches a fragment of the process algebra for hybrid systems closely. We present an adaptation of the formalism of hybrid automata that yields an exact match.     

Efficient Querying and Animation of Periodic Spatio-Temporal Databases

We propose a representation of spatio-temporal objects with continuous and cyclic or acyclic periodic movements. We also describe an extended relational algebra query language for databases with such objects. We show that the new spatio-temporal databases are closed under the extended relational algebra queries, and each fixed relational algebra query can be evaluated in PTIME in the size of the input database.     

The equational theory of Kleene lattices

Languages and families of binary relations are standard interpretations of Kleene algebras. It is known that the equational theories of these interpretations coincide and that the free Kleene algebra is representable both as a relation and as a language algebra. We investigate the identities valid in these interpretations when we expand the signature of Kleene algebras with the meet operation. In both cases, meet is interpreted as intersection. We prove that in this case, there are more identities valid in language algebras than in relation algebras (exactly three more in some sense), and representability of the free algebra holds for the relational interpretation but fails for the language interpretation. However, if we exclude the identity constant from the algebras when we add meet, then the equational theories of the relational and language interpretations remain the same, and the free algebra is representable as a language algebra, too. The moral is that only the identity constant behaves differently in the language and the relational interpretations, and only meet makes this visible.     

多粒化的模糊粗糙集代数

众所周知,一个粗糙集代数是由一个集合代数加上一对近似算子构成的。首先利用公理化的方法探讨经典的多粒化模糊粗糙集代数系统,可知经典的多粒化模糊粗糙集代数没有很好的性质;其次,引入 具有最小(大)元的等价关系的定义,并给出了基于具有最小(大)元等价关系的多粒化模糊近似算子的概念,在此基础上讨论了模糊粗糙集代数的性质,并得到了诸多结果。     

An extended algebra for constraint databases

Constraint relational databases use constraints to both model and query data. A constraint relation contains a finite set of generalized tuples. Each generalized tuple is represented by a conjunction of constraints on a given logical theory and, depending on the logical theory and the specific conjunction of constraints, it may possibly represent an infinite set of relational tuples. For their characteristics, constraint databases are well suited to model multidimensional and structured data, like spatial and temporal data. The definition of an algebra for constraint relational databases is important in order to make constraint databases a practical technology. We extend the previously defined constraint algebra (called generalized relational algebra). First, we show that the relational model is not the only possible semantic reference model for constraint relational databases and we show how constraint relations can be interpreted under the nested relational model. Then, we introduce two distinct classes of constraint algebras, one based on the relational algebra, and one based on the nested relational algebra, and we present an algebra of the latter type. The algebra is proved equivalent to the generalized relational algebra when input relations are modified by introducing generalized tuple identifiers. However, from a user point of view, it is more suitable. Thus, the difference existing between such algebras is similar to the difference existing between the relational algebra and the nested relational algebra, dealing with only one level of nesting. We also show how external functions can be added to the proposed algebra     

Identities for the Associator in Alternative Algebras

The associator is an alternating trilinear product for any alternative algebra. We study this trilinear product in three related algebras: the associator in a free alternative algebra, the associator in the Cayley algebra, and the ternary cross product on four-dimensional space. This last example is isomorphic to the ternary subalgebra of the Cayley algebra which is spanned by the non-quaternion basis elements. We determine the identities of degree  ≤  7 satisfied by these three ternary algebras. We discover two new identities in degree 7 satisfied by the associator in every alternative algebra and five new identities in degree 7 satisfied by the associator in the Cayley algebra. For the ternary cross product we recover the ternary derivation identity in degree 5 introduced by Filippov.     

Poincaré–Birkhoff–Witt theorem for Leibniz -algebras

We construct the universal enveloping algebra of a Leibniz n-algebra and we prove that the category of modules over this algebra is equivalent to the category of representations.We also give a proof of the Poincaré–Birkhoff–Witt theorem for universal enveloping algebras of finite-dimensional Leibniz n-algebras using Gröbner bases in a free associative algebra.     

Two-dimensional linear algebra

We introduce two-dimensional linear algebra, by which we do not mean two-dimensional vector spaces but rather the systematic replacement in linear algebra of sets by categories. This entails the study of categories that are simultaneously categories of algebras for a monad and categories of coalgebras for comonad on a category such as SymMon_s, the category of small symmetric monoidal categories. We outline relevant notions such as that of pseudo-closed 2-category, symmetric monoidal Lawvere theory, and commutativity of a symmetric monoidal Lawvere theory, and we explain the role of coalgebra, explaining its precedence over algebra in this setting. We outline salient results and perspectives given by the dual approach of algebra and coalgebra, extending to two dimensions the study of linear algebra.     

Query languages for relational multidatabases

With the existence of many autonomous databases widely accessible through computer networks, users will require the capability to jointly manipulate data in different databases. A multidatabase system provides such a capability through a multidatabase manipulation language, such as MSQL. We propose a theoretical foundation for such languages by presenting a multirelational algebra and calculus based on the relational algebra and calculus. The proposal is illustrated by various queries on an example multidatabase. It is shown that properties of the multirelational algebra may be used for optimization and that every multirelational algebra query can be expressed as a multirelational calculus query. The connection between the multirelational languages and MSQL, the multidatabase version of SQL, is also investigated.