Search

Graph databases have received much attention as of late due to numerous applications in which data is naturally viewed as a graph; these include social networks, RDF and the Semantic Web, biological databases, and many others. There are many proposals for query languages for graph databases that mainly fall into two categories. One views graphs as a particular kind of relational data and uses traditional relational mechanisms for querying. The other concentrates on querying the topology of the graph. These approaches, however, lack the ability to combine data and topology, which would allow queries asking how data changes along paths and patterns enveloping it. In this article, we present a comprehensive study of languages that enable such combination of data and topology querying. These languages come in two flavors. The first follows the standard approach of path queries, which specify how labels of edges change along a path, but now we extend them with ways of specifying how both labels and data change. From the complexity point of view, the right type of formalisms are subclasses of register automata. These, however, are not well suited for querying. To overcome this, we develop several types of extended regular expressions to specify paths with data and study their querying power and complexity. The second approach adopts the popular XML language XPath and extends it from XML documents to graphs. Depending on the exact set of allowed features, we have a family of languages, and our study shows that it includes efficient and highly expressive formalisms for querying both the structure of the data and the data itself. [ABSTRACT FROM AUTHOR]

We consider a fragment of XPath 1.0, where attribute and text values may be compared. We show that for any unary query ϕ in this fragment, the set of nodes that satisfy the query in a document t can be calculated in time O(|ϕ|3|t|). We show that for a query in a bigger fragment with Kleene star allowed, the same can be done in time O(2O(|ϕ|)|t|) or in time O(|ϕ|3|t| log |t|). Finally, we present algorithms for binary queries of XPath, which do a precomputation on the document and then output the selected pairs with constant delay. [ABSTRACT FROM AUTHOR]

We study FO(MTC), first-order logic with monadic transitive closure, a logical formalism in between FO and MSO on trees. We characterize the expressive power of FO(MTC) in terms of nested tree-walking automata. Using the latter, we show that FO(MTC) is strictly less expressive than MSO, solving an open problem. We also present a temporal logic on trees that is expressively complete for FO(MTC), in the form of an extension of the XML document navigation language XPath with two operators: the Kleene star for taking the transitive closure of path expressions, and a subtree relativisation operator, allowing one to restrict attention to a specific subtree while evaluating a subexpression. We show that the expressive power of this XPath dialect equals that of FO(MTC) for Boolean, unary and binary queries. We also investigate the complexity of the automata model as well as the XPath dialect. We show that query evaluation be done in polynomial time (combined complexity), but that emptiness (or, satisfiability) is 2ExpTime-complete. [ABSTRACT FROM AUTHOR]

XPath is a prominent W3C standard for navigating XML documents that has stimulated a lot of research into query answering and static analysis. In particular, query containment has been studied extensively for fragments of the 1.0 version of this standard, whereas little is known about query containment in (fragments of) the richer language XPath 2.0. In this article, we consider extensions of Core XPath, the navigational core of XPath 1.0, with operators that are part of or inspired by XPath 2.0: path intersection, path equality, path complementation, for-loops, and transitive closure. For each combination of these operators, we determine the complexity of query containment, both with and without DTDs. It turns out to range from EXPTIME (for extensions with path equality) and 2-EXPTIME (for extensions with path intersection) to non-elementary (for extensions with path complementation or for-loops). In almost all cases, adding transitive closure on top has no further impact on the complexity. We also investigate the effect of dropping the upward and/or sibling axes, and show that this sometimes leads to a reduction in complexity. Since the languages we study include negation and conjunction in filters, our complexity results can equivalently be stated in terms of satisfiability. We also analyze the above languages in terms of succinctness. [ABSTRACT FROM AUTHOR]

We study the satisfiability problem associated with XPath in the presence of DTDs. This is the problem of determining, given a query p in an XPath fragment and a DTD D, whether or not there exists an XML document T such that T conforms to D and the answer of p on T is nonempty. We consider a variety of XPath fragments widely used in practice, and investigate the impact of different XPath operators on the satisfiability analysis. We first study the problem for negationfree XPath fragments with and without upward axes, recursion and data-value joins, identifying which factors lead to tractability and which to NP-completeness. We then turn to fragments with negation but without data values, establishing lower and upper bounds in the absence and in the presence of upward modalities and recursion. We show that with negation the complexity ranges from PSPACE to EXPTIME. Moreover, when both data values and negation are in place, we find that the complexity ranges from NEXPTIME to undecidable. Furthermore, we give a finer analysis of the problem for particular classes of DTDs, exploring the impact of various DTD constructs, identifying tractable cases, as well as providing the complexity in the query size alone. Finally, we investigate the problem for XPath fragments with sibling axes, exploring the impact of horizontal modalities on the satisfiability analysis. [ABSTRACT FROM AUTHOR]

