Recently, a lot of research work has been proposed in different domains to detect outliers and analyze the outlierness of outliers for relational data. However, while sequence data is ubiquitous in real life, analyzing the outlierness for sequence data has not received enough attention. In this article, we study the problem of mining outlying sequence patterns in sequence data addressing the question: given a query sequence s in a sequence dataset D , the objective is to discover sequence patterns that will indicate the most unusualness (i.e., outlierness) of s compared against other sequences. Technically, we use the rank defined by the average probabilistic strength ( aps ) of a sequence pattern in a sequence to measure the outlierness of the sequence. Then a minimal sequence pattern where the query sequence is ranked the highest is defined as an outlying sequence pattern. To address the above problem, we present OSPMiner, a heuristic method that computes aps by incorporating several pruning techniques. Our empirical study using both real and synthetic data demonstrates that OSPMiner is effective and efficient.

This paper first introduces a new style of regression models, namely pattern aided regression (PXR) models, aimed at representing accurate and interpretable prediction models. It also introduces a contrast pattern aided regression (CPXR) method, to build accurate PXR models in an efficient manner. In experiments, the PXR models built by CPXR are very accurate in general, often outperforming state-of-the-art regression methods by wide margins. From extensive experiments we also found that (1) regression modeling applications often involve complex diverse predictor-response relationships, which occur when the optimal regression models (of given regression model type) fitting distinct natural subgroups of data are highly different, and (2) state-of-the-art regression methods are often unable to adequately model such relationships. CPXR is also useful for analyzing how a given regression model makes prediction errors. This is an extended abstract of [6].

This paper makes several contributions to research on classification. First, it introduces a new style of classifiers, namely pattern aided classifiers (PXC), each defined by several pattern and group-specific-classifier pairs. A PXC uses patterns as conditions and it applies a group-specific classifier only to data instances satisfying its associated pattern. Second, it introduces a new classification algorithm, called Contrast Pattern Aided Classification (CPXC), for learning accurate PXCs. Experiments over multiple benchmark datasets confirm that CPXC often builds significantly more accurate classifiers than traditional classification algorithms. Third, it introduces the technique of opportunity-guided boosting and the concept of conditional classifier ensembles, and it provides insight on why certain datasets are very challenging to traditional classification algorithms.

Contrast patterns describe differences between two or more data sets or data classes; they have been proven to be useful for solving many kinds of problems, such as building accurate classifiers, defining clustering quality measures, and analyzing disease subtypes. This article investigates the mining of a new kind of contrast patterns, namelydiscriminating inter‐attribute functions(DIFs), which represent arithmetic‐expression‐based inter‐attribute relationships that distinguish classes of data. DIFs are an expressive and practical alternative of item‐based contrast patterns and can express discriminating relationships such as “weight/(height)2is more likely to be ≤25 in one class than in another class.” Besides introducing the DIF mining problem, this article makes theoretical and algorithmic contributions on the problem. We prove that DIF mining is MAX SNP‐hard. Regarding how to efficiently mine DIFs, we present a set of rules to prune the search space of arithmetic expressions by eliminating redundant ones (equivalent to some others). We give two algorithms: one for finding all DIFs satisfying given thresholds and another for finding certain optimal DIFs using genetic computation techniques. The former is useful when the number of attributes is small, whereas the latter is useful when that number is large; both use the redundant arithmetic‐expression pruning rules. A performance study shows that our techniques are effective and efficient for finding DIFs.

Discovering useful patterns in medical time series data such as EEG and EMG recordings is an important step for gaining useful insights into the data and medical problem under investigation, and for building accurate classifiers. However, pattern mining algorithms often require a binning step, which maps the time series data into a representation in terms of discretized values, in order to discover patterns. How the intervals are constructed has a significant impact on the quality of the mined patterns. We propose a novel binning technique, called Distribution Skew-based Binning (or DS Binning), which uses the distribution of the classes associated with the numerical attribute values to construct the intervals. Experiments show that this method outperforms existing binning methods in facilitating the discovery of high quality patterns from multivariate EEG/EMG time series data, leading to higher classification accuracy. Our experiments demonstrate that DS binning can provide approximately a 5-10% improvement in classification accuracy over other binning methods in multiple scenarios.

