XML queries can be modeled by twig pattern queries (TPQs) specifying predicates on XML nodes and XPath relationships satisfied between them. A lot of TPQ types have been proposed; this paper takes into account a TPQ model extended by a specification of output and non-output query nodes since it complies with the XQuery semantics and, in many cases, it leads to a more efficient query processing. In general, there are two types of approaches to process a TPQ: holistic joins and binary joins. Whereas the binary join approach builds a query plan as a tree of interconnected binary operators, the holistic join approach evaluates a whole query using one operator (i.e., using one complex algorithm). Surprisingly, a thorough analytical and experimental comparison is still missing despite an enormous research effort in this area. In this paper, we try to fill this gap; we analytically and experimentally show that the binary joins used in a fully-pipelined plan (i.e., the plan where each join operation does not wait for the complete result of the previous operation and no explicit sorting is used) can often outperform the holistic joins, especially for TPQs with a higher ratio of non-output query nodes. The main contributions of this paper can be summarized as follows: (i) we introduce several improvements of existing binary join approaches allowing to build a fully-pipelined plan for a TPQ considering non-output query nodes, (ii) we prove that for a certain class of TPQs such a plan has the linear time complexity with respect to the size of the input and output as well as the linear space complexity with respect to the XML document depth (i.e., the same complexity as the holistic join approaches), (iii) we show that our improved binary join approach outperforms the holistic join approaches in many situations, and (iv) we propose a simple combined approach that utilizes advantages of both types of approaches.

Structural XQuery and XPath queries are often modeled by twig pattern queries (TPQs) specifying predicates on XML nodes and structural relationships to be satisfied between them. This paper considers a TPQ model extended by a specification of output and non-output query nodes since it complies with the XQuery and XPath semantics. There are two types of TPQ processing approaches: binary joins and holistic joins. The binary joins utilize a query plan of interconnected binary operators, whereas the holistic joins are based on one complex operator to process the whole query. In the recent years, the holistic joins have been considered as the state-of-the-art TPQ processing method. However, a thorough analytical and experimental comparison of binary and holistic joins has been missing despite an enormous research effort in this area. In this paper, we try to fill this gap. We introduce several improvements of the binary join operators which enable us to build a so-called fully-pipelined (FP) query plan for any TPQ with the specification of output and non-output query nodes. We analytically show that, for a class of queries, the proposed approach has the same time and space complexity as holistic joins, and we experimentally demonstrate that the proposed approach outperforms holistic joins in many cases.

Keyword search over relational databases has gained popularity as it provides a user-friendly way to explore structured data. Current research in keyword search has largely ignored queries to retrieve statistical information from the database. The work in [13] extends keywords by supporting aggregate functions in their SQAK system. However, SQAK does not consider the semantics of objects and relationships in the database, and thus suffers from the problems of returning incorrect answers. In this work, we propose a semantic approach to answer keyword queries involving aggregates and GROUPBY. Our approach utilizes the ORM schema graph to capture the Object-Relationship-Attribute (ORA) semantics in the database, and determines the various interpretations of a query before generating the corresponding SQL statements. These semantics enable us to distinguish objects with the same attribute value and detect duplications of objects in relationships to compute the answers correctly. Our approach can also handle unnormalized relations in the database and GROUPBY in keyword queries which SQAK cannot. Experiments on the TPC-H and ACM Digital Library publication datasets demonstrate the advantages of the proposed semantic approach in retrieving correct statistical information for users.

Keyword search over relational databases has gained popularity due to its ease of use. Current research has focused on the efficient computation of results from multiple tuples, and largely ignores queries to retrieve statistical information from databases. The work in [5] developed a system that allows aggregate functions to be expressed using simple keywords. However, this system may return incorrect answers because it does not consider the semantics of objects and relationships in the database. In this paper, we present an interactive keyword search engine called PowerQ to answer queries involving aggregate functions and GROUPBY. PowerQ utilizes an ORM schema graph to capture the Object-Relationship-Attribute (ORA) semantics in the database. Given a keyword query, PowerQ identifies the various interpretations of the query and applies aggregate functions and GROUPBY on the appropriate attributes of objects/relationships. Each query interpretation is denoted as an annotated query pattern, whose meaning can be described in natural language to facilitate user understanding. Through user interactions, PowerQ can determine the user’s search intention, and translate the corresponding patterns into SQLs to compute the answers correctly. The PowerQ prototype is available at http://powerq.comp.nus.edu.sg.