XPath expressions define navigational queries on XML data and are issued on XML documents to select sets of element nodes. Due to the wide use of XPath, which is embedded into several languages for querying and manipulating XML data, the problem of efficiently answering XPath queries has received increasing attention from the research community. As the efficiency of computing the answer of an XPath query depends on its size, replacing XPath expressions with equivalent ones having the smallest size is a crucial issue in this direction. This article investigates the minimization problem for a wide fragment of XPath (namely XP[...]), where the use of the most common operators (child, descendant, wildcard and branching) is allowed with some syntactic restrictions. The examined fragment consists of expressions which have not been specifically studied in the relational setting before: neither are they mere conjunctive queries (as the combination of "//" and "*" enables an implicit form of disjunction to be expressed) nor do they coincide with disjunctive ones (as the latter are more expressive). Three main contributions are provided. The "global minimality" property is shown to hold: the minimization of a given XPath expression can be accomplished by removing pieces of the expression, without having to re-formulate it (as for "general" disjunctive queries). Then, the complexity of the minimization problem is characterized, showing that it is the same as the containment problem. Finally, specific forms of XPath expressions are identified, which can be minimized in polynomial time. [ABSTRACT FROM AUTHOR]

We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTIME in previous work. We prove that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, while the combined complexity is PTIME-hard. Subsequently, we study the sources of this hardness and identify a large and practically important fragment of XPath 1.0 for which the combined complexity is LOGCFL-complete and, therefore, in the highly parallelizable complexity class NC². The second problem is the complexity of validating XML documents against various typing schemes like Document Type Definitions (DTDs), XML Schema Definitions (XSDs), and tree automata, both with respect to data and to combined complexity. For data complexity, we prove that validation is in LOGSPACE and depends crucially on how XML data is represented. For the combined complexity, we show that the complexity ranges from LOGSPACE to LOGCFL, depending on the typing scheme. [ABSTRACT FROM AUTHOR]

XPath is a language for navigating an XML document and selecting a set of element nodes. XPath expressions are used to query XML data, describe key constraints, express transformations, and reference elements in remote documents. This article studies the containment and equivalence problems for a fragment of the XPath query language, with applications in all these contexts. In particular, we study, a class of XPath queries that contain branching, label wildcards and can express descendant relationships between nodes. Prior work has shown that languages that combine any two of these tree features have efficient containment algorithms. However, we show that for the combination of features, containment is coNP-complete. We provide a sound and complete algorithm for containment that runs in exponential time, and study parameterized PTIME special cases. While we identify one parameterized class of queries for which containment can be decided efficiently, we also show that even with some bounded parameters, containment remains coNP-complete. In response to these negative results, we describe a sound algorithm that is efficient for all queries, but may return false negatives in some cases. [ABSTRACT FROM AUTHOR]

Web Scraping may consider as data theft action, several researchers have introduced some approaches for addressing this issue. These solutions could solve the problem in partial ways and sometimes, solution cannot be applicable with modern web techniques. Consequently, in our work we have introduced a new approach for stopping web scraping in an efficient way and applicable with modern web techniques called Markup Randomizer, which changes the HTML and CSS in proper way randomly in timely manner. The best feature of our model is that each web page can use it without paying any efforts or restrictions in web site markup. Experiments done over collected dataset which consist of 30 websites divided into three categories: News, Currency Rates and Weather. The proposed model based on Markup Randomizer applied over this dataset. The aim of the experimental is to measure the Similarity, File Size and the time. During testing the proposed model, we get that a change on the markup done up to 50%, file size is changed and optimized after during the process. The required time to applying the model and generating the new markup is good and up to 2 minutes. Finally, we find that our proposed markup randomizer is accepted. [ABSTRACT FROM AUTHOR]