A wide range of methods have been proposed for detecting different types of outliers in both the full attribute space and its subspaces. However, the interpretability of outliers, that is, explaining in what ways and to what extent an object is an outlier, remains a critical issue. In this paper, we focus on improving the interpretability of outliers. Particularly, we develop a notion of multidimensional contextual outliers to model the context of an outlier, and propose a framework for contextual outlier detection. Intuitively, a contextual outlier is a small group of objects that share strong similarity with a significantly larger reference group of objects on some attributes, but deviate dramatically on some other attributes. In contextual outlier detection, we identify not only the outliers, but also their associated contextual information including (1) comparing to what reference group of objects the detected object(s) is/are an outlier; (2) the attributes defining the unusual behavior of the outlier(s) compared against the reference group; (3) the population of similar outliers sharing the same context; and (4) the outlier degree, which measures the population ratio between the reference group and the outlier group. We present an algorithm and conduct extensive experiments to evaluate our approach.

This paper first introduces pattern aided regression (PXR) models, a new type of regression models designed to represent accurate and interpretable prediction models. This was motivated by two observations: (1) Regression modeling applications often involve complex diverse predictor-response relationships, which occur when the optimal regression models (of given regression model type) fitting two or more distinct logical groups of data are highly different. (2) State-of-the-art regression methods are often unable to adequately model such relationships. This paper defines PXR models using several patterns and local regression models, which respectively serve as logical and behavioral characterizations of distinct predictor-response relationships. The paper also introduces a contrast pattern aided regression (CPXR) method, to build accurate PXR models. In experiments, the PXR models built by CPXR are very accurate in general, often outperforming state-of-the-art regression methods by big margins. Usually using (a) around seven simple patterns and (b) linear local regression models, those PXR models are easy to interpret; in fact, their complexity is just a bit higher than that of (piecewise) linear regression models and is significantly lower than that of traditional ensemble based regression models. CPXR is especially effective for high-dimensional data. The paper also discusses how to use CPXR methodology for analyzing prediction models and correcting their prediction errors.

Prognostic modeling is central to medicine, as it is often used to predict patients' outcome and response to treatments and to identify important medical risk factors. Logistic regression is one of the most used approaches for clinical prediction modeling. Traumatic brain injury (TBI) is an important public health issue and a leading cause of death and disability worldwide. In this study, we adapt CPXR (Contrast Pattern Aided Regression, a recently introduced regression method), to develop a new logistic regression method called CPXR (Log), for general binary outcome prediction (including prognostic modeling), and we use the method to carry out prognostic modeling for TBI using admission time data. The models produced by CPXR (Log) achieved AUC as high as 0.93 and specificity as high as 0.97, much better than those reported by previous studies. Our method produced interpretable prediction models for diverse patient groups for TBI, which show that different kinds of patients should be evaluated differently for TBI outcome prediction and the odds ratios of some predictor variables differ significantly from those given by previous studies, such results can be valuable to physicians.

A wide range of methods have been proposed for detecting different types of outliers in full space and subspaces. However, the interpretability of outliers, that is, explaining in what ways and to what extent an object is an outlier, remains a critical open issue. In this paper, we develop a notion of contextual outliers on categorical data. Intuitively, a contextual outlier is a small group of objects that share strong similarity with a significantly larger reference group of objects on some attributes, but deviate dramatically on some other attributes. We develop a detection algorithm, and conduct experiments to evaluate our approach.

This article addresses the incremental and decremental maintenance of the frequent pattern space. We conduct an in‐depth investigation on how the frequent pattern space evolves under both incremental and decremental updates. Based on the evolution analysis, a new data structure, Generator‐Enumeration Tree (GE‐tree), is developed to facilitate the maintenance of the frequent pattern space. With the concept of GE‐tree, we propose two novel algorithms, Pattern Space Maintainer+ (PSM+) and Pattern Space Maintainer− (PSM−), for the incremental and decremental maintenance of frequent patterns. Experimental results demonstrate that the proposed algorithms, on average, outperform the representative state‐of‐the‐art methods by an order of magnitude.

We study the problem of deciding the satisfiability of first-order logic queries over views, with our aim to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occupy a central place in database research due to their role in applications such as information integration and data warehousing. Our main result is the identification of a decidable class of first-order queries over unary conjunctive views that generalizes the decidability of the classical class of first-order sentences over unary relations known as the Löwenheim class. We then demonstrate how various extensions of this class lead to undecidability and also provide some expressivity results. Besides its theoretical interest, our new decidable class is potentially interesting for use in applications such as deciding implication of complex dependencies, analysis of a restricted class of active database rules, and ontology reasoning.