In the world of academia, research documents enable the sharing and dissemination of scientific discoveries. During these “big data” times, academic search engines are widely used to find the relevant research documents. Considering the domain of computer science, a researcher often inputs a query with a specific goal to find an algorithm or a theorem. However, to this date, the return result of most search engines is just as a list of related papers. Users have to browse the results, download the interesting papers and look for the desired information, which is obviously laborious and inefficient. In this paper, we present a novel academic search system, called PandaSearch, that returns the results with a fine-grained interface, where the results are well organized by different categories, such as definitions, theorems, lemmas, algorithms and figures. The key technical challenges in our system include the automatic identification and extraction of different parts in a research document, the discovery of the main topic phrases for a definition or a theorem, and the recommendation of related definitions or figures to elegantly satisfy the search intention of users. Based on this, we have built a user friendly search interface for users to conveniently explore the documents, and find the relevant information.

Due to the intrinsic ambiguity of keyword queries, users usually need to reformulate their queries multiple times to get the desired information. Even worse, users either have no way to precisely specify their search intention, or have limited domain knowledge on the data to precisely express their search intention. Moreover, they may just have a general interest to explore the data by keyword query. Therefore, our goal is to design an exploratory search paradigm that is able to bring humans more actively into the search process, in order to meet various user information needs, ranging from simple lookup to learning and understanding of the data.

Keyword search in relational databases has gained popularity due to its ease of use. However, the challenge to return query answers that satisfy users' information need remains. Traditional keyword queries have limited expressive capability and are ambiguous. In this work, we extend keyword queries to enhance their expressive power and describe an semantic approach to process these queries. Our approach considers keywords that match meta-data such as the names of relations and attributes, and utilizes them to provide the context of subsequent keywords in the query. Based on the ORM schema graph which captures the semantics of objects and relationships in the database, we determine the objects and relationships referred to by the keywords in order to infer the search target of the query. Then, we construct a set of minimal connected graphs called query patterns, to represent user's possible search intentions. Finally, we translate the top-k ranked query patterns into SQL statements in order to retrieve information that the user is interested in. We develop a system prototype called ExpressQ to process the extended keyword queries. Experimental results show that our system is able to generate SQL statements that retrieve user intended information effectively.

When users issue a query to a database, they have expectations about the results. If what they search for is unavailable in the database, the system will return an empty result or, worse, erroneous mismatch results.We call this problem the MisMatch Problem. In this paper, we solve the MisMatch problem in the context of XML keyword search. Our solution is based on two novel concepts that we introduce: Target Node Type and Distinguishability. Using these concepts, we develop a low-cost post-processing algorithm on the results of query evaluation to detect the MisMatch problem and generate helpful suggestions to users. Our approach has three noteworthy features: (1) for queries with the MisMatch problem, it generates the explanation, suggested queries and their sample results as the output to users, helping users judge whether the MisMatch problem is solved without reading all query results; (2) it is portable as it can work with any LCA-based matching semantics and is orthogonal to the choice of result retrieval method adopted; (3) it is lightweight in the way that it occupies a very small proportion of the whole query evaluation time. Extensive experiments on three real datasets verify the effectiveness, efficiency and scalability of our approach. A search engine called XClear has been built and is available at http://xclear.comp.nus.edu.sg.

For keyword search on XML data, traditionally, a list of query results in the form of subtrees will be returned to users. However, we find that it is still not sufficient to meet users' information needs because: (1) the search intention of a certain keyword query varies from person to person; (2) amongst the query results, they may have sibling or containment relationships (in the context of whole XML database), which could be important for users to digest the query results and should be shown to users. Therefore, we try to equip the traditional XML keyword search engine with our new exploration model XMAP, providing user an interactive yet novel way to explore the results with better user experience.

In this demo, we study one category of query refinement problems in the context of XML keyword search, where what users search for do not exist in the data while useless results are returned by the search engine. It is a hidden but important problem. We refer to it as the MisMatch problem. We propose a practical yet efficient way to detect the MisMatch problem and generate helpful suggestions to users, namely MisMatch detector and suggester. Our approach can be viewed as a post-processing job of query evaluation. An online XML keyword search engine embedding the MisMatch detector and suggester has been built and is available at [1].

The existing query languages for XML (e.g., XQuery) require professional programming skills to be formulated, however, such complex query languages burden the query processing. In addition, when issuing an XML query, users are required to be familiar with the content (including the structural and textual information) of the hierarchical XML, which is diffcult for common users. The need for designing user friendly interfaces to reduce the burden of query formulation is fundamental to the spreading of XML community. We present a twig-based XML graphical search system, called LotusX, that provides a graphical interface to simplify the query processing without the need of learning query language and data schemas and the knowledge of the content of the XML document. The basic idea is that LotusX proposes "position-aware" and "auto-completion" features to help users to create tree-modeled queries (twig pattern) by providing the possible candidates on-the-fly. In addition, complex twig queries (including order sensitive queries) are supported in LotusX. Furthermore, a new ranking strategy and a query rewriting solution are implemented to rank and rewrite the query effectively. We provide an online demo for LotusX system: http://datasearch.ruc.edu.cn:8080/LotusX.

