The Experts below are selected from a list of 31551 Experts worldwide ranked by ideXlab platform
Yip Chi Lap - One of the best experts on this subject based on the ideXlab platform.
-
SF-Tree: An efficient and flexible structure for estimating selectivity of simple Path Expressions with statistical accuracy guarantee
Lecture Notes in Computer Science, 2004Co-Authors: Ben Kao, David W. Cheung, Yip Chi LapAbstract:Estimating the selectivity of a simple Path Expression (SPE) is essential for selecting the most efficient evaluation plans for XML queries. To estimate selectivity, we need an efficient and flexible structure to store a summary of the Path Expressions that are present in an XML document collection. In this paper we propose a new structure called SF-Tree to address the selectivity estimation problem. SF-Tree provides a flexible way for the users to choose among accuracy, space requirement and selectivity retrieval speed. It makes use of signature files to store the SPEs in a tree form to increase the selectivity retrieval speed and the accuracy of the retrieved selectivity. Our analysis shows that the probability that a selectivity estimation error occurs decreases exponentially with respect to the error size.
-
DASFAA - SF-Tree: An efficient and flexible structure for estimating selectivity of simple Path Expressions with statistical accuracy guarantee
Database Systems for Advanced Applications, 2004Co-Authors: Ben Kao, David W. Cheung, Yip Chi LapAbstract:Estimating the selectivity of a simple Path Expression (SPE) is essential for selecting the most efficient evaluation plans for XML queries. To estimate selectivity, we need an efficient and flexible structure to store a summary of the Path Expressions that are present in an XML document collection. In this paper we propose a new structure called SF-Treeto address the selectivity estimation problem. SF-Tree provides a flexible way for the users to choose among accuracy, space requirement and selectivity retrieval speed. It makes use of signature files to store the SPEs in a tree form to increase the selectivity retrieval speed and the accuracy of the retrieved selectivity. Our analysis shows that the probability that a selectivity estimation error occurs decreases exponentially with respect to the error size.
Guoren Wang - One of the best experts on this subject based on the ideXlab platform.
-
CAiSE - Query processing and optimization for regular Path Expressions
Notes on Numerical Fluid Mechanics and Multidisciplinary Design, 2003Co-Authors: Guoren Wang, Mengchi LiuAbstract:Regular Path Expression is one of the core components of XML query languages, and several approaches to evaluating regular Path Expressions have been proposed. In this paper, a new Path Expression evaluation approach, extent join, is proposed to compute both parent-children ('/') and ancestor-descendent ('//') connectors between Path steps. Furthermore, two Path Expression optimization rules, Pathshortening and Path-complementing, are proposed. The former reduces the number of joins by shortening the Path while the latter optimizes the execution of a Path by using an equivalent complementary Path Expression to compute the original Path. Experimental results show that the algorithms proposed in this paper are much more efficient than conventional ones.
-
A New Path Expression Computing Approach for XML Data
Efficiency and Effectiveness of XML Tools and Techniques and Data Integration over the Web, 2003Co-Authors: Guoren Wang, Bing SunAbstract:Most query languages in XML database systems use Regular Path Expressions (RPE) to query or extract data from databases and some query processing and optimization techniques have been proposed for RPEs. Conceptually XML documents are collections of Path instances. Each Path instance should conform to an XML element tag sequence, called Path schema. A RPE query can be written as an automaton that can represent a language, while Path schemas can be seen as sentences. In this paper, a novel RPE computing approach, automaton match (AM), is proposed. AM queries the RPEs by matching the automatons with Path schemas. The experimental results show AM is quite efficient for computing RPE queries.
-
comparison of parallel algorithms for Path Expression query in object database systems
Database Systems for Advanced Applications, 2001Co-Authors: Guoren Wang, K Kaneko, Akitake MakinouchiAbstract:Proposes a new parallel algorithm for computing Path Expressions, named the "parallel cascade semi-join" (PCSJ) algorithm. Moreover, a new scheduling strategy called the "right-deep zigzag tree" is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in a distributed and parallel NOW (network of workstations) environment. The results show that the PCSJ algorithm outperforms two other parallel algorithms [the parallel forward pointer chasing (PFPC) algorithm and the index-splitting parallel algorithm (IndexSplit)] when computing Path Expressions with restrictive predicates, and that the right-deep zigzag tree scheduling strategy has a better performance than the right-deep tree scheduling strategy.
-
DASFAA - Comparison of parallel algorithms for Path Expression query in object database systems
Proceedings Seventh International Conference on Database Systems for Advanced Applications DASFAA 2001 DASFAA-01, 2001Co-Authors: Guoren Wang, K Kaneko, Akitake MakinouchiAbstract:Proposes a new parallel algorithm for computing Path Expressions, named the "parallel cascade semi-join" (PCSJ) algorithm. Moreover, a new scheduling strategy called the "right-deep zigzag tree" is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in a distributed and parallel NOW (network of workstations) environment. The results show that the PCSJ algorithm outperforms two other parallel algorithms [the parallel forward pointer chasing (PFPC) algorithm and the index-splitting parallel algorithm (IndexSplit)] when computing Path Expressions with restrictive predicates, and that the right-deep zigzag tree scheduling strategy has a better performance than the right-deep tree scheduling strategy.
-
Analysis and evaluation of resources utility strategies for parallel Path Expression algorithms on DSVM
Proceedings Fourth International Conference Exhibition on High Performance Computing in the Asia-Pacific Region, 2000Co-Authors: Qiang Fang, Guoren WangAbstract:DSVM is a valuable technique developed in shared-nothing parallel architecture. Some research is given to the parallel algorithms on DSVM in the object database, but the essential topic is how to make full use of all kinds of resources to avoid the bottlenecks of CPUs, disks, memory and networks. In order to study this issue deeply, the paper takes parallel algorithms for Path Expressions as examples and analyzes how to use resources reasonably based on DSVM in NOW environments.
Aoying Zhou - One of the best experts on this subject based on the ideXlab platform.
-
index selection for efficient xml Path Expression processing
International Conference on Conceptual Modeling, 2003Co-Authors: Zhimao Guo, Shuigeng Zhou, Aoying ZhouAbstract:One approach to building an efficient XML query processor is to use RDBMSs to store and query XML documents. XML queries contain a number of features that are either hard to translate into SQLs or for which the resulting SQL is complex and inefficient. Among them, Path Expressions pose a new challenge for efficient XML query processing in RDBMSs. Building index structures for Path Expressions is necessary. Meanwhile, indexes occupy much disk space. There is a tradeoff between the consumption of disk space and the efficiency of query evaluation. In this paper, we present a cost model for the space consumption of indexes and their benefit to XML queries. Making use of the statistics of XML data and the characteristics of the target application, we adopt greedy algorithm to select some map indexes to be built. Our experimental study demonstrates that query performance get comparatively significant improvement over the case without indexes while only consuming disk space of modest size.
-
ER (Workshops) - Index Selection for Efficient XML Path Expression Processing
Conceptual Modeling for Novel Application Domains, 2003Co-Authors: Zhimao Guo, Shuigeng Zhou, Aoying ZhouAbstract:One approach to building an efficient XML query processor is to use RDBMSs to store and query XML documents. XML queries contain a number of features that are either hard to translate into SQLs or for which the resulting SQL is complex and inefficient. Among them, Path Expressions pose a new challenge for efficient XML query processing in RDBMSs. Building index structures for Path Expressions is necessary. Meanwhile, indexes occupy much disk space. There is a tradeoff between the consumption of disk space and the efficiency of query evaluation. In this paper, we present a cost model for the space consumption of indexes and their benefit to XML queries. Making use of the statistics of XML data and the characteristics of the target application, we adopt greedy algorithm to select some map indexes to be built. Our experimental study demonstrates that query performance get comparatively significant improvement over the case without indexes while only consuming disk space of modest size.
-
WAIM - Structural Map: A New Index for Efficient XML Path Expression Processing
Advances in Web-Age Information Management, 2002Co-Authors: Shihui Zheng, Aoying Zhou, Long Zhang, Han TaoAbstract:XML is merging as the main standard of presentation and exchange on the Internet. Various XML query languages are proposed. As a ubiquitous part of those XML query languages, Path Expression poses a new challenge for efficient XML query processing in database systems. In this paper, we present a new index structure, Structural Map, for efficient evaluation of Path Expression queries. Structural Map can be used to support Path-indices as well as valueindices in an integrated manner. It is powerful to handle not only simple Path Expressions but also the branching Path Expressions and Path Expressions with predicates efficiently. Performance study shows the Structural Map can improve the performance of XML Path Expression processing significantly.
-
structural map a new index for efficient xml Path Expression processing
Web-Age Information Management, 2002Co-Authors: Shihui Zheng, Aoying Zhou, Long Zhang, Han TaoAbstract:XML is merging as the main standard of presentation and exchange on the Internet. Various XML query languages are proposed. As a ubiquitous part of those XML query languages, Path Expression poses a new challenge for efficient XML query processing in database systems. In this paper, we present a new index structure, Structural Map, for efficient evaluation of Path Expression queries. Structural Map can be used to support Path-indices as well as valueindices in an integrated manner. It is powerful to handle not only simple Path Expressions but also the branching Path Expressions and Path Expressions with predicates efficiently. Performance study shows the Structural Map can improve the performance of XML Path Expression processing significantly.
Chunxia Tang - One of the best experts on this subject based on the ideXlab platform.
-
indexing xml data for Path Expression queries
Lecture Notes in Computer Science, 2004Co-Authors: Chunxia TangAbstract:Many XML query languages use regular Path Expressions to query XML data. Retrieval of XML data is like retrieval of relational databases, but the difference is that relational data are stored in 2-D flat tables whereas XML data are organized in a tree-like structure. Hence, fist tree traversal is a key to XML query processing. This is commonly accomplished using indexing. In this paper, we present a design and implementation of an efficient and quick solution to indexing XML data. Our approach is based on a numbering scheme that encodes the XML elements for not only indexing to the elements but also for quick determination of the ancestor-descendant relationship between elements in the tree hierarchy. This approach also allows efficiently inserting and updating the index system, which is an improvement over several existing XML tree node numbering methods.
-
SERA - Indexing XML Data for Path Expression Queries
Software Engineering Research and Applications, 2004Co-Authors: Chunxia TangAbstract:Many XML query languages use regular Path Expressions to query XML data. Retrieval of XML data is like retrieval of relational databases, but the difference is that relational data are stored in 2-D flat tables whereas XML data are organized in a tree-like structure. Hence, fast tree traversal is a key to XML query processing. This is commonly accomplished using indexing. In this paper, we present a design and implementation of an efficient and quick solution to indexing XML data. Our approach is based on a numbering scheme that encodes the XML elements for not only indexing to the elements but also for quick determination of the ancestor-descendant relationship between elements in the tree hierarchy. This approach also allows efficiently inserting and updating the index system, which is an improvement over several existing XML tree node numbering methods.
J.f. Naughton - One of the best experts on this subject based on the ideXlab platform.
-
ICDE - Recursive XML schemas, recursive XML queries, and relational storage: XML-to-SQL query translation
Proceedings. 20th International Conference on Data Engineering, 2004Co-Authors: Rajasekar Krishnamurthy, Venkatesan T. Chakaravarthy, Raghav Kaushik, J.f. NaughtonAbstract:We consider the problem of translating XML queries into SQL when XML documents have been stored in an RDBMS using a schema-based relational decomposition. Surprisingly, there is no published XML-to-SQL query translation algorithm for this scenario that handles recursive XML schemas. We present a generic algorithm to translate Path Expression queries into SQL in the presence of recursion in the schema and queries. This algorithm handles a general class of XML-to-relational mappings, which includes all techniques proposed in literature. Some of the salient features of this algorithm are: (i) It translates a Path Expression query into a single SQL query, irrespective of how complex the XML schema is, (ii) It uses the "with" clause in SQL99 to handle recursive queries even over nonrecursive schemas, (iii) It reconstructs recursive XML subtrees with a single SQL query and (iv) It shows that the support for linear recursion in SQL99 is sufficient for handling Path Expression queries over arbitrarily complex recursive XML schema.