Since clustering is unsupervised and highly explorative, clustering validation (i.e. assessing the quality of clustering solutions) has been an important and long standing research problem. Existing validity measures have significant shortcomings. This paper proposes a novel contrast pattern based clustering quality index (CPCQ) for categorical data, by utilizing the quality and diversity of the contrast patterns (CPs) which contrast the clusters in clusterings. High quality CPs can characterize clusters and discriminate them against each other. Experiments show that the CPCQ index (1) can recognize that expert-determined classes are the best clusters for many datasets from the UCI repository; (2) does not give inappropriate preference to larger number of clusters; (3) does not require a user to provide a distance function.

Supervised learning on sequence data, also known as sequence classification, has been well recognized as an important data mining task with many significant applications. Since temporal order is important in sequence data, in many critical applications of sequence classification such as medical diagnosis and disaster prediction, early prediction is a highly desirable feature of sequence classifiers. In early prediction, a sequence classifier should use a prefix of a sequence as short as possible to make a reasonably accurate prediction. To the best of our knowledge, early prediction on sequence data has not been studied systematically. In this paper, we identify the novel problem of mining sequence classifiers for early prediction. We analyze the problem and the challenges. As the first attempt to tackle the problem, we propose two interesting methods. The sequential classification rule (SCR) method mines a set of sequential classification rules as a classifier. A so-called early-prediction utility is defined and used to select features and rules. The generalized sequential decision tree (GSDT) method adopts a divide-and-conquer strategy to generate a classification model. We conduct an extensive empirical evaluation on several real data sets. Interestingly, our two methods achieve accuracy comparable to that of the state-of-the-art methods, but typically need to use only very short prefixes of the sequences. The results clearly indicate that early prediction is highly feasible and effective.

Improving the precision of information retrieval has been a challenging issue on Chinese Web. As exemplified by Chinese recipes on the Web, it is not easy/natural for people to use keywords (e.g. recipe names) to search recipes, since the names can be literally so abstract that they do not bear much, if any, information on the underlying ingredients or cooking methods. In this paper, we investigate the underlying features of Chinese recipes, and based on workflow-like cooking procedures, we model recipes as graphs. We further propose a novel similarity measurement based on the frequent patterns, and devise an effective filtering algorithm to prune unrelated data so as to support efficient on-line searching. Benefiting from the characteristics of graphs, frequent common patterns can be mined from a cooking graph database. So in our prototype system called RecipeView, we extend the subgraph mining algorithm FSG to cooking graphs and combine it with our proposed similarity measurement, resulting in an approach that well caters for specific users' needs. Our initial experimental studies show that the filtering algorithm can efficiently prune unrelated cooking graphs without affecting the retrieval performance and the similarity measurement gets a relatively higher precision/recall against its counterparts.

Abstract The recent explosive proliferation of interesting and useful data over the Web such as various recipes, while providing people with readily available information, brings out a challenging issue on how to manage such non‐conventional data effectively. To respond to the challenge, we have been developing a Web‐based recipe database system calledDish_Masterto manage recipes in a novel way, which not only covers the static recipe attributes but also elucidates the dynamic cooking behaviors. In this paper, we present several semantic knowledge facilities devised inDish_Master, including a set of semantic modeling and knowledge constructs to effectively represent recipe data, rules and constraints, and user profile aspects. With such a rich set of semantic knowledge facilities,Dish_Masterlays down a solid foundation of providing users with personalized services such as adaptation and recommendation. Users can benefit from the system's real‐time consultation and automatic summarization of cuisine knowledge. The usefulness and elegance ofDish_Masterare demonstrated through an experimental prototype system. Copyright © 2007 John Wiley & Sons, Ltd.

