Abstract O'Neill (The genuine Sieve of Eratosthenes. J. Funct. Program . 19 (1), 2009, 95–106) has previously considered a functional implementation for the genuine Sieve of Eratosthenes, based on the well-known heap data structure. Here, we develop it further by adapting this data structure to this particular application.

Searching statistically significant association rules is an important but neglected problem. Traditional association rules do not capture the idea of statistical dependence and the resulting rules can be spurious, while the most significant rules may be missing. This leads to erroneous models and predictions which often become expensive.The problem is computationally very difficult, because the significance is not a monotonic property. However, in this paper we prove several other properties, which can be used for pruning the search space. The properties are implemented in the StatApriori algorithm, which searches statistically significant, non-redundant association rules. Based on both theoretical and empirical observations, the resulting rules are very accurate compared to traditional association rules. In addition, StatApriori can work with extremely low frequencies, thus finding new interesting rules.

Current data management and information retrieval systems lack advanced string processing capabilities needed in string-oriented application areas like computational molecular biology. Several theoretical models for string processing and querying have been proposed but they either have not been implemented in practice or the implementations are too restricted or platform-dependent to be generally useful. We propose a design for a string processing method that could be used to extend different kinds of data management systems by trying to minimise the interconnections between the database management system and the string handling part. The work continues the development of the Alignment Declaration language, our proposal for specifying string relations, by presenting a new and improved method for evaluating the queries and analysing their finiteness.

In order to enable the database programmer to reason about relations over strings of arbitrary length we introduce alignment logic, a modal extension of relational calculus. In addition to relations, a state in the model consists of a two-dimensional array where the strings are aligned on top of each other. The basic modality in the language (a transpose, or “slide”) allows for a rearrangement of the alignment, and more complex formulas can be formed using a syntax reminiscent of regular expressions, in addition to the usual connectives and quantifiers. It turns out that the computational counterpart of the string-based portion of the logic is the class of multitape two-way finite state automata, which are devices particularly well suited for the implementation of string matching. A computational counterpart of the full logic is obtained from relational algebra by extending the selection operator into filters based on these multitape machines. Safety of formulas in alignment logic implies that new strings generated from old ones have to be of bounded length. While an undecidable property in general, this boundedness is decidable for an important subclass of formulas. As far as expressive power is concerned, alignment logic includes previous proposals for querying string databases, and gives full Turing computability. The language can be restricted to define exactly regular sets and sets in the polynomial hierarchy.