In this paper, we focus on efficient keyword query processing for XML data based on the SLCA and ELCA semantics. We propose a novel form of inverted lists for keywords which include IDs of nodes that directly or indirectly contain a given keyword. We propose a family of efficient algorithms that are based on the set intersection operation for both semantics. We show that the problem of SLCA/ELCA computation becomes finding a set of nodes that appear in all involved inverted lists and satisfy certain conditions. We also propose several optimization techniques to further improve the query processing performance. We have conducted extensive experiments with many alternative methods. The results demonstrate that our proposed methods outperform previous methods by up to two orders of magnitude in many cases.

Twig pattern matching is a critical operation for XML query processing, and the holistic computing approach has shown superior performance over other methods. Since Bruno et al. introduced the first holistic twig join algorithm, TwigStack, numerous so-called holistic twig join algorithms have been proposed. Yet practical XML queries often require support for more general twig patterns, such as the ones that allow arbitrary occurrences of an arbitrary number of logical connectives (AND, OR, and NOT); such types of twigs are referred to as B-twigs (i.e., Boolean-Twigs) or AND/OR/NOT-twigs. We have seen interesting work on generalizing the holistic twig join approach to AND/OR-twigs and AND/NOT-twigs, but have not seen any further effort addressing the problem of AND/OR/NOT-Twigs at the full scale, which therefore forms the main theme of this paper. In this paper, we investigate novel mechanisms for efficient B-twig pattern matching. In particular, we introduce “B-twig normalization” as an important first-step in our approach toward eventually conquering the complexity of B-twigs, and then present BTwigMerge-the first holistic twig join algorithm designed for B-twigs. Both analytical and experimental results show that BTwigMerge is optimal for B-twig patterns with AD (Ancestor-Descendant) edges and/or PC (Parent-Child) edges.

Dynamic XML labeling schemes have important applications in XML Database Management Systems. In this paper, we explore dynamic XML labeling schemes from a novel order-centric perspective. We compare the various labeling schemes proposed in the literature with a special focus on their orders of labels. We show that the order of labels fundamentally impacts the update performance of a labeling scheme and develop an order-based framework to classify and characterize XML labeling schemes. Although there are dynamic XML labeling schemes that can completely avoid relabeling, the gain in update performance all come with considerable costs such as larger label size and lower query performance, even if the XML documents are hardly updated. We introduce vector order which is the foundation of the dynamic labeling schemes we propose. Compared with previous solutions that are based on natural order or lexicographical order, vector order is a simple, yet most effective solution to process updates in XML DBMS. We show that vector order can be gracefully applied to both range-based and prefix-based labeling schemes with little overhead introduced. Moreover, vector order-based labeling schemes are not only efficient to process, but also resilient to skewed insertions. Qualitative and experimental evaluations confirm the benefits of our approach compared to previous solutions.

As business and enterprises generate and exchange XML data more often, there is an increasing need for efficient processing of queries on XML data. Searching for the occurrences of a tree pattern query in an XML database is a core operation in XML query processing. Prior works demonstrate that holistic twig pattern matching algorithm is an efficient technique to answer an XML tree pattern with parent-child (P-C) and ancestor-descendant (A-D) relationships, as it can effectively control the size of intermediate results during query processing. However, XML query languages (e.g., XPath and XQuery) define more axes and functions such as negation function, order-based axis, and wildcards. In this paper, we research a large set of XML tree pattern, called extended XML tree pattern, which may include P-C, A-D relationships, negation functions, wildcards, and order restriction. We establish a theoretical framework about “matching cross” which demonstrates the intrinsic reason in the proof of optimality on holistic algorithms. Based on our theorems, we propose a set of novel algorithms to efficiently process three categories of extended XML tree patterns. A set of experimental results on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our proposed theories and algorithms.

Keyword search over XML data usually brings irrelevant results especially when the keywords in a user query have ambiguities. We demonstrate a statistic-based approach to identify the search targets and constraints of a user query in the presence of keyword ambiguities, and come out a relevance oriented result ranking scheme called XML TF*IDF. Since the search intention of a same query may even vary from user to user, we provide an interactive search strategy by allowing user to simply tick their desired search targets from a list of suggestions recommended by the search engine. In this way, we can acquire more precise results and also take the burden of learning the schema of XML data off users.