The iceberg cubing problem is to compute the multidimensional group-by partitions that satisfy given aggregation constraints. Pruning unproductive computation for iceberg cubing when nonantimonotone constraints are present is a great challenge because the aggregate functions do not increase or decrease monotonically along the subset relationship between partitions. In this paper, we propose a novel bound prune cubing (BP-Cubing) approach for iceberg cubing with nonantimonotone aggregation constraints. Given a cube over n dimensions, an aggregate for any group-by partition can be computed from aggregates for the most specific n--dimensional partitions (MSPs). The largest and smallest aggregate values computed this way become the bounds for all partitions in the cube. We provide efficient methods to compute tight bounds for base aggregate functions and, more interestingly, arithmetic expressions thereof, from bounds of aggregates over the MSPs. Our methods produce tighter bounds than those obtained by previous approaches. We present iceberg cubing algorithms that combine bounding with efficient aggregation strategies. Our experiments on real-world and artificial benchmark data sets demonstrate that BP-Cubing algorithms achieve more effective pruning and are several times faster than state-of-the-art iceberg cubing algorithms and that BP-Cubing achieves the best performance with the top-down cubing approach.

As OLAP engines are widely used to support multidimensional data analysis, it is desirable to support in data cubes advanced statistical measures, such as regression and filtering, in addition to the traditional simple measures such as count and average. Such new measures will allow users to model, smooth, and predict the trends and patterns of data. Existing algorithms for simple distributive and algebraic measures are inadequate for efficient computation of statistical measures in a multidimensional space. In this paper, we propose a fundamentally new class of measures, compressible measures, in order to support efficient computation of the statistical models. For compressible measures, we compress each cell into an auxiliary matrix with a size independent of the number of tuples. We can then compute the statistical measures for any data cell from the compressed data of the lower-level cells without accessing the raw data. Time- and space-efficient lossless aggregation formulae are derived for regression and filtering measures. Our analytical and experimental studies show that the resulting system, regression cube, substantially reduces the memory usage and the overall response time for statistical analysis of multidimensional data.

Sensor networks have emerged as a promising technology for large-scale, real-time monitoring in complex environments. This paper develops in-network algorithms for the detection and tracking of region-based targets and events. We deal with such issues as network topology, event boundary detection, region merging, and region simplification and smoothing. Simulation experiments confirmed that our algorithms are efficient and accurate.

Discovering contrasts between collections of data is an important task in data mining. In this paper, we introduce a new type of contrast pattern, called a minimal distinguishing subsequence (MDS). An MDS is a minimal subsequence that occurs frequently in one class of sequences and infrequently in sequences of another class. It is a natural way of representing strong and succinct contrast information between two sequential datasets and can be useful in applications such as protein comparison, document comparison and building sequential classification models. Mining MDS patterns is a challenging task and is significantly different from mining contrasts between relational/transactional data. One particularly important type of constraint that can be integrated into the mining process is the maximum gap constraint. We present an efficient algorithm called ConSGapMiner, to mine all MDSs according to a maximum gap constraint. It employs highly efficient bitset and Boolean operations, for powerful gap based pruning within a prefix growth framework. A performance evaluation with both sparse and dense datasets, demonstrates the scalability of ConSGapMiner and shows its ability to mine patterns from high dimensional datasets at low supports.

The iceberg cube mining computes all cells v, corresponding to GROUP BY partitions, that satisfy a given constraint on aggregated behaviors of the tuples in a GROUP BY partition. The number of cells often is so large that the result cannot be realistically searched without pushing the constraint into the search. Previous works have pushed antimonotone and monotone constraints. However, many useful constraints are neither antimonotone nor monotone. We consider a general class of aggregate constraints of the form f(v)/spl theta//spl sigma/, where f is an arithmetic function of SQL-like aggregates and /spl theta/ is one of. We propose a novel pushing technique, called divide-and-approximate, to push such constraints. The idea is to recursively divide the search space and approximate the given constraint using antimonotone or monotone constraints in subspaces. This technique applies to a class called separable constraints, which properly contains all constraints built by an arithmetic function f of all SQL aggregates.

Given a database, the view maintenance problem is concerned with the efficient computation of the new contents of a given view when updates to the database happen. We consider the view maintenance problem for the situation when the database contains a weighted graph and the view is either the transitive closure or the answer to the all-pairs shortest-distance problem ( APSD ). We give incremental algorithms for APSD , which support both edge insertions and deletions. For transitive closure, the algorithm is applicable to a more general class of graphs than those previously explored. Our algorithms use first-order queries, along with addition (+) and less-than (<) operations ( FO (+,<)); they store O ( n 2 ) number of tuples, where n is the number of vertices, and have AC 0 data complexity for integer weights. Since FO (+,<) is a sublanguage of SQL and is supported by almost all current database systems, our maintenance algorithms are more appropriate for database applications than nondatabase query types of maintenance algorithms.