We give sound and complete axiomatizations for XPath with data tests by ‘equality’ or ‘inequality’, and containing the single ‘child’ axis. This data-aware logic predicts over data trees, which are tree-like structures whose every node contains a label from a finite alphabet and a data value from an infinite domain. The language allows us to compare data values of two nodes but cannot access the data values themselves (i.e. there is no comparison by constants). Our axioms are in the style of equational logic, extending the axiomatization of data-oblivious XPath, by B. ten Cate, T. Litak and M. Marx. We axiomatize the full logic with tests by ‘equality’ and ‘inequality’, and also a simpler fragment with ‘equality’ tests only. Our axiomatizations apply both to node expressions and path expressions. The proof of completeness relies on a novel normal form theorem for XPath with data tests. [ABSTRACT FROM AUTHOR]

We study the expressive power of the downward and vertical fragments of XPath equipped with (in)equality tests over possibly infinite data trees. We introduce a suitable notion of saturation with respect to node expressions, and show that over saturated data trees, the already studied notion of (unary) bisimulation coincides with the idea of ‘indistinguishability by means of node expressions’. We also prove definability and separation theorems for classes of pointed data trees. We introduce new notions of binary bisimulations, which relate two pairs of nodes of data trees. We show that over finitely branching data trees, these notions correspond to the idea of ‘indistinguishability by means of path expressions’. We prove a characterization theorem, which describes when a first-order formula with two free variables is expressible in the downward fragment. We show definability and separation theorems, for classes of two-pointed data trees and in the context of path expressions. [ABSTRACT FROM AUTHOR]

In this paper, we show the process inspired by model checking which integrate temporal logic to the application of semi-structured data query. We investigate the potential of a technique based on CTL (Computation Tree Logic) model checking for evaluating queries expressed in (a subset of) XPath. Our research consists of query algebra, constraint understanding and expression mapping. The core of research is mapping the XML query algebra to an expression collection of temporal logic. We try a new kind of query execution strategy to enhance the accuracy of semantic description of the XML query. For the purpose of supporting the generation of the formal specifications and reducing the mapping processing, the XML query constraint can be converted to a specification of SPS (Specification Pattern System) through which we get the formula set to evaluate path queries directly on CTL formula. [ABSTRACT FROM AUTHOR]

Web Services allow applications to communicate with each other independent of platform and/or language. They are prone to attacks in the form of Denial-Of-Service, XML, XPath, SQL injection and spoofing, making implementation of web service security vital. Though many solutions are proposed for minimizing attacks, there is no single solution for mitigating all the attacks on web services. The objective of this paper is to present a systematic review on the studies of web service security. It is identified that there is lot of research going on in web services, dealing mostly with attack detection as well as identification of vulnerabilities in the services. Denial-of-service attack is found to be the most addressed of all attacks. Solutions were mainly proposed using dynamic analysis, closely followed by static analysis. [ABSTRACT FROM AUTHOR]

Extracting data from various semi-structured sources is a topic that has received a lot of attention. Wrapper induction specifically has been studied extensively, where users annotate a couple of data sources with examples of the data they want, after which a procedure (wrapper) is constructed that can optimally extract similar data as well. In this paper a novel wrapper induction approach is proposed, exploiting the premise of the general applicability of the XPath query language, studied specifically within the context of web pages. After a user annotates a limited set of web pages with the required data, a generalised XPath is constructed that is capable of extracting the examples and, optimally, similar data as well. This generalised baseline XPath is then enriched with predicates, based on context and structure of the data sources, to optimise the precision/recall balance of the data extraction capability of the wrapper. Six variations of such limiting predicates are introduced and investigated. In this paper, it is shown that the baseline approach often generalises the samples too much, leading to a decreased precision. Enriching the baseline wrapper by the addition of predicates limits the generalisation power of the queries in an intelligent manner. Experimental results show that there is a significant improvement in the overall precision of the generalised query, without an excessive loss in recall. Documented tests and real world experience with a large amount of data show that the technique is flexible, easily understood and applicable in a broad range of applications. It is not only of interest in the fields of web information retrieval, but can also be used in the contexts of, e.g., reverse engineering of databases, ontology expansion and deep web data mining, as both simple lists of data and complex structures can be extracted. [ABSTRACT FROM AUTHOR]

Björklund et al. [6] showed that containment for conjunctive queries (CQ) over trees and positive XPath is respectively Π 2 P and coNP-complete. In this article we show that the same problem has the same complexity when we expand these languages with XPath׳s attribute value comparisons. We show that different restrictions on the domain of attribute values (finite, infinite, dense, discrete) have no impact on the complexity. Making attributes required does have an impact: the problem becomes harder. We also show that containment of tree patterns without the wildcard ⁎ , which is in PTIME, becomes coNP-hard when adding equality and inequality comparisons. [ABSTRACT FROM AUTHOR]