Inspired by the great success of information retrieval (IR) style keyword search on the web, keyword search on XML has emerged recently. The difference between text database and XML database results in three new challenges: 1) Identify the user search intention, i.e., identify the XML node types that user wants to search for and search via. 2) Resolve keyword ambiguity problems: a keyword can appear as both a tag name and a text value of some node; a keyword can appear as the text values of different XML node types and carry different meanings; a keyword can appear as the tag name of different XML node types with different meanings. 3) As the search results are subtrees of the XML document, new scoring function is needed to estimate its relevance to a given query. However, existing methods cannot resolve these challenges, thus return low result quality in term of query relevance. In this paper, we propose an IR-style approach which basically utilizes the statistics of underlying XML data to address these challenges. We first propose specific guidelines that a search engine should meet in both search intention identification and relevance oriented ranking for search results. Then, based on these guidelines, we design novel formulae to identify the search for nodes and search via nodes of a query, and present a novel XML TF*IDF ranking strategy to rank the individual matches of all possible search intentions. To complement our result ranking framework, we also take the popularity into consideration for the results that have comparable relevance scores. Lastly, extensive experiments have been conducted to show the effectiveness of our approach.

Inspired by the great success of information retrieval (IR) style keyword search on the Web, keyword search on XML has emerged recently. The difference between text database and XML database results in three new challenges: (1) Identify the user search intention, i.e. identify the XML node types that user wants to search for and search via. (2) Resolve keyword ambiguity problems: a keyword can appear as both a tag name and a text value of some node; a keyword can appear as the text values of different XML node types and carry different meanings. (3) As the search results are sub-trees of the XML document, new scoring function is needed to estimate its relevance to a given query. However, existing methods cannot resolve these challenges, thus return low result quality in term of query relevance. In this paper, we propose an IR-style approach which basically utilizes the statistics of underlying XML data to address these challenges. We first propose specific guidelines that a search engine should meet in both search intention identification and relevance oriented ranking for search results. Then based on these guidelines, we design novel formulae to identify the search for nodes and search via nodes of a query, and present a novel XML TF*IDF ranking strategy to rank the individual matches of all possible search intentions. Lastly, the proposed techniques are implemented in an XML keyword search engine called XReal, and extensive experiments show the effectiveness of our approach.

Labeling schemes lie at the core of query processing for many XML database management systems. Designing labeling schemes for dynamic XML documents is an important problem that has received a lot of research attention. Existing dynamic labeling schemes, however, often sacrifice query performance and introduce additional labeling cost to facilitate arbitrary updates even when the documents actually seldom get updated. Since the line between static and dynamic XML documents is often blurred in practice, we believe it is important to design a labeling scheme that is compact and efficient regardless of whether the documents are frequently updated or not. In this paper, we propose a novel labeling scheme called DDE (for Dynamic DEwey) which is tailored for both static and dynamic XML documents. For static documents, the labels of DDE are the same as those of dewey which yield compact size and high query performance. When updates take place, DDE can completely avoid re-labeling and its label quality is most resilient to the number and order of insertions compared to the existing approaches. In addition, we introduce Compact DDE (CDDE) which is designed to optimize the performance of DDE for insertions. Both DDE and CDDE can be incorporated into existing systems and applications that are based on dewey labeling scheme with minimum efforts. Experiment results demonstrate the benefits of our proposed labeling schemes over the previous approaches.

Since more and more business data are represented in XML format, there is a compelling need of supporting analytical operations in XML queries. Particularly, the latest version of XQuery proposed by W3C, XQuery 1.1, introduces a new construct to explicitly express grouping operation in FLWOR expression. Existing works in XML query processing mainly focus on physically matching query structure over XML document. Given the explicit grouping operation in a query, how to efficiently compute grouping and aggregate functions over XML document is not well studied yet. In this paper, we extend our previous XML query processing algorithm, VERT, to efficiently perform grouping and aggregate function in queries. The main technique of our approach is introducing relational tables to index values. Query pattern matching and aggregation computing are both conducted with table indices. We also propose two semantic optimizations to further improve the query performance. Finally we present experimental results to validate the efficiency of our approach, over other existing approaches.

It is important to process the updates when nodes are inserted into or deleted from the XML tree. All the existing labeling schemes have high update cost, thus in this paper we propose a novel Compact Dynamic Binary String (CDBS) encoding to efficiently process the updates. CDBS has two important properties which form the foundations of this paper: (1) CDBS supports that codes can be inserted between any two consecutive CDBS codes with the orders kept and without re-encoding the existing codes; (2) CDBS is orthogonal to specific labeling schemes, thus it can be applied broadly to different labeling schemes or other applications to efficiently process the updates. We report our experimental results to show that our CDBS is superior to previous approaches to process updates in terms of the number of nodes to re-label and the time for updating.