Many data analysis tasks can be viewed as search or mining in a multidimensional space (MDS). In such MDSs, dimensions capture potentially important factors for given applications, and cells represent combinations of values for the factors. To systematically analyze data in MDS, an interesting notion, called "cubegrade" was recently introduced by Imielinski et al. [2002], which focuses on the notable changes in measures in MDS by comparing a cell (which we refer to as probe cell) with its gradient cells, namely, its ancestors, descendants, and siblings. We call such queries gradient analysis queries (GQs). Since an MDS can contain billions of cells, it is important to answer GQs efficiently. We focus on developing efficient methods for mining GQs constrained by certain (weakly) antimonotone constraints. Instead of conducting an independent gradient-cell search once per probe cell, which is inefficient due to much repeated work, we propose an efficient algorithm, LiveSet-Driven. This algorithm finds all good gradient-probe cell pairs in one search pass. It utilizes measure-value analysis and dimension-match analysis in a set-oriented manner, to achieve bidirectional pruning between the sets of hopeful probe cells and of hopeful gradient cells. Moreover, it adopts a hypertree structure and an H-cubing method to compress data and to maximize sharing of computation. Our performance study shows that this algorithm is efficient and scalable. In addition to data cubes, we extend our study to another important scenario: mining constrained gradients in transactional databases where each item is associated with some measures such as price. Such transactional databases can be viewed as sparse MDSs where items represent dimensions, although they have significantly different characteristics than data cubes. We outline efficient mining methods for this problem.

Iceberg-cube mining is to compute the GROUP BY partitions, for all GROUP BY dimension lists, that satisfy a given aggregate constraint. Previous works have pushed anti-monotone constraints into iceberg-cube mining. However, many useful constraints are not anti-monotone. We propose a novel strategy for pushing general aggregate constraints, called divide-and-approximate. This strategy divides the search space and approximates the constraint in subspaces by a pushable constraint. As the strategy is recursively applied, the approximation approaches the given constraint and the pruning tights up. We show that all constraints defined by SQL aggregates, arithmetic operators and comparison operators can be pushed by divide-and-approximate. We present an efficient implementation for an important subclass and evaluate it on both synthetic and real life databases.

Frequent pattern mining has been studied extensively. However, the effectiveness and efficiency of this mining is often limited, since the number of frequent patterns generated is often too large. In many applications it is sufficient to generate and examine only frequent patterns with support frequency in close-enough approximation instead of in full precision. Such a compact but close-enough frequent pattern base is called a condensed frequent patterns-base. In this paper we propose and examine several alternatives at the design, representation, and implementation of such condensed frequent pattern-bases. A few algorithms for computing such pattern-bases are proposed. Their effectiveness at pattern compression and their efficient computation methods are investigated. A systematic performance study is conducted on different kinds of databases, which demonstrates the effectiveness and efficiency of our approach at handling frequent pattern mining in large databases.

Data cube enables fast online analysis of large data repositories which is attractive in many applications. Although there are several kinds of available cube-based OLAP products, users may still encounter challenges on effectiveness and efficiency in the exploration of large data cubes due to the huge computation space as well as the huge observation space in a data cube. CubeExplorer is an integrated environment for online exploration of data cubes. It integrates our newly developed techniques on iceberg cube computation [2], cube-based feature extraction, and gradient analysis [1], and makes cube exploration effective and efficient. In this demo, we will show the features of CubeExplorer, especially its power and flexibility at exploring and mining of large databases.

It is often too expensive to compute and materialize a complete high-dimensional data cube. Computing an iceberg cube, which contains only aggregates above certain thresholds, is an effective way to derive nontrivial multi-dimensional aggregations for OLAP and data mining.

For an enterprise to take advantage of the opportunities afforded by electronic commerce it must be able to make decisions about business transactions in near-real-time. In the coming era of segment-of-one marketing, these decisions will be quite intricate, so that customer treatments can be highly personalized, reflecting customer preferences, the customer's history with the enterprise, and targeted business objectives. This paper describes a paradigm called "decision flows" for specifying a form of incremental decision-making that can combine diverse business factors in near-real-time. This paper introduces and empirically analyzes a variety of optimization strategies for decision flows that are "data-intensive", i.e. that involve many database queries. A primary focus is on the use of parallelism and eagerness (a.k.a. speculative execution) to minimize work and/or reduce response time. A family of optimization techniques is developed, including algorithms and heuristics for scheduling tasks of the decision flow. Using a prototype execution engine the techniques are compared and analyzed in connection with decision-making applications having differing characteristics.

