Loading…

Rewriting Regular XPath Queries on XML Views

We study the problem of answering queries posed on virtual views of XML documents, a problem commonly encountered when enforcing XML access control and integrating data. We approach the problem by rewriting queries on views into equivalent queries on the underlying document, and thus avoid the overh...

Full description

Saved in:
Bibliographic Details
Main Authors: Wenfei Fan, Geerts, F., Xibei Jia, Kementsietsidis, A.
Format: Conference Proceeding
Language:English
Subjects:
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 675
container_issue
container_start_page 666
container_title
container_volume
creator Wenfei Fan
Geerts, F.
Xibei Jia
Kementsietsidis, A.
description We study the problem of answering queries posed on virtual views of XML documents, a problem commonly encountered when enforcing XML access control and integrating data. We approach the problem by rewriting queries on views into equivalent queries on the underlying document, and thus avoid the overhead of view materialization and maintenance. We consider possibly recursively defined XML views and study the rewriting of both XPath and regular XPath queries. We show that while rewriting is not always possible for XPath over recursive views, it is for regular XPath; however, the rewritten query may be of exponential size. To avoid this prohibitive cost we propose a rewriting algorithm that characterizes rewritten queries as a new form of automata, and an efficient algorithm to evaluate the automaton-represented queries. These allow us to answer queries on views in linear time. We have fully implemented a prototype system, SMOQE, which yields the first regular XPath engine and a practical solution for answering queries over possibly recursively defined XML views.
doi_str_mv 10.1109/ICDE.2007.367912
format conference_proceeding
fullrecord <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_4221715</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>4221715</ieee_id><sourcerecordid>4221715</sourcerecordid><originalsourceid>FETCH-LOGICAL-i1322-168743a7791ed4f68eb6291b09502c7a7656d4e36d51a0d149139a2e67d828873</originalsourceid><addsrcrecordid>eNpVjktLw0AURscXWGr2gpv5ASbex2QeS4lVCxG1qGRXpua2jtQqSUvx31vQjd_mLA4cPqVOEQpECBfj6mpUEIAr2LqAtKey4DwaMgY8MOyrAbErcyDbHPxzxIdqgGA5t-zpWGV9_w67BYNYwkCdT2TbpXVaLfREFptl7HTzENdv-nEjXZJef650c1frlyTb_kQdzeOyl-yPQ_V8PXqqbvP6_mZcXdZ5QibK0XpnOLrdU2nN3HqZWQo4g1ACvbrobGlbI2zbEiO0aAJyiCTWtZ68dzxUZ7_dJCLTry59xO57aojQYck_sCVErg</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Rewriting Regular XPath Queries on XML Views</title><source>IEEE Xplore All Conference Series</source><creator>Wenfei Fan ; Geerts, F. ; Xibei Jia ; Kementsietsidis, A.</creator><creatorcontrib>Wenfei Fan ; Geerts, F. ; Xibei Jia ; Kementsietsidis, A.</creatorcontrib><description>We study the problem of answering queries posed on virtual views of XML documents, a problem commonly encountered when enforcing XML access control and integrating data. We approach the problem by rewriting queries on views into equivalent queries on the underlying document, and thus avoid the overhead of view materialization and maintenance. We consider possibly recursively defined XML views and study the rewriting of both XPath and regular XPath queries. We show that while rewriting is not always possible for XPath over recursive views, it is for regular XPath; however, the rewritten query may be of exponential size. To avoid this prohibitive cost we propose a rewriting algorithm that characterizes rewritten queries as a new form of automata, and an efficient algorithm to evaluate the automaton-represented queries. These allow us to answer queries on views in linear time. We have fully implemented a prototype system, SMOQE, which yields the first regular XPath engine and a practical solution for answering queries over possibly recursively defined XML views.</description><identifier>ISSN: 1063-6382</identifier><identifier>ISBN: 9781424408023</identifier><identifier>ISBN: 1424408024</identifier><identifier>EISSN: 2375-026X</identifier><identifier>EISBN: 9781424408030</identifier><identifier>EISBN: 1424408032</identifier><identifier>DOI: 10.1109/ICDE.2007.367912</identifier><language>eng</language><publisher>IEEE</publisher><subject>Access control ; Automata ; Bioinformatics ; Costs ; Engines ; Filters ; Hospitals ; Ontologies ; Prototypes ; XML</subject><ispartof>2007 IEEE 23rd International Conference on Data Engineering, 2007, p.666-675</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/4221715$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/4221715$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Wenfei Fan</creatorcontrib><creatorcontrib>Geerts, F.</creatorcontrib><creatorcontrib>Xibei Jia</creatorcontrib><creatorcontrib>Kementsietsidis, A.</creatorcontrib><title>Rewriting Regular XPath Queries on XML Views</title><title>2007 IEEE 23rd International Conference on Data Engineering</title><addtitle>ICDE</addtitle><description>We study the problem of answering queries posed on virtual views of XML documents, a problem commonly encountered when enforcing XML access control and integrating data. We approach the problem by rewriting queries on views into equivalent queries on the underlying document, and thus avoid the overhead of view materialization and maintenance. We consider possibly recursively defined XML views and study the rewriting of both XPath and regular XPath queries. We show that while rewriting is not always possible for XPath over recursive views, it is for regular XPath; however, the rewritten query may be of exponential size. To avoid this prohibitive cost we propose a rewriting algorithm that characterizes rewritten queries as a new form of automata, and an efficient algorithm to evaluate the automaton-represented queries. These allow us to answer queries on views in linear time. We have fully implemented a prototype system, SMOQE, which yields the first regular XPath engine and a practical solution for answering queries over possibly recursively defined XML views.</description><subject>Access control</subject><subject>Automata</subject><subject>Bioinformatics</subject><subject>Costs</subject><subject>Engines</subject><subject>Filters</subject><subject>Hospitals</subject><subject>Ontologies</subject><subject>Prototypes</subject><subject>XML</subject><issn>1063-6382</issn><issn>2375-026X</issn><isbn>9781424408023</isbn><isbn>1424408024</isbn><isbn>9781424408030</isbn><isbn>1424408032</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2007</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpVjktLw0AURscXWGr2gpv5ASbex2QeS4lVCxG1qGRXpua2jtQqSUvx31vQjd_mLA4cPqVOEQpECBfj6mpUEIAr2LqAtKey4DwaMgY8MOyrAbErcyDbHPxzxIdqgGA5t-zpWGV9_w67BYNYwkCdT2TbpXVaLfREFptl7HTzENdv-nEjXZJef650c1frlyTb_kQdzeOyl-yPQ_V8PXqqbvP6_mZcXdZ5QibK0XpnOLrdU2nN3HqZWQo4g1ACvbrobGlbI2zbEiO0aAJyiCTWtZ68dzxUZ7_dJCLTry59xO57aojQYck_sCVErg</recordid><startdate>200704</startdate><enddate>200704</enddate><creator>Wenfei Fan</creator><creator>Geerts, F.</creator><creator>Xibei Jia</creator><creator>Kementsietsidis, A.</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>200704</creationdate><title>Rewriting Regular XPath Queries on XML Views</title><author>Wenfei Fan ; Geerts, F. ; Xibei Jia ; Kementsietsidis, A.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i1322-168743a7791ed4f68eb6291b09502c7a7656d4e36d51a0d149139a2e67d828873</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2007</creationdate><topic>Access control</topic><topic>Automata</topic><topic>Bioinformatics</topic><topic>Costs</topic><topic>Engines</topic><topic>Filters</topic><topic>Hospitals</topic><topic>Ontologies</topic><topic>Prototypes</topic><topic>XML</topic><toplevel>online_resources</toplevel><creatorcontrib>Wenfei Fan</creatorcontrib><creatorcontrib>Geerts, F.</creatorcontrib><creatorcontrib>Xibei Jia</creatorcontrib><creatorcontrib>Kementsietsidis, A.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Wenfei Fan</au><au>Geerts, F.</au><au>Xibei Jia</au><au>Kementsietsidis, A.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Rewriting Regular XPath Queries on XML Views</atitle><btitle>2007 IEEE 23rd International Conference on Data Engineering</btitle><stitle>ICDE</stitle><date>2007-04</date><risdate>2007</risdate><spage>666</spage><epage>675</epage><pages>666-675</pages><issn>1063-6382</issn><eissn>2375-026X</eissn><isbn>9781424408023</isbn><isbn>1424408024</isbn><eisbn>9781424408030</eisbn><eisbn>1424408032</eisbn><abstract>We study the problem of answering queries posed on virtual views of XML documents, a problem commonly encountered when enforcing XML access control and integrating data. We approach the problem by rewriting queries on views into equivalent queries on the underlying document, and thus avoid the overhead of view materialization and maintenance. We consider possibly recursively defined XML views and study the rewriting of both XPath and regular XPath queries. We show that while rewriting is not always possible for XPath over recursive views, it is for regular XPath; however, the rewritten query may be of exponential size. To avoid this prohibitive cost we propose a rewriting algorithm that characterizes rewritten queries as a new form of automata, and an efficient algorithm to evaluate the automaton-represented queries. These allow us to answer queries on views in linear time. We have fully implemented a prototype system, SMOQE, which yields the first regular XPath engine and a practical solution for answering queries over possibly recursively defined XML views.</abstract><pub>IEEE</pub><doi>10.1109/ICDE.2007.367912</doi><tpages>10</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1063-6382
ispartof 2007 IEEE 23rd International Conference on Data Engineering, 2007, p.666-675
issn 1063-6382
2375-026X
language eng
recordid cdi_ieee_primary_4221715
source IEEE Xplore All Conference Series
subjects Access control
Automata
Bioinformatics
Costs
Engines
Filters
Hospitals
Ontologies
Prototypes
XML
title Rewriting Regular XPath Queries on XML Views
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T19%3A51%3A26IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Rewriting%20Regular%20XPath%20Queries%20on%20XML%20Views&rft.btitle=2007%20IEEE%2023rd%20International%20Conference%20on%20Data%20Engineering&rft.au=Wenfei%20Fan&rft.date=2007-04&rft.spage=666&rft.epage=675&rft.pages=666-675&rft.issn=1063-6382&rft.eissn=2375-026X&rft.isbn=9781424408023&rft.isbn_list=1424408024&rft_id=info:doi/10.1109/ICDE.2007.367912&rft.eisbn=9781424408030&rft.eisbn_list=1424408032&rft_dat=%3Cieee_CHZPO%3E4221715%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i1322-168743a7791ed4f68eb6291b09502c7a7656d4e36d51a0d149139a2e67d828873%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=4221715&rfr_iscdi=true