Fast in-memory XPath search using compressed indexes

A large fraction of an XML document typically consists of text data. The XPath query language allows text search via the equal, contains, and starts-with predicates. Such predicates can be efficiently implemented using a compressed self-index of the document's text nodes. Most queries, however, contain some parts querying the text of the document, plus some parts querying the tree structure. It is therefore a challenge to choose an appropriate evaluation order for a given query, which optimally leverages the execution speeds of the text and tree indexes. Here the SXSI system is introduced. It stores the tree structure of an XML document using a bit array of opening and closing brackets plus a sequence of labels, and stores the text nodes of the document using a global compressed self-index. On top of these indexes sits an XPath query engine that is based on tree automata. The engine uses fast counting queries of the text index in order to dynamically determine whether to evaluate top-down or bottom-up with respect to the tree structure. The resulting system has several advantages over existing systems: (1) on pure tree queries (without text search) such as the XPathMark queries, the SXSI system performs on par or better than the fastest known systems MonetDB and Qizx, (2) on queries that use text search, SXSI outperforms the existing systems by 1-3 orders of magnitude (depending on the size of the result set), and (3) with respect to memory consumption, SXSI outperforms all other systems for counting-only queries.

Suporte a argumentos de consulta vagos através da linguagem XPath

Abordagens clássicas de linguagens de consultas para bancos de dados possuem certas restrições ao serem usadas, diretamente, por aplicações que acessam dados cujo conteúdo não é completamente conhecido pelo usuário. Essas restrições geram um cenário onde argumentos de consultas, especificados com operadores boleanos, podem retornar resultados vazios. Desse modo, o usuário é forçado a refazer suas consultas até que os argumentos usados estejam idênticos aos dados armazenados no banco de dados. Em bases XML, este problema é reforçado pela heterogeneidade das formas em que a informação encontra-se armazenada em diferentes lugares. Como solução, uma alternativa seria o uso de funções de similaridade na substituição de operadores boleanos, a fim de que o usuário obtenha resultados aproximados para a consulta especificada. Neste trabalho é apresentada uma proposta para suporte a argumentos de consulta vagos através da extensão da linguagem XPath. Para isso, são utilizadas expressões XPath que utilizam novas funções, as quais são, diretamente, adicionadas ao processador da linguagem de consulta. Além disso, é apresentada uma breve descrição das métricas de similaridade utilizadas para a criação das funções. As funções que foram adicionadas a um processador XPath possuem uma ligação muito estreita com as métricas utilizadas. Como as métricas, as funções trabalham com valores simples (elementos atômicos) e compostos (elementos complexos). As funções que trabalham com elementos atômicos podem ser classificadas tanto pelo tipo de dado que será analisado, como pelo tipo de análise que será feita. As funções para elementos complexos comparam conjuntos de elementos atômicos de acordo com a forma do agrupamento (conjunto, lista ou tupla).

The NLP task at INEX 2004

The INEX workshop is concerned with evaluating the effectiveness of XML retrieval systems. In 2004 a natural language query task was added to the INEX Ad hoc track. Standard INEX Ad hoc topic titles are specified in NEXI -- a simplified and restricted subset of XPath, with a similar feel, and yet with a distinct IR flavour and interpretation. The syntax of NEXI is rigid and it imposes some limitations on the kind of information need that it can faithfully capture. At INEX 2004 the NLP question to be answered was simple -- is it practical to use a natural language query that is the equivalent of the formal NEXI title? The results of this experiment are reported and some information on the future direction of the NLP task is presented.

Robust Web content extraction

We present an empirical evaluation and comparison of two content extraction methods in HTML: absolute XPath expressions and relative XPath expressions. We argue that the relative XPath expressions, although not widely used, should be used in preference to absolute XPath expressions in extracting content from human-created Web documents. Evaluation of robustness covers four thousand queries executed on several hundred webpages. We show that in referencing parts of real world dynamic HTML documents, relative XPath expressions are on average significantly more robust than absolute XPath ones.

Balidazio-eskemetan oinarritutako interfaze-sorkuntza dinamikoa

Gradu-amaierako proiektu hau anotazio linguistiko konplexuen testuinguruan kokatzen da. Proiektuaren helburuak hiru zatitan bereizi dira. Lehena, Armiarma web-aplikazioa eta LibiXaML liburutegia egokitzea bilaketa konplexuagoak onartu ahal izateko; horretarako Relax NG eskemen erabilpena errazten duen JavaScript liburutegia garatu da. Ondoren, LibiXaML liburutegiak bilaketarako erabiltzen dituen XPath-en sorkuntza automatizatzea, Relax NG eskematik abiatuz. Eta amaitzeko, analisi-sorkuntzako prototipoa hobetzea, hasieran sortutako liburutegia berrerabiliz eta Relax NG eskemak erabiliz.