In this article, we propose a framework, called XAR-Miner, for mining ARs from XML documents efficiently. In XAR-Miner, raw data in the XML document first are preprocessed to transform either to an Indexed XML Tree (IX-tree) or to Multirelational Databases (Multi-DB), depending on the size of the XML document and the memory constraint of the system, for efficient data selection and AR mining. Concepts that are relevant to the AR mining task are generalized to produce generalized metapatterns. A suitable metric is devised for measuring the degree of concept generalization in order to prevent undergeneralization or overgeneralization. Resulting generalized metapatterns are used to generate large ARs that meet the support and confidence levels. A greedy algorithm is also presented in order to integrate data selection and large itemset generation to enhance the efficiency of the AR mining process. The experiments conducted show that XAR-Miner is more efficient in performing a large number of AR mining tasks from XML documents than the state-of-the-art method of repetitively scanning through XML documents in order to perform each of the mining tasks.

The method of assigning labels to the nodes of the XML tree is called a labeling scheme. Based on the labels only, both ordered and un-ordered queries can be processed without accessing the original XML file. One more important point for the labeling scheme is the label update cost in inserting or deleting a node into or from the XML tree. All the current labeling schemes have high update cost, therefore in this paper we propose a novel quaternary encoding approach for the labeling schemes. Based on this encoding approach, we need not re-label any existing nodes when the update is performed. Extensive experimental results on the XML datasets illustrate that our QED works much better than the existing labeling schemes on the label updates when considering either the number of nodes or the time for re-labeling.

The basic relationships to be determined in XML query processing are ancestor-descendant (A-D), parent-child (P-C), sibling and ordering relationships. The containment labeling scheme can determine the A-D, P-C and ordering relationships fast, but it is very expensive in determining the sibling relationship. The prefix labeling scheme can determine all the four basic relationships fast if the XML tree is shallow. However, if the XML tree is deep, the prefix scheme is inefficient since the prefix is long. Furthermore, the prefix label is repeated by all the siblings (only the self labels of these siblings are different). Thus in this paper, we propose the P-Containment and P-Prefix schemes which can determine all the four basic relationships faster no matter what the XML structure is; meanwhile P-Prefix can reduce the redundancies in the prefix labeling scheme.

Searching for all occurrences of a twig pattern in an XML document is an important operation in XML query processing. Recently a holistic method TwigStack. [2] has been proposed. The method avoids generating large intermediate results which do not contribute to the final answer and is CPU and I/O optimal when twig patterns only have ancestor-descendant relationships. Another important direction of XML query processing is to build structural indexes [3][8][13][15] over XML documents to avoid unnecessary scanning of source documents. We regard XML structural indexing as a technique to partition XML documents and call it streaming scheme in our paper. In this paper we develop a method to perform holistic twig pattern matching on XML documents partitioned using various streaming schemes. Our method avoids unnecessary scanning of irrelevant portion of XML documents. More importantly, depending on different streaming schemes used, it can process a large class of twig patterns consisting of both ancestor-descendant and parent-child relationships and avoid generating redundant intermediate results. Our experiments demonstrate the applicability and the performance advantages of our approach.

We study the representation, derivation and utilization of a special kind of constraints in multidatabase systems. A major challenge is when component database schemas are schematic discrepant from each other, i.e., data values of one database correspond to schema labels of another. We propose "qualified functional dependencies" (or qualified FDs), an extension to conventional FDs to formalize integrity constraints in multidatabase systems. We first give inference rules to derive qualified FDs in fixed schemas, then study the derivation of qualified FDs during the transformations between schematic discrepant schemas. Propagation rules are given to derive qualified FDs of transformed schemas from qualified FDs of original schemas. Our work can be used in different stages of building and accessing a multidatabase system, e.g., to detect and resolve value inconsistency in schema integration, to verify lossless schema transformations, to normalize integrated schemas, to verify the integrity of data, and to optimize queries at an integration level. In particular, as an application of our theory, we will use FDs to check the validity of SchemaSQL views (SchemaSQL is a powerful multidatabase language).

With the growing importance of semi-structure data in information exchange, much research has been done to provide an effective mechanism to match a twig query in an XML database. A number of algorithms have been proposed recently to process a twig query holistically. Those algorithms are quite efficient for quires with only ancestor-descendant edges. But for queries with mixed ancestor-descendant and parent-child edges, the previous approaches still may produce large intermediate results, even when the input and output size are more manageable. To overcome this limitation, in this paper, we propose a novel holistic twig join algorithm, namely TwigStackList. Our main technique is to look-ahead read some elements in input data steams and cache limited number of them to lists in the main memory. The number of elements in any list is bounded by the length of the longest path in the XML document. We show that TwigStackList is I/O optimal for queries with only ancestor-descendant relationships below branching nodes. Further, even when queries contain parent-child relationship below branching nodes, the set of intermediate results in TwigStackList is guaranteed to be a subset of that in previous algorithms. We complement our experimental results on a range of real and synthetic data to show the significant superiority of TwigStackList over previous algorithms for queries with parent-child relationships.

