3074232
From XML to Semantic Web
The present web is existing in the HTML and XML formats for persons to browse. Recently there is a trend towards the semantic web where the information can be can be processed and understood by agents. Most of the present research works focus on the translation from HTML to semantic web, but seldom on XML. In this paper, we design a method to translate XML to semantic web. It is known that ontologies play an important role in the semantic web, therefore firstly, we propose a genetic model to organize ontologies, and based on this model, we use three steps, viz. semantic translation, structural translation and schematic translation, to translate XML to semantic web. The aim of the paper is to facilitate the wide use of semantic web.
516020
Efficient Processing of Ordered XML Twig Pattern
Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. Holistic twig join algorithm has showed its superiority over binary decompose based approach due to efficient reducing intermediate results. The existing holistic join algorithms, however, cannot deal with ordered twig queries. A straightforward approach that first matches the unordered twig queries and then prunes away the undesired answers is obviously not optimal in most cases. In this paper, we study a novel holistic-processing algorithm, called OrderedTJ, for ordered twig queries. We show that OrderedTJ can identify a large query class to guarantee the I/O optimality. Finally, our experiments show the effectiveness, scalability and efficiency of our proposed algorithm.
5215475
QED: a novel quaternary encoding to completely avoid re-labeling in XML updates
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.
16587000
OWL-Based Semantic Conflicts Detection and Resolution for Data Interoperability
Ontology provides sharing knowledge among different data sources which will help to clarify the semantics of information. OWL is being promoted as a standard for web ontology language, thus in the future a considerable number of ontologies will be created based on OWL. Therefore automatically detecting semantic conflicts based on OWL will greatly expedite the step to achieve semantic interoperability, and will greatly reduce the manual work to detect semantic conflicts. In this paper, we summarize seven cases based on OWL in which semantic conflicts are easily to be encountered, and for each case, we give a rule to resolve the conflict. Via a series of examples, we show how this method works. Based on the seven cases, we propose a semantic conflicts detection and resolution algorithm. This aims at providing a semi-automatic method for semantic uniform data interoperability and integration.
29028846
Reuse or Never Reuse the Deleted Labels in XML Query Processing Based on Labeling Schemes
To facilitate the XML query processing, several kinds of labeling schemes have been proposed. Based on the labeling schemes, the ancestor-descendant and parent-child relationships in XML queries can be quickly determined without accessing the original XML file. Recently, more researches are focused on how to update the labels when nodes are inserted into the XML. However how to process the deleted labels are not discussed previously. We think that the deleted labels can be processed in two different directions: (1) reuse all the deleted labels to control the label size increasing speed and improve the query performance; (2) never reuse the deleted labels to query different versions of the XML data based on labeling schemes. In this paper, we firstly introduce our previous work, called QED, which can completely avoid the re-labeling in XML updates. Secondly based on QED we propose a new algorithm, called Reuse, which can reuse all the deleted labels to control the label size increasing speed; meanwhile the Reuse algorithm can completely avoid the re-labeling also. Thirdly to query different versions of the XML data, we propose another new algorithm, called NeverReuse, which is the only approach that never reuses any deleted labels. Extensive experimental results show that the algorithms proposed in this paper can control the label size increasing speed when reusing all the deleted labels, and is the only approach to query different versions of the XML data based on labeling schemes.
139092767
An Improved Prefix Labeling Scheme: A Binary String Approach for Dynamic Ordered XML
A number of labeling schemes have been designed to facilitate the query of XML, based on which the ancestor-descendant relationship between any two nodes can be determined quickly. Another important feature of XML is that the elements in XML are intrinsically ordered. However the label update cost is high based on the present labeling schemes. They have to re-label the existing nodes or re-calculate some values when inserting an order-sensitive element. Thus it is important to design a scheme that supports order-sensitive queries, yet it has low label update cost. In this paper, we design a binary string prefix scheme which supports order-sensitive update without any re-labeling or re-calculation. Theoretical analysis and experimental results also show that this scheme is compact compared to the existing dynamic labeling schemes, and it provides efficient support to both ordered and un-ordered queries.
2062689
Optimizing Large Join Queries in Mediation Systems
In data integration systems, queries posed to a mediator need to be translated into a sequence of queries to the underlying data sources. In a heterogeneous environment, with sources of diverse and limited query capabilities, not all the translations are feasible. In this paper, we study the problem of finding feasible and efficient query plans for mediator systems. We consider conjunctive queries on mediators and model the source capabilities through attribute-binding adornments. We use a simple cost model that focuses on the major costs in mediation systems, those involved with sending queries to sources and getting answers back. Under this metric, we develop two algorithms for source query sequencing - one based on a simple greedy strategy and another based on a partitioning scheme. The first algorithm produces optimal plans in some scenarios, and we show a linear bound on its worst case performance when it misses optimal plans. The second algorithm generates optimal plans in more scenarios, while having no bound on the margin by which it misses the optimal plans. We also report on the results of the experiments that study the performance of the two algorithms.
8850461
Schema-guided wrapper maintenance for web-data extraction
Extracting data from Web pages using wrappers is a fundamental problem arising in a large variety of applications of vast practical interests. There are two main issues relevant to Web-data extraction, namely wrapper generation and wrapper maintenance. In this paper, we propose a novel schema-guided approach to the problem of automatic wrapper maintenance. It is based on the observation that despite various page changes, many important features of the pages are preserved, such as syntactic patterns, annotations, and hyperlinks of the extracted data items. Our approach uses these preserved features to identify the locations of the desired values in the changed pages, and repair wrappers correspondingly by inducing semantic blocks from the HTML tree. Our intensive experiments on real Web sites show that the proposed approach can effectively maintain wrappers to extract desired data with high accuracies.
8267935
Structural Modeling and Analysis of Signaling Pathways Based on Petri Nets
The purpose of this paper is to discuss how to model and analyze signaling pathways by using Petri net. Firstly, we propose a modeling method based on Petri net by paying attention to the molecular interactions and mechanisms. Then, we introduce a new notion "activation transduction component" in order to describe an enzymic activation process of reactions in signaling pathways and shows its correspondence to a so-called elementary T-invariant in the Petri net models. Further, we design an algorithm to effectively find basic enzymic activation processes by obtaining a series of elementary T-invariants in the Petri net models. Finally, we demonstrate how our method is practically used in modeling and analyzing signaling pathway mediated by thrombopoietin as an example.
31791732
Cluster-Based Self-organizing Neuro-fuzzy System with Hybrid Learning Approach for Function Approximation
A novel hybrid cluster-based self-organizing neuro-fuzzy system (HC-SONFS) is proposed for dynamic function approximation and prediction. With the mechanism of self-organization, fuzzy rules are generated in the form of clusters using the proposed self-organization method to achieve compact and sufficient system structure if the current structure of knowledge base is insufficient to satisfy the required performance. A hybrid learning algorithm combining the well-known random optimization (RO) and the least square estimation (LSE) is use for fast learning. An example of chaos time series for system identification and prediction is illustrated. Compared to other approaches, excellent performance of the proposed HC-SONFS is observed.
45651558
The Solution of a Problem of Godsil on Cubic Cayley Graphs
In this short paper, we give a positive answer to a question of C. D. Godsil (1983,Europ. J. Combin.4, 25?32) regarding automorphisms of cubic Cayley graphs of 2-groups: “If Cay(G, S) is a cubic Cayley graph of a 2-groupGandA=AutCay(G, S), doesA1?1 imply Aut(G, S)?1?”