Procedimiento de refutación para un conjunto de restricciones sobre documentos XML

We present a prototype that implements a set of logical rules to prove the satis ability for a class of speci cations on XML documents. Speci cations are given by means of constraints built on Boolean XPath patterns. The main goal of this tool is to test if a given speci cation is satis able or not, showing the history of the execution. It can also be used to test if a given document is a model of a given speci cation and, as a subproduct, it allows to look for all the relations (monomorphisms) between two patterns or the result of doing some operations by combining patterns in di erent ways. The results of these operations are visually shown and therefore the tool makes these operations more understandable. The implementation of the algorithm has been written in Prolog but the prototype has a Java interface for an easy and friendly use.

移动环境下的服务描述和服务匹配研究

服务发现与资源定位是移动环境下进行信息共享、处理的前提,服务描述和服务匹配策略是其中的关键问题,服务的多样性、异构性以及移动环境的动态性使得这些问题更加复杂。该文提出一种支持服务多样性和异构性的服务描述模型,针对此模型设计并实现了高效的存储结构和包括精确匹配、部分匹配的服务匹配策略,实验结果表明该策略的服务匹配性能优于基于XML的XPath方式。

普适环境下服务发现的语义支持机制

随着计算能力和通信能力的增强，计算设备所占用的体积也越来越小，各种新形态的传感器、移动设备及无线网络设备日趋普及。这极大地促进了以无线、移动和嵌入式设备为基础的普适计算模式的形成和发展。普适环境下的服务发现机制可使得用户能够使用各种移动设备无缝的、随时随地的共享和访问各种服务信息。 普适环境中的网络异构性和动态性，以及服务的多样性和异构性，均对服务发现提出了新的挑战。目前学术界和工业界在服务发现方面进行了不少的探索和研究，当前的一些服务发现协议或系统比如SLP、UPnP、INS等，一般基于语法的方法描述服务，主要关注服务的功能性需求，但基于关键字来匹配请求和服务描述，在普适环境下常常会导致较差的匹配结果。 针对服务发现在普适环境中的新需求，本文基于XML定义了一种轻量级的服务语义建模语言SML，SML定义了丰富的数据类型，以模板和属性的方式定义各领域的实体，可以表达丰富的语义知识；同时，本文以轻量级的推理引擎Jess为依托，将用服务建模语言定义的各应用领域的服务模板和语义知识自动转换成Jess的推理规则和事实。本文定义了一种类似XPath的服务查询语言规范，并在支持精确匹配的基础上，提出了服务的近似匹配策略，提供了各种的近似计算规则。鉴于不同用户对服务的各属性有不同的偏好程度，还提出了基于用户偏好的服务匹配策略。动态的上下文信息是服务匹配过程的重要考虑因素。本文以Jess规则来匹配服务和用户的上下文，选择适合于用户当前情况的服务。对服务各种QoS的描述支持也是服务语义建模语言提供的功能之一，为此，本文还提出了一种基于Pareto最优的服务选择策略，根据服务的QoS以及服务与请求的匹配程度来选择Pareto最优的服务。本文的上述工作已实现到服务发现系统Service CatalogNet Extended中。

COMP3016 Web Technology - Strand "XML" Lecture 3

Lecture 3: DOM and XPath Lecture slides and exercises for using DOM and XPath to access material within an XML database or document.

Obesity prevention and public health

More than 22 million children under five are now obese or overweight. Globally, an estimated 10% of school-aged children, between five and 17 years old, are overweight or obese, and the situation is getting worse. Although recognised clinically for some time as an important condition that increases risk of ill-health in affected individuals, it is only recently, that obesity has been recognised as a population-wide problem that requires preventive action. Obesity is a major contributor to diseases and disability, the associated health costs are enormous, obesity has already reached epidemic proportions in many countries, and incidence is continuing to increase in children and adults. Disturbingly the epidemic is not confined to developed countries, with many developing countries and those in transition affected. While recognised as a major population health problem, our understanding of the causes of the epidemic is poor, there has been relatively little population-based research that has focused on the prevention of unhealthy weight gain, and as a consequence knowledge regarding how and where best to intervene is limited. This book draws together the existing literature and expertise and with a view to helping set the agenda for public health action. The book is divided into three sections. Part 1 provides an overview of the context of the problem. It examines the epidemiology of obesity, the role of behavioural factors, socio-cultural factors and environmental factors in the obesity epidemic. Part 2 reviews interventions across a range of key settings and in different population groups - drawing on existing research that has aimed to increase physical activity, promote healthy eating and prevent obesity at a population level. Given how little research there is that has specifically examined the effectiveness of interventions aimed at preventing obesity per se, Part 3 explores potential opportunities to prevent obesity