We study the expressiveness on a given document of various fragments of XPath, the core navigational language on XML documents. Viewing these languages as fragments of Tarski's relation algebra, we give characterizations for when a binary relation on the document's nodes (i.e., a set of paths) is definable by an expression in these algebras. In contrast with this “global view” on language semantics, there is also a “local view” where one is interested in the nodes to which one can navigate starting from a particular node. In this view, we characterize when a set of nodes can be defined as the result of applying an expression to a given node. All of these global and local definability results are obtained using a two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the language, and then bootstrapping these characterizations to the desired results. [ABSTRACT FROM AUTHOR]

Automated test scripts are used with success in many web development projects, so as to automatically verify key functionalities of the web application under test, reveal possible regressions and run a large number of tests in short time. However, the adoption of automated web testing brings advantages but also novel problems, among which the test code fragility problem. During the evolution of the web application, existing test code may easily break and testers have to correct it. In the context of automated DOM-based web testing, one of the major costs for evolving the test code is the manual effort necessary to repair broken web page element locators-lines of source code identifying the web elements (e.g. form fields and buttons) to interact with. In this work, we present ROBULA+, a novel algorithm able to generate robust XPath-based locators-locators that are likely to work correctly on new releases of the web application. We compared ROBULA+ with several state of the practice/art XPath locator generator tools/algorithms. Results show that XPath locators produced by ROBULA+ are by far the most robust. Indeed, ROBULA+ reduces the locators' fragility on average by 90% w.r.t. absolute locators and by 63% w.r.t. Selenium IDE locators. [ABSTRACT FROM AUTHOR]

An energy efficient way of disseminating XML data to several mobile clients is broadcast. Information such as alert on emergencies, election results and sporting event results can be of interest to large number of mobile clients. Since extensible Markup Language (XML) is widely used for information exchange, wireless information services require an energy efficient XML data dissemination. XML Path (XPath) represents selective data required by mobile clients. XPath query processing involves two performance metrics, namely tune-in time and access time. In this paper, we propose a novel structure for streaming XML data called Path Stream Group Level (PSGL) node by exploiting the tree structure of XML document. It possesses various small indices such as level, child, sibling, attribute, text for selective download of XML data by mobile clients. It organizes data based on the level of XML document tree and groups XML elements with same XML path prefix to conserve battery power at mobile clients. Experimental results show that proposed method has reduced tune-in time when compared with existing approaches. Hence PSGL approach enhances performance with energy conservation for processing various types of XPath queries. [ABSTRACT FROM AUTHOR]

The World Wide Web is the biggest source of data that the general public has access to Students and researchers working on data-related problems need a well-maintained source to get their data from. Most online services provide APIs to use their service. However, this may not provide all the data that they actually need even though it exists on the website. In this paper, "Scrapple" - a framework for creating semi-automatic web scrapers, which extract required data from the Web, is introduced. Users do not need to write the entire scraping programs - they only need to define a configuration file which is used to build the required scraper. The configuration provides support for CSS selectors and XPath expressions. [ABSTRACT FROM AUTHOR]

In this paper we present a fuzzy variant of the XPath query language for the flexible information retrieval on XML documents. Our main purpose is to provide a repertoire of operators that offer the possibility of managing satisfaction degrees by adding structural constraints and fuzzy operators inside conditions, in order to produce a ranked sorted list of answers according to user's preferences when composing queries. By using the FLOPER system designed in our research group, our proposal has been implemented with a fuzzy logic language to take profit of the clear synergies between both target and source fuzzy languages. [ABSTRACT FROM AUTHOR]

A great deal of research into the learning of schemas from XML data has been conducted in recent years to enable the automatic discovery of XML schemas from XML documents when no schema or only a low-quality one is available. Unfortunately, and in strong contrast to, for instance, the relational model, the automatic discovery of even the simplest of XML constraints, namely XML keys, has been left largely unexplored in this context. A major obstacle here is the unavailability of a theory on reasoning about XML keys in the presence of XML schemas, which is needed to validate the quality of candidate keys. The present article embarks on a fundamental study of such a theory and classifies the complexity of several crucial properties concerning XML keys in the presence of an XSD, like, for instance, testing for consistency, boundedness, satisfiability, universality, and equivalence. Of independent interest, novel results are obtained related to cardinality estimation of XPath result sets. A mining algorithm is then developed within the framework of levelwise search. The algorithm leverages known discovery algorithms for functional dependencies in the relational model, but incorporates the properties mentioned before to assess and refine the quality of derived keys. An experimental study on an extensive body of real-world XML data evaluating the effectiveness of the proposed algorithm is provided. [ABSTRACT FROM AUTHOR]