Emerging patterns (EPs) were proposed recently to capture changes or dierences betw een datasets: an EP is a multivariate feature whose support increases sharply from a background dataset to a target dataset, and the support ratio is called its gro wth rate.Interesting long EPs often have l o w support; mining suc h EPs from high-dimensional datasets is a great challenge due to the combinatorial explosion of the number of candidates.We propose a Constraint-based EP Miner, ConsEPMiner, that utilizes tw o types of constraints for eectively pruning the search space: External constrain tsare user-giv en minimums on support, growth rate, and growth-rate improvement to con ne the resulting EP set.Inheren t constrain ts | same subset support, top growth rate, and same origin | are deriv ed from the propertiesof EPs and datasets, and are solely for pruning the search space and saving computation.ConsEPMiner can eÆciently mine all EPs at low support on large highdimensional datasets, with low minimums on growth rate and growth-rate improvement.In comparison, the widely known Apriori-like approach is ineective on high-dimensional data.While ConsEPMiner adopts several ideas from Dense-Miner [4], a recent constrain t-based association rule miner, its main new contributions are the introduction of inherent constrain ts and the w ays to use them together with externalconstrain ts for eÆcien t EP mining from dense datasets.Experiments on dense data sho w that, at low support, Con-sEPMiner outperforms the Apriori-like approach b y o r d e r s of magnitude and is more than twice as fast as the Dense-Miner approach.D, supp(X), is jft2DjXtgj jDj .

We develop a data integration approach for the efficient evaluation of queries over autonomous source databases. The approach is based on some novel applications and extensions of constraint database techniques. We assume the existence of a global database schema. The contents of each data source are described using a set of constraint tuples over the global schema; each such tuple indicates possible contributions from the source. The "source description catalog" (SDC) of a global relation consists of its associated constraint tuples. Such a method of description is advantageous since it is flexible to add new sources and to modify existing ones. In our framework, to evaluate a conjunctive query over the global schema, a plan generator first identifies relevant data sources by "evaluating" the query against the SDCs using techniques of constraint query evaluation; it then formulates an evaluation plan, consisting of some specialized queries over different paths. The evaluation of a query associated with a path is done by a sequence of partial evaluations at data sources along the path, similar to sideways information passing of Datalog; the partially evaluated queries travel along their associated paths. Our SDC based query planning is efficient since it avoids the NP-complete query rewriting process. We can achieve further optimization using techniques such as emptiness test.

Partial periodicity search, i.e., search for partial periodic patterns in time-series databases, is an interesting data mining problem. Previous studies on periodicity search mainly consider finding full periodic patterns, where every point in time contributes (precisely or approximately) to the periodicity. However, partial periodicity is very common in practice since it is more likely that only some of the time episodes may exhibit periodic patterns. We present several algorithms for efficient mining of partial periodic patterns, by exploring some interesting properties related to partial periodicity such as the Apriori property and the max-subpattern hit set property, and by shared mining of multiple periods. The max-subpattern hit set property is a vital new property which allows us to derive the counts of all frequent patterns from a relatively small subset of patterns existing in the time series. We show that mining partial periodicity needs only two scans over the time series database, even for mining multiple periods. The performance study shows our proposed methods are very efficient in mining long periodic patterns.

We introduce a new kind of patterns, called emerging patterns (EPs), for knowledge discovery from databases. EPs are defined as itemsets whose supports increase significantly from one dataset to another. EPs can capture emerging trends in timestamped databases, or useful contrasts between data classes. EPs have been proven useful: we have used them to build very powerful classifiers, which are more accurate than C4.5 and CBA, for many datasets. We believe that EPs with low to medium support, such as 1%-20%, can give useful new insights and guidance to experts, in even “well understood” applications. The efficient mining of EPs is a challenging problem, since (i) the Apriori property no longer holds for EPs, and (ii) there are usually too many candidates for high dimensional databases or for small support thresholds such as 0.5%. Naive algorithms are too costly. To solve this problem, (a) we promote the description of large collections of itemsets using their concise borders (the pair of sets of the minimal and of the maximal itemsets in the collections). (b) We design EP mining algorithms which manipulate only borders of collections (especially using our multiborder- differential algorithm), and which represent discovered EPs using borders. All EPs satisfying a constraint can be efficiently discovered by our border-based algorithms, which take the borders, derived by Max-Miner, of large itemsets as inputs. In our experiments on large and high dimensional datasets including the US census and Mushroom datasets, many EPs, including some with large cardinality, are found quickly. We also give other algorithms for discovering general or special types of EPs.