Consultando fontes de dados XML heterogêneas através de modelos conceituais

XML é um padrão da W3C largamente utilizado por vários tipos de aplicações para representação de informação semi-estruturada e troca de dados pela Internet. Com o crescimento do uso de XML e do intercâmbio de informações pela Internet é muito provável que determinadas aplicações necessitem buscar uma mesma informação sobre várias fontes XML relativas a um mesmo domínio de problema. No intuito de representar a informação dessas várias fontes XML, o programador é obrigado a escolher entre muitas estruturas hierárquicas possíveis na criação dos esquemas de seus documentos XML. Um mesmo domínio de informação, desta maneira, pode então ser representado de diferentes formas nas diversas fontes de dados XML existentes. Por outro lado, verifica-se que as linguagens de consulta existentes são fortemente baseadas no conhecimento da estrutura de navegação do documento. Assim, ao consultar uma determinada informação semanticamente equivalente em várias fontes é necessário conhecer todos os esquemas envolvidos e construir consultas individuais para cada uma dessas fontes. Em um ambiente de integração, entretanto, é possível gerar um modelo global que representa essas fontes. Ao construir consultas sobre um modelo global, temos consultas integradas sobre estas fontes. Para se atingir esse objetivo, contudo, devem ser resolvidos os problemas da heterogeneidade de representação dos esquemas XML. Dessa forma, com base em uma abordagem de integração de esquemas, o presente trabalho define a linguagem de consulta CXQuery (Conceptual XQuery) que possibilita a construção de consultas sobre um modelo conceitual. Para possibilitar o retorno dos dados das fontes nas consultas feitas em CXQuery, foi desenvolvido um mecanismo de tradução da linguagem CXQuery para a linguagem de consulta XQuery 1.0. A linguagem XQuery 1.0 é umas das linguagens mais utilizadas para o acesso as fontes XML e permite que os dados possam ser retornados ao usuário. Para possibilitar essa tradução, foi definida uma metodologia de representação da informação de mapeamento através de visões XPath. Essa metodologia é relativamente eficaz no mapeamento das diferentes representações das fontes XML.

Materialização de visões XML

A grande quantidade de dados eletrônicos disponível atualmente nem sempre pode ser representada com modelos tradicionais, principalmente devido à ausência de esquema no momento da criação destes dados. Neste sentido, modelos semi-estruturados têm sido propostos; uma das abordagens utilizadas é XML, uma linguagem para troca e representação deste tipo de informação. Entretanto, consultar dados semi-estruturados pode demandar processos de extração com alto custo. Uma das alternativas para solucionar este problema é a definição de visões sobre estes dados, e a posterior materialização destas informações. O uso de visões materializadas para dados XML ainda é pouco explorado. Uma das abordagens que podem ser utilizadas é o uso de sistemas de gerenciamento de bancos de dados relacionais para o armazenamento das visões. Desse modo, informação semanticamente relacionada (informação acerca de um mesmo domínio, possivelmente representada em formatos diferentes) pode ser agrupada em uma única unidade lógica, facilitando o acesso a estes dados por parte do usuário, e introduzindo alguma estrutura nos dados semiestruturados. Dessa maneira, o usuário final submete consultas diretamente sobre a visão materializada, evitando extrações contínuas de dados nas fontes XML. A materialização de dados XML exige a definição de um repositório de dados para o armazenamento destas instâncias. Utilizando-se a abordagem relacional, é necessário definir um mecanismo para a geração do esquema lógico do banco de dados. Consultar os dados nas fontes XML exige a integração destas instâncias. Neste contexto, integrá-las significa identificar quais instâncias de dados representam o mesmo objeto do mundo real, bem como resolver ambigüidades de representação deste objeto. O problema de identificação de entidades em XML é mais complexo que em bases de dados estruturadas. Dados XML, como propostos originalmente, não carregam necessariamente a noção de chave primária ou identificador de objeto. Assim, é necessária a adoção de um mecanismo que faça a identificação das instâncias na integração destes dados. Além disso, à medida que as fontes de dados XML sofrem alterações, a visão materializada deve ser atualizada, a fim de manter-se consistente com as fontes de dados. A manutenção deve propagar as alterações feitas nos dados XML para a visão materializada. Reprocessar todo o conteúdo da visão materializada é, na maioria das vezes, muito caro. Assim, é desejável propagar as mudanças incrementalmente, ou seja, processar apenas as alterações necessárias. Neste sentido, o presente trabalho apresenta uma proposta de técnica para armazenamento de dados XML em um banco de dados relacional. A proposta utiliza ontologias para a geração do esquema lógico do banco de dados. O problema de integração de dados é mostrado. O foco principal do trabalho está na proposta de uma técnica de atribuição de identificadores a instâncias XML, baseada no uso de funções Skolem e no padrão XPath, proposto pelo W3C. Também é proposto um mecanismo para manutenção incremental deste banco, à medida que as fontes XML sofrem atualizações.