We review the problem of finding contained rewritings (CRs) for XPath queries using XPath views. CR is proposed to cater for data integration scenarios, where views are unlikely to be complete due to the limited coverage of data sources, and hence equivalent rewritings are impossible to be found. As a result, we are usually required to find a maximal contained rewriting (MCR) for a query to provide the best possible answers. An MCR is a set of CRs, and may contain redundant CRs. Obviously, evaluating redundant CRs on materialized views is unnecessary. In this paper, we first address how to find the irredundant maximal contained rewriting (IMCR), i.e. all the irredundant CRs. We show that the existing approach ignores a type of situation, and turns out to be not sufficient. As a result, the only safe solution is a brute-force pairwise containment check for all the CRs. We then propose some heuristics to speed up the brute-force comparisons. When a materialized view is given, we propose how to evaluate the IMCR on the materialized view, which, to our knowledge, is the first work on optimizing the evaluation of a set of produced CRs on the materialized view by considering the inherent structural characteristics of the CRs. Our experiments show the effectiveness and efficiency of our algorithms. [ABSTRACT FROM AUTHOR]

Data heterogeneity in XML retrieval activities can be tackled by giving users the possibility to obtain approximate answers to their queries. XPath query relaxation has been proposed as a mechanism to provide approximate answers in the case of positive XPath queries. Under this mechanism, the “satisfaction score” of an answer is defined by looking at how the query must be relaxed to produce that answer, and the user is provided with the best \(k\) answers according to their satisfaction score (top- \(k\) query answering). In this paper we investigate the problem of top- \(k\) query answering for XPath queries with negation. We tackle the challenging issues that need to be carefully considered when dealing with the approximation of negated conditions and propose an incremental top- \(k\) query answering technique based on query relaxation. Specifically, after defining a weighted query language and its semantics, we develop a general incremental query evaluation framework, which is flexible enough to support different evaluation strategies. The experimental assessment confirms the effectiveness of the whole framework. [ABSTRACT FROM AUTHOR]

Healthcare information and its secure management has become an active research topic along with an increase in the usage of XML documents and the importance of access control in maintaining patient records. In this paper, we present a methodology to describe a formal specification for an authorized view of an XMLbased healthcare system having a schema-level access control by assigning well-established concurrency semantics to the system. To achieve this goal, we translate the semantics of the schema, query, access control for XML-based health records, and XPath expressions, into a CSP-like process algebra language through an illustrative example. Finally, our experimental results show the possibility to reason about security properties of an XML-based access control model with the support of automated model checking tools, because it provides the formal semantics for access control policies and XML documents with the tree structure. [ABSTRACT FROM AUTHOR]

Data-driven Web services build on service-oriented technologies to provide an interoperable method of interacting with data sources on top of the Web. Data Web services composition has emerged as a flexible solution to answer users' complex queries on the fly. However, as the number of Web services on the Web grows quickly, a large number of candidate compositions that would use different (most likely competing) services may be used to answer the same query. User preferences are a key factor that can be used to rank candidate services/compositions and retain only the best ones. In this article, we present a novel approach for computing the top-ß data service compositions based on user preferences. In our approach, we model user preferences using fuzzy sets and incorporate them into the composition query. We use an efficient RDF query rewriting algorithm to determine the relevant services that may be used to answer the composition query. We match the (fuzzy) constraints of the relevant services to those of the query and determine their matching degrees using a set of matching methods. We then rank-order the candidate services based on a fuzzification of Pareto dominance and compute the top-ß data service compositions. In addition, we introduce a new method for increasing the diversity of returned top-ß compositions while maintaining as much as possible the compositions with the highest scores. Finally, we describe the architecture of our system and present a thorough experimental study of our proposed techniques and algorithms. The experimental study demonstrates the efficiency and the effectiveness of our techniques in different settings. [ABSTRACT FROM AUTHOR]