The increase in the use of XML (eXtensible Markup Language) makes the semistructured data more and more important on the Web. To exploit the full power of XML documents, a query language for semistructured data will be a promising and interesting application. However, the XQuery standard released by W3C is too difficult for common users to use. Some XML graphical query languages for semistructured data have been proposed but they are either too complex or too limited in use. We introduce a graphical query language for semistructured data, which we call GLASS. GLASS is developed on the base of ORA-SS data model, a semantically richer data model for semistructured data In GLASS, we combine the advantages of graphs and texts, which make the graphical language much clear and easy to use. The paper presents the notations and basic capabilities of GLASS via a series of examples with increasingly complexity. We also discuss some complex query examples such as order, group entity, negation and IF-THEN statement.

With the rapid growth of on-line information available, text classification is becoming more and more important. kNN is a widely used text classification method of high performance. However, this method is inefficient because it requires a large amount of computation for evaluating the similarity between a test document and each training document. In this paper, we propose a fast kNN text classification approach based on pruning the training corpus. By using this approach, the size of training corpus can be condensed sharply so that time-consuming on kNN searching can be cut off significantly, and consequently classification efficiency can be improved substantially while classification performance is preserved comparable to that of without pruning. Effective, algorithm for text corpus pruning is designed. Experiments over the Reuters corpus are carried out, which validate the practicability of the proposed approach. Our approach is especially suitable for on-line text classification applications.

In decision support systems, having knowledge on the top k values is more informative and crucial than the maximum value. Unfortunately, the naive method involves high computational cost and the existing methods for range-max query are inefficient if applied directly. In this paper, we propose a Pre-computed Partition Top method (PPT) to partition the data cube and pre-store a number of top values for improving query performance. The main focus of this study is to find the optimum values for two parameters, i.e., the partition factor (b) and the number of pre-stored values (r), through analytical approach. A cost function based on Poisson distribution is used for the analysis. The analytical results obtained are verified against simulation results. It is shown that the PPT method outperforms other alternative methods significantly when proper b and r are used.

With the increasing popularity of data-centric XML, data warehousing and mining applications are being developed for rapidly burgeoning XML data repositories. Data quality will no doubt be a critical factor for the success of such applications. Data cleaning, which refers to the processes used to improve data quality, has been well researched in the context of traditional databases. In earlier work we developed a knowledge-based framework for data cleaning relational databases. In this work, we present a novel attempt to apply this framework to XML databases. Our experimental dataset is the DBLP database, a popular online XML bibliography database used by many researchers.

Extracting data from XML documents is an important issue for XML research and development. However, how XML documents are viewed determines how they can be queried. We first describe a natural way of viewing XML documents as in complex object data models so that we can easily comprehend XML data from a database point of view. We then illustrate how to use logical variables to extract data from XML documents. We also describe a rule-based declarative query language for XML. We demonstrate that our rule-based language provides a uniform framework that has the following advantages over other XML query languages including XQuery. First, it provides a natural way of separating querying and result constructing using the body and head respectively. Second, several rules can be used for the same query so that complex queries can be expressed in a simple and natural way. Also, its use of logical variables and rules makes many functions and operators in XQuery and XPath unnecessary or definable constructively. Finally, it provides natural and direct support for recursion as in deductive databases and has logical foundations that have played a significant role in database research in the past.

We propose to use object-relational database management systems to store and manage semi-structured data. ORA-SS (Object-Relationship-Attribute model for Semi-Structured data) (Dobbie et al., 2000) is used as the data model. It not only reflects the nested structure of semi-structured data, but also distinguishes between object classes and relationship types, and between attributes of object classes and attributes of relationship types. ORA-SS can specify the degree of n-ary relationship types and indicate if an attribute is an attribute of a relationship type or an attribute of an object class. Existing semi-structured data models cannot specify such information. We use this information to translate XML Schemas/DTD to ORA-SS schemas, then to object-relational databases correctly and without avoidable redundancy. The existing techniques have a lot of redundancy in storage and introduce node IDs of the tree instance which are not needed in our approach.