Uma abordagem Bottom-UP para a integração semântica de esquemas XML

XML (eXtensibile Markup Language) é um padrão atual para representação e intercâmbio dos semi-estruturados na Web. Dados semi-estruturados são dados não convencionais cujas instâncias de uma mesma fonte de dados podem ter representações altamente heterogêneas. Em função isto, um esquema para estes dados tende a ser extenso para suportar todas as alternativas de representação que um dado pode assumir. Parte do grande volume de dados disponível hoje na Web é composto por fontes de dados heterogêneas XML sobre diversos domínios do conhecimento. Para realizar o acesso a estas fontes, aplicações na Web necessitam de um mecanismo de integração de dados. O objetivo principal deste mecanismo é disponibilizar um esquema de dados global representativo dos diversos esquemas XML das fontes de dados. Com base neste esquema global, consultas são formuladas, traduzidas para consultas sobre os esquemas XML, executadas nas fontes de dados e os resultados retornados à aplicação. Esta tese apresenta uma abordagem para a integração semântica de esquemas XML relativos a um domínio de aplicação chamada BInXS. BInXS adota um processo bottom-up de integração, no qual o esquema global é definido para um conjunto de esquemas XML representadas atrtavés de DTDs (Document Type Definitions). A vantagem do processo bottom-up é que todas as informações dos esquemas XML são consideradas no esquema global. Desta forma, toda a informação presente nas fontes de dados pode ser consultada. O processo de integração de BInXS é baseado em um conjunto de regras e algoritmos que realizam a cnversão de cada DTD para um esquema canônico conceitual e a posterior integração semântica propriamente dita destes esquemas canônicos. O processo é semi-automático pois considera uma eventual intervenção de um usuário especialista no domínio para validar ou confirmar alternativas de resultado produzidas automaticamente. Comparada com trabalhos relacionados, BInXS apresenta as seguintes contribuições: (i) uma representação canônica conceitual para esquemas XML que é o resultado de uma anállise detalhada do modelo XML; (ii) um étodo de unificação que lida com as particularidades da integração de dados semi-estruturados e; (iii) uma estratégia de mapeamento baseada em expressões de consulta XPath que possibilita uma tradução simples de consultas globais para consultas a serem executadas nas fontes de dados XML.

Towards more personalized web: Extraction and integration of dynamic content from the Web

Information and content integration are believed to be a possible solution to the problem of information overload in the Internet. The article is an overview of a simple solution for integration of information and content on the Web. Previous approaches to content extraction and integration are discussed, followed by introduction of a novel technology to deal with the problems, based on XML processing. The article includes lessons learned from solving issues of changing webpage layout, incompatibility with HTML standards and multiplicity of the results returned. The method adopting relative XPath queries over DOM tree proves to be more robust than previous approaches to Web information integration. Furthermore, the prototype implementation demonstrates the simplicity that enables non-professional users to easily adopt this approach in their day-to-day information management routines.

Separable Hyperstructure and Delayed Link Binding

As the amount of material on the World Wide Web continues to grow, users are discovering that the Web's embedded, hard-coded, links are difficult to maintain and update. Hyperlinks need a degree of abstraction in the way they are specified together with a sound underlying document structure and the property of separability from the documents they are linking. The case is made by studying the advantages of program/data separation in computer system architectures and also by re-examining some selected hypermedia systems that have already implemented separability. The prospects for introducing more abstract links into future versions of HTML and PDF, via emerging standards such as XPath, XPointer XLink and URN, are briefly discussed.