Schemas are often used to constrain the content and structure of XML documents. They can be quite big and complex and, thus, difficult to be accessed manually. The ability to query a single schema, a collection of schemas or to retrieve schema components that meet certain structural constraints significantly eases schema management and is, thus, useful in many contexts. In this paper, we propose a query language, named XSPath, specifically tailored for XML schema that works on logical graph-based representations of schemas, on which it enables the navigation, and allows the selection of nodes. We also propose XPath/XQuery-based translations that can be exploited for the evaluation of XSPath queries. An extensive evaluation of the usability and efficiency of the proposed approach is finally presented within the (E\cal X up) system . [ABSTRACT FROM AUTHOR]

Publish-subscribe systems present the state of the art in information dissemination to multiple users. Such systems have evolved from simple topic-based to the current XML-based systems. XML-based pubsub systems provide users with more flexibility by allowing the formulation of complex queries on the content as well as the structure of the streaming messages. Messages that match a given user query are forwarded to the user. This article examines how to exploit the parallelism found in XPath filtering. Using an incoming XML stream, parsing and matching thousands of user profiles are performed simultaneously by matching engines. We show the benefits and trade-offs of mapping the proposed filtering approach onto FPGAs, processing streams of XML at wire speed, and GPUs, providing the flexibility of software. This is in contrast to conventional approaches bound by the sequential aspect of software computing, associated with a large memory footprint. By converting XPath expressions into custom stacks, our solution is the first to provide support for complex XPath structural constructs, such as parent-child and ancestor descendant relations, whilst allowing wildcarding and recursion. The measured speedups resulting from the GPU and FPGA accelerations versus single-core CPUs are up to 6.6X and 2.5 orders of magnitude, respectively. The FPGA approaches are up to 31X faster than software running on 12 CPU cores. [ABSTRACT FROM AUTHOR]

XML is a markup language that defines a set of rules for encoding semi-structured data in a readable format for both humans and machines, in other words the increase of various XML data as information source has raised a number of issues about how to represent and manage this data. Find out an ontology knowledge to derive semantics of XML document has become a major challenge in semi-structured data management. XPath and XQuery languages are used for selecting nodes and compute values from XML document, tuple the XML tree and address the problem of XML data clustering according to structure with ontology knowledge. Experiment on real XML database gives evidence that our proposed approach is highly effective in tupling and clustering of XML tree. So this paper will propose Sedna, which is a free native XML database that provides flexible XML processing facilities include W3C XQuery implementation. Finally we will discuss the results of No. of replayed nodes and time taken by XPath or XQuery. [ABSTRACT FROM AUTHOR]

We prove the undecidability of Core XPath 1.0 (CXP) [G. Gottlob and C. Koch, in Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS ’02 (Copenhagen, July 2002). IEEE CS Press (2002) 189–202.] extended with an Inflationary Fixed Point (IFP) operator. More specifically, we prove that the satisfiability problem of this language is undecidable. In fact, the fragment of CXP+IFP containing only the self and descendant axes is already undecidable. [ABSTRACT FROM PUBLISHER]

This article proposes algorithms for evaluating XPath queries over an XML tree that is partitioned horizontally and vertically, and is distributed across a number of sites. The key idea is based on partial evaluation: it is to send the whole query to each site that partially evaluates the query, in parallel, and sends the results as compact (Boolean) functions to a coordinator that combines these to obtain the result. This approach possesses the following performance guarantees. First, each site is visited at most twice for data-selecting XPath queries, and only once for Boolean XPath queries. Second, the network traffic is determined by the answer to the query, rather than the size of the tree. Third, the total computation is comparable to that of centralized algorithms on the tree stored in a single site, regardless of how the tree is fragmented and distributed. We also present a MapReduce algorithm for evaluating Boolean XPath queries, based on partial evaluation. In addition, we provide algorithms to evaluate XPath queries on very large XML trees, in a centralized setting. We show both analytically and empirically that our techniques are scalable with large trees and complex XPath queries. These results, we believe, illustrate the usefulness and potential of partial evaluation in distributed systems as well as centralized XML stores for evaluating XPath queries and beyond. [ABSTRACT FROM AUTHOR]