Data dependencies play an important role in the design of a database. Many legacy database applications have been developed on old generation database management systems and conventional file systems. As a result, most of the data dependencies in legacy databases are not enforced in the database management systems. As such, they are not explicitly defined in database schema and are enforced in the transactions, which update the databases. It is very difficult and time consuming to find out the designed data dependencies manually during the maintenance and reengineering of database applications. In software engineering, program analysis has long been developed and proven as a useful aid in many areas. With the use of program analysis, this paper proposes a novel approach for the recovery of common data dependencies, i.e., functional dependencies, key constraints, inclusion dependencies, referential constraints, and sum dependencies, designed in a database from the behavior of transactions, which update the database. The approach is based on detecting program path patterns for implementing most commonly used methods to enforce these data dependencies.

Over the past decade, a large number of deductive object-oriented database languages have been proposed. The earliest of these languages had few object-oriented features, and more and more features have systematically been incorporated in successive languages. However, a language with a clean logical semantics that naturally accounts for all the key object-oriented features, is still missing from the literature. This article takes us another step towards solving this problem. Two features that are currently missing are the encapsulation of rule-based methods in classes, and nonmonotonic structural and behavioral inheritance with overriding, conflict resolution and blocking. This article introduces the syntax of a language with these features. The language is restricted in the sense that we have omitted other object-oriented and deductive features that are now well understood, in order to make our contribution clearer. It then defines a class of databases, called well-defined databases , that have an intuitive meaning and develops a direct logical semantics for this class of databases. The semantics is based on the well-founded semantics from logic programming. The work presented in this article establishes a firm logical foundation for deductive object-oriented databases.

Using materialized view to accelerate OLAP queries is one of the most common methods used in ROLAP systems. However, high storage and computation cost make this method very difficult to be implemented in the actual environment. Among various issues associated with this, index selection and view materialization are two of the top challenges. In this paper, we propose to build indexes on subsets of the primary keys rather than the full sets if the index selectivity for these smaller indexes can be maintained above the required level. Based on that we propose an index filtering rule, Dominant Prime (DPrime) Index Set Filter, to filter out candidate indexes that have insufficient index selectivity or have cheaper alternatives. In the second part, we propose a view materialization method, Nested Relation Approach, to group tuples with the same value for index attributes into one super tuple using a nested relation and implement this method using Oracle VARRAY. In performance tests, our method outperforms others significantly.

Over the past decade, a large number of deductive object-oriented database languages have been proposed. The earliest of these languages had few object-oriented features, and more and more features have systematically been incorporated in successive languages. However, a language with a clean logical semantics that naturally accounts for all the key object-oriented features, is still missing from the literature. Two features that are currently missing are the encapsulation of rule-based methods in classes, and nonmonotonic behavioral inheritance with overriding, conflict resolution and blocking. This paper introduces the syntax of a language with these features. It then defines a class of databases, called well-defined databases, that have an intuitive meaning and develops a direct logical semantics for this class of databases. The semantics is based on the well-founded semantics from logic programming. The work presented in this paper establishes a firm logical foundation for deductive object-oriented databases.

With the recent popularity of the Web, an enormous amount of information is now available online. Most Web documents available over the Web are in HTML format and are hierarchically structured in nature. How to query such Web documents based on their internal hierarchical structure becomes more and more important. We present a rule-based language called WebQL to support effective and flexible Web queries. Unlike other Web query languages, WebQL is a high level declarative query language with a logical semantics. It allows us to query Web documents based on their internal hierarchical structures. It supports not only negation and recursion, but also query result restructuring in a natural way. We also describe the implementation of the system that supports the WebQL query language.

XML is increasingly being adopted for information publishing on the World Wide Web. However, the underlying data is often stored in the relational databases. Some mechanism is needed to convert the relational data into XML data. In this work we employ a semantically rich semistructured data model, the object-relationship-attribute model for semistructured data, as a middleware to support the schema conversion from semantically enriched relational schema to XML schema. This approach allows us to handle the translation of a set of related relations and to distinguish attributes of relationship types from attributes of object classes, multivalued attributes, and different types of relationships such as binary, n-ary, recursive and ISA. The resulting XML structures are able to reflect the inherent semantics and implicit structure in the underlying relational database. We also show that the appropriate use of references is able to avoid unnecessary redundancy and the proliferation of disconnected XML elements.

Most of the data stored in HTML files on the Web are semistructured. Extracting data and packing them into semistructured data models has received a lot of attention recently. We introduce a method that generates wrappers automatically for HTML files. The wrapper is generated from labeled training examples. We use weight-controlled token matching to locate the delimiters of the data of interest to the users. A list of tokens near the data is evaluated and each token is given a weight. We define a list of tokens to be the delimiter if the tokens are so important that the sum of the weights is larger than a threshold. A prototype is designed and a GUI is used to help build wrappers and extract data from the Web. Our method requires a small number of training examples and is flexible enough to deal with missing and misordered items. Compared to other approaches that may be too restrictive, our approach tolerates small modifications of HTML files.