Active database systems enhance the functionality of traditional databases through the use of active rules or `triggers'. One of the principal questions for such systems is that of termination - is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. In this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. We present two families of rule languages, the one literal languages where each update is permitted to have just one atom in its body, and the unary languages where only unary relations may be updated, but higher arity relations may be accessed through views. Within each of these, we identify members close to the boundary of (un)decidability. Our context is similar to the while query language and the dynamics gives an interesting contrast to Datalog with negation; our results shed insights on the power of triggers as well as comparison of the termination problem to boundedness and query containment.

The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic Boolean queries expressible in the relational calculus augmented with a given class of constraints coincides with the class of queries expressible in the relational calculus (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic Boolean queries under both the natural and active-domain semantics. In the course of proving these results for the active-domin semantics, we establish Ramsey-type theorems saying that any query involving certain kinds of constraints coincides with a constraint-free query on databases whose elements come from a certain infinite subset of the domain. To prove the collapse results for the natural semantics, we make use of techniques from nonstandard analysis and from the model theory of ordered structures.

The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic Boolean queries expressible in the relational calculus augmented with a given class of constraints coincides with the class of queries expressible in the relational calculus (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic Boolean queries under both the natural and active-domain semantics.In the course of proving these results for the active-domin semantics, we establish Ramsey-type theorems saying that any query involving certain kinds of constraints coincides with a constraint-free query on databases whose elements come from a certain infinite subset of the domain. To prove the collapse results for the natural semantics, we make use of techniques from nonstandard analysis and from the model theory of ordered structures.

After inserting a tuple into (or deleting a tuple from) a database, a "first-order incremental evaluation system" (or "foies") for a database query derives the new query answer by using a non recursive or first-order query on the new database, the old answer, and perhaps some (stored) auxiliary relations.Furthermore, the auxiliary relations must also be maintained in the same manner, i.e., derived using first-order queries.In this paper we measure the space needed by foies in terms of the maximal arity of the auxiliary relations and present results on existence and nonexistence of space restricted foies for a variety of conventional queries.We construct space efficient foies for these queries, and show that the space bounds are tight using a variation of Ehrenfeucht-Fraiss6 games.In particular, we show that, for transitive closure over undirected graphs, the minimum space bound of its foies is exactly 2; this resolves an open problem raised by Patnaik and Immerman in PODS '94. 1 Introduction Recently, there have been research interests focusing on incremental evaluations of database queries [BLT86, AP87, Kuc91, WDSY91, DT92, DS93a, DS93b, DST93, DS95, GMS93, P194, RRSS94].In par-

A chain query seeks, for each input database (viewed as directed graph), all pairs of start and end nodes of paths whose labels spell words in an associated (possibly non context-free) language over some binary predicates. We study the expressive power of Datalog for chain queries. Extending context-free productions with labels, we introduce a new tool called “indexed positive programmed grammarr” (IPPG). Three variations of IPPG are introduced to characterize chain queries computable (i) by linear Datalog, (ii) by “semi-linear Datalog”, and (iii) by general Datalog, respectively, under a natural “addressable” condition.

We consider distributed or parallel processing of datalog queries. We address this issue by decomposing databases into a number of subdatabases such that the computation of a program on a database can be achieved by unioning its independent evaluations on the subdatabases. More specifically, we identify two kinds of distributed-processible programs according to the properties of database decomposition. (i) A program is disjoint distributive if it is distributed processible over a decomposition consisting of subdatabases with disjoint domains. A characterization of such programs is given in terms of an easily decidable syntactic property called connectivity. (ii) A program is bounded distributive if it is distributed processible over a decomposition consisting of subdatabases with a fixed size. Three interesting characterizations of such a program are presented, the first by bounded recursion, the second by equivalence to a 1-bounded-recursive program, and the third by constant parallel complexity