We investigate the satisfiability problem for downward-XPath, the fragment of XPath that includes the child and descendant axes, and tests for (in)equality of attributes' values. We prove that this problem is decidable, EXPTIME-complete. These bounds also hold when path expressions allow closure under the Kleene star operator. To obtain these results, we introduce a Downward Data automata model (DD automata) over trees with data, which has a decidable emptiness problem. Satisfiability of downward-XPath can be reduced to the emptiness problem of DD automata and hence its decidability follows. Although downward-XPath does not include any horizontal axis, DD automata are more expressive and can perform some horizontal tests. Thus, we show that the satisfiability remains in EXPTIME even in the presence of the regular constraints expressible by DD automata. However, the same problem in the presence of any regular constraint is known to have a nonprimitive recursive complexity. Finally, we give the exact complexity of the satisfiability problem for several fragments of downward-XPath. [ABSTRACT FROM AUTHOR]

We revisit the problem of answering tree pattern queries using views.We first show that, for queries and views that do not have nodes labeled with the wildcard *, there is an approach which does not require us to find any rewritings explicitly, yet which produces the same answers as the maximal contained rewriting. Then, using the new approach, we give simple conditions and a corresponding algorithm for identifying redundant view answers, which are view answers that can be ignored when evaluating the maximal contained rewriting.We also consider redundant view answers in the case where there are multiple views, the relationship between redundant views and redundant view answers, and discuss how to combine the removal of redundant view answers and redundant rewritings. We show that the aforesaid results can be extended to a number of other special cases. Finally, for arbitrary queries and views in P{/,//,*,[]}, we provide a method to find the maximal contained rewriting and show how to answer the query using views without explicitly finding the rewritings. [ABSTRACT FROM AUTHOR]

Enterprise systems produce a vast amount of logging data. This critical and valuable information must be processed automatically for timely system analysis and recovery. As a result of industry demands, a standard database containing known issues has been introduced - a symptom database. Each symptom consists of a rule pattern and corresponding solutions. Patterns used for symptom identification are encoded as a XPath expression and matched against a stream of events in a standardised WSGI format common base event. The ability of an efficient matching for symptom patterns has been raised as an important requirement by industries. The authors present a real-time symptom identification in a stream of events. The implementation will allow multiple autonomic computing components such as self-monitoring sensors to effectively match known patterns in large datasets in run time. Unlike current state of the art approaches, the proposed solution allows users to define patterns using all the complex XPath functions in addition to standard numeric and Boolean operators. In particular, it was aimed at efficient simultaneous matching of a large set of XPath-based symptom patterns against a high-volume event stream, which is crucial for symptom identification but was not addressed efficiently by currently available XPath-matching engines. [ABSTRACT FROM AUTHOR]

The ability to compute top-k matches to eXtensible Markup Language (XML) queries is gaining importance owing to the increasing of large XML repositories. Current work on top-k match to XML queries mainly focuses on employing XPath, XQuery or NEXI as the query language, whereas little work has concerned on top-k match to XML keyword search. In this study, the authors propose a novel two-layer-based index construction and associated algorithm for efficiently computing top-k results for XML keyword search. Our core contribution, the two-layer-based inverted Index and associated algorithm for XML keyword search take both score-sorted-sequence and Dewey ID-sorted-sequence into consideration, and thus gain performance benefits during querying process. The authors have conducted expensive experiments and our experimental results show efficiency advantages compared with existing approaches. [ABSTRACT FROM AUTHOR]

Abstract: Let be the fragment of XPath 1.0, consisting of queries that involve only the child and descendant axes, and predicates without disjunction or negation (and no wildcard nodetests); these queries can be represented as tree patterns. We consider the problem of rewriting a query Q using a materialized view V, where . We present more efficient algorithms for the following: (1) Determine if an equivalent rewriting of Q using V exists; find the smallest such rewriting, when it exists. A previously-known algorithm runs in time. For the special case when Q is known to be minimal, we present an algorithm. (2) Determine if a (nonempty) contained rewriting of Q using V exists. We present an algorithm, compared to the previous algorithm. We also present a more efficient algorithm for finding a maximal such rewriting, when it exists. Then we extend this result to a subset of that allows restricted occurrences of wildcard nodetests. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees P and T, finding all occurrences of P in T via such many-to-one matchings that preserve node labels and parent–child relationship. This problem is closely related to the tree pattern matching problem for XPath queries with child axis only. If , we present an efficient algorithm that solves the problem in time using space and preprocessing on a unit-cost arithmetic RAM model with addition, where m is the number of nodes in P, n is the number of nodes in T, h is the height of T, and w is the word length, and we assume that . We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to the tree pattern matching problem for XPath queries with descendant axis only. [Copyright &y& Elsevier]