Semistructured data has become prevalent with the growth of the Internet. The development of new web applications that require efficient design and maintenance of large amounts of data makes it increasingly important to design "good" semistructured databases to prevent data redundancy and updating anomalies. However, it is not easy, even impossible, for current semistructured data models to capture the semantics traditionally needed for designing databases. In this paper, we show how an object-relationship-attribute model for semistructured data (ORA-SS) can facilitate the design of "good" semistructured databases. This is accomplished via the normalization of ORA-SS. An XML DTD or Schema generated from a normal form ORA-SS schema diagram has no undesirable redundancy, and thus no updating anomalies for the complying semistructured databases. The general design methodology and detailed steps for converting an ORA-SS schema diagram into a normal form ORA-SS schema diagram are presented. These steps can also be used as guidelines for designing semistructured databases using the ORA-SS model.

Real-life data mining applications are interesting because they often present a different set of problems for data miners.One such real-life application that we have done is on the diabetic patients databases.Valuable lessons are learnt from this application.In particular, we discover that the often neglected pre-processing and post-processing steps in knowledge discovery are the most critical elements in determining the success of a real-life data mining application.In this paper, we shall discuss how we carry out knowledge discovery on this diabetic patient database, the interesting issues that have surfaced, as well as the lessons we have learnt from this application.We will describe a semi-automatic means for cleaning the diabetic patient database, and present a step-by-step approach to help the health doctors explore their data and to understand the discovered rules better.While it is important to generate understandable rules, it is also important to the medical doctors to have a complete picture of all

Existing data cleaning methods work on the basis of computing the degree of similarity be t ween nearby records in a sorted database.High recall is achieved by accepting records with low degrees of similarity as duplicates, at the cost of lower precision.High precision is achieved analogously at the cost of lower recall.This is the r e c all-pr ecision dilemma.In this paper, we propose a generic knowledge-based framework for eective data cleaning that implements existing cleaning strategies and more.We develop a new method to compute transitive closure under uncertaint ywhich handles the merging of groups of inexact duplicate records.Experimental results show that this framework can identify duplicates and anomalies with high recall and precision.

Many algorithms have been proposed in the area of materialized view maintenance. They provide different capabilities and features, and have different complexity in their implementation. Each of these algorithms is suited for some types of applications. The authors propose a model for evaluating the merit of these algorithms. This model would allow a user to choose an appropriate maintenance algorithm according to his application needs. It can also be used as a benchmark where new maintenance algorithms can be evaluated.

A data warehouse stores materialized views over data from one or more sources in order to provide fast access to the integrated data, regardless of the availability of the data sources. We define a new compensation algorithm that is used in removing the anomalies, caused by interfering updates at the base relations, of incremental computation for updating the view. Unlike existing methods on view maintenance, our algorithm does not assume that messages from a data source will reach the view maintenance machinery in the same order as they are generated, and we are also able to detect update notification messages that are lost in their transit to the view, which would otherwise cause the view to be updated incorrectly. These are achieved with the use of version numbers that reflect the states of the base relations. Our algorithm also does not require that the system be quiescent before the view can be refreshed.

Data integration from several sources has gained considerable attention with the recent popularity of the World Wide Web. In the real world, some information may be missing (i.e. partial) and some may be inconsistent from several sources. How to obtain information that is as complete as possible and how to detect inconsistency from these sources is thus an interesting question. Most existing work uses a simple graph-based or tree-based semistructured data model to represent heterogeneous data coming from various sites, which fails to account for the existence of partial and inconsistent information. In this paper, we redefine the notion of semistructured objects to reflect the existence of partial and inconsistent information and study how to integrate such objects spread over various sources and check their consistency in the meantime. We propose a new integration operator for this purpose and discuss its semantic properties.

Classical data dependencies are oblivious to important constraints which may exist between sets of attributes occurring in different relation schemes. The authors study how inclusion dependencies can be used to model these constraints, leading to the design of better database schemes. A normal form called the inclusion normal form (IN-NF) is proposed. Unlike classical normal forms, the IN-NF characterizes a database scheme as a whole rather than the individual relation schemes. It is shown that a database scheme in IN-NF is always in improved third normal form, while the converse is not true. It is demonstrated that the classical relational design framework may be extended to facilitate the design of database schemes in IN-NF.>

In this paper, we show that some Codd third normal form relations may contain “superfluous” attributes because the definitions of transitive dependency and prime attribute are inadequate when applied to sets of relations. To correct this, an improved third normal form is defined and an algorithm is given to construct a set of relations from a given set of functional dependencies in such a way that the superfluous attributes are guaranteed to be removed. This new normal form is compared with other existing definitions of third normal form, and the deletion normalization method proposed is shown to subsume the decomposition method of normalization.