Loading…
On the complexity of tree pattern containment with arithmetic comparisons
In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show...
Saved in:
| Published in: | Information processing letters 2011-08, Vol.111 (15), p.754-760 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c386t-88367ab7d1b0ce973e7264ae4200ae91ce9ba6ae23b613484e814d407da66d513 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c386t-88367ab7d1b0ce973e7264ae4200ae91ce9ba6ae23b613484e814d407da66d513 |
| container_end_page | 760 |
| container_issue | 15 |
| container_start_page | 754 |
| container_title | Information processing letters |
| container_volume | 111 |
| creator | Afrati, Foto N. Cohen, Sara Kuper, Gabriel |
| description | In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is
Π
2
P
-complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (, ⩾, =) attribute constraints.
► Query containment for tree patterns with arithmetic comparisons is studied. ► Query containment is
Π
2
P
-complete in the general case. ► For left (or right) semi-interval constraints, query containment is NP-complete. |
| doi_str_mv | 10.1016/j.ipl.2011.04.014 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_889399248</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0020019011001207</els_id><sourcerecordid>2373084601</sourcerecordid><originalsourceid>FETCH-LOGICAL-c386t-88367ab7d1b0ce973e7264ae4200ae91ce9ba6ae23b613484e814d407da66d513</originalsourceid><addsrcrecordid>eNp9kE1PHSEUhkljk14_fkB3kyamqxnPAQQmroxRa2Lixq4Jlzk3cjPDTIFr678Xe00XXbiBAM_7HvIw9hWhQ0B1tu3CMnYcEDuQHaD8xFZoNG8VYn_AVgAcWsAevrDDnLcAoKTQK3b3EJvyRI2fp2WkP6G8NPOmKYmoWVwplGJ9isWFOFEsze9QnhqX6jpRCf5vrB7zHPMx-7xxY6aT9_2I_by5frz60d4_3N5dXd63XhhVWmOE0m6tB1yDp14L0lxJR5IDOOqx3q2dcsTFWqGQRpJBOUjQg1NqOEdxxL7ve5c0_9pRLnYK2dM4ukjzLltjetH3XJpKfvuP3M67FOvnrNEoUXLJK4R7yKc550Qbu6QwufRiEeybWru1Va19U2tB2qq2Zk7fi132btwkF33I_4K1thdanVfuYs9R9fEcKNnsA0VPQ0jkix3m8MGUVxFujdc</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>871414242</pqid></control><display><type>article</type><title>On the complexity of tree pattern containment with arithmetic comparisons</title><source>ScienceDirect Journals</source><source>Backfile Package - Computer Science (Legacy) [YCS]</source><source>Backfile Package - Mathematics (Legacy) [YMT]</source><creator>Afrati, Foto N. ; Cohen, Sara ; Kuper, Gabriel</creator><creatorcontrib>Afrati, Foto N. ; Cohen, Sara ; Kuper, Gabriel</creatorcontrib><description>In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is
Π
2
P
-complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (<, ⩽, =) or right semi-interval (>, ⩾, =) attribute constraints.
► Query containment for tree patterns with arithmetic comparisons is studied. ► Query containment is
Π
2
P
-complete in the general case. ► For left (or right) semi-interval constraints, query containment is NP-complete.</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/j.ipl.2011.04.014</identifier><identifier>CODEN: IFPLAT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Arithmetic ; Arithmetic comparisons ; Combinatorics ; Combinatorics. Ordered structures ; Comparative analysis ; Complexity ; Computer science; control theory; systems ; Containment ; Decision trees ; Exact sciences and technology ; Fragmentation ; Graph theory ; Information systems. Data bases ; Mathematical problems ; Mathematics ; Memory organisation. Data processing ; Miscellaneous ; Query containment ; Query processing ; Sciences and techniques of general use ; Software ; Studies ; Theoretical computing ; Tree patterns ; Trees ; XPath queries</subject><ispartof>Information processing letters, 2011-08, Vol.111 (15), p.754-760</ispartof><rights>2011 Elsevier B.V.</rights><rights>2015 INIST-CNRS</rights><rights>Copyright Elsevier Sequoia S.A. Aug 15, 2011</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c386t-88367ab7d1b0ce973e7264ae4200ae91ce9ba6ae23b613484e814d407da66d513</citedby><cites>FETCH-LOGICAL-c386t-88367ab7d1b0ce973e7264ae4200ae91ce9ba6ae23b613484e814d407da66d513</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/S0020019011001207$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,780,784,3429,3564,27924,27925,45972,46003</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=24293765$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Afrati, Foto N.</creatorcontrib><creatorcontrib>Cohen, Sara</creatorcontrib><creatorcontrib>Kuper, Gabriel</creatorcontrib><title>On the complexity of tree pattern containment with arithmetic comparisons</title><title>Information processing letters</title><description>In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is
Π
2
P
-complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (<, ⩽, =) or right semi-interval (>, ⩾, =) attribute constraints.
► Query containment for tree patterns with arithmetic comparisons is studied. ► Query containment is
Π
2
P
-complete in the general case. ► For left (or right) semi-interval constraints, query containment is NP-complete.</description><subject>Algorithmics. Computability. Computer arithmetics</subject><subject>Applied sciences</subject><subject>Arithmetic</subject><subject>Arithmetic comparisons</subject><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Comparative analysis</subject><subject>Complexity</subject><subject>Computer science; control theory; systems</subject><subject>Containment</subject><subject>Decision trees</subject><subject>Exact sciences and technology</subject><subject>Fragmentation</subject><subject>Graph theory</subject><subject>Information systems. Data bases</subject><subject>Mathematical problems</subject><subject>Mathematics</subject><subject>Memory organisation. Data processing</subject><subject>Miscellaneous</subject><subject>Query containment</subject><subject>Query processing</subject><subject>Sciences and techniques of general use</subject><subject>Software</subject><subject>Studies</subject><subject>Theoretical computing</subject><subject>Tree patterns</subject><subject>Trees</subject><subject>XPath queries</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2011</creationdate><recordtype>article</recordtype><recordid>eNp9kE1PHSEUhkljk14_fkB3kyamqxnPAQQmroxRa2Lixq4Jlzk3cjPDTIFr678Xe00XXbiBAM_7HvIw9hWhQ0B1tu3CMnYcEDuQHaD8xFZoNG8VYn_AVgAcWsAevrDDnLcAoKTQK3b3EJvyRI2fp2WkP6G8NPOmKYmoWVwplGJ9isWFOFEsze9QnhqX6jpRCf5vrB7zHPMx-7xxY6aT9_2I_by5frz60d4_3N5dXd63XhhVWmOE0m6tB1yDp14L0lxJR5IDOOqx3q2dcsTFWqGQRpJBOUjQg1NqOEdxxL7ve5c0_9pRLnYK2dM4ukjzLltjetH3XJpKfvuP3M67FOvnrNEoUXLJK4R7yKc550Qbu6QwufRiEeybWru1Va19U2tB2qq2Zk7fi132btwkF33I_4K1thdanVfuYs9R9fEcKNnsA0VPQ0jkix3m8MGUVxFujdc</recordid><startdate>20110815</startdate><enddate>20110815</enddate><creator>Afrati, Foto N.</creator><creator>Cohen, Sara</creator><creator>Kuper, Gabriel</creator><general>Elsevier B.V</general><general>Elsevier</general><general>Elsevier Sequoia S.A</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20110815</creationdate><title>On the complexity of tree pattern containment with arithmetic comparisons</title><author>Afrati, Foto N. ; Cohen, Sara ; Kuper, Gabriel</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c386t-88367ab7d1b0ce973e7264ae4200ae91ce9ba6ae23b613484e814d407da66d513</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2011</creationdate><topic>Algorithmics. Computability. Computer arithmetics</topic><topic>Applied sciences</topic><topic>Arithmetic</topic><topic>Arithmetic comparisons</topic><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Comparative analysis</topic><topic>Complexity</topic><topic>Computer science; control theory; systems</topic><topic>Containment</topic><topic>Decision trees</topic><topic>Exact sciences and technology</topic><topic>Fragmentation</topic><topic>Graph theory</topic><topic>Information systems. Data bases</topic><topic>Mathematical problems</topic><topic>Mathematics</topic><topic>Memory organisation. Data processing</topic><topic>Miscellaneous</topic><topic>Query containment</topic><topic>Query processing</topic><topic>Sciences and techniques of general use</topic><topic>Software</topic><topic>Studies</topic><topic>Theoretical computing</topic><topic>Tree patterns</topic><topic>Trees</topic><topic>XPath queries</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Afrati, Foto N.</creatorcontrib><creatorcontrib>Cohen, Sara</creatorcontrib><creatorcontrib>Kuper, Gabriel</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Afrati, Foto N.</au><au>Cohen, Sara</au><au>Kuper, Gabriel</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On the complexity of tree pattern containment with arithmetic comparisons</atitle><jtitle>Information processing letters</jtitle><date>2011-08-15</date><risdate>2011</risdate><volume>111</volume><issue>15</issue><spage>754</spage><epage>760</epage><pages>754-760</pages><issn>0020-0190</issn><eissn>1872-6119</eissn><coden>IFPLAT</coden><abstract>In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is
Π
2
P
-complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (<, ⩽, =) or right semi-interval (>, ⩾, =) attribute constraints.
► Query containment for tree patterns with arithmetic comparisons is studied. ► Query containment is
Π
2
P
-complete in the general case. ► For left (or right) semi-interval constraints, query containment is NP-complete.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/j.ipl.2011.04.014</doi><tpages>7</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0020-0190 |
| ispartof | Information processing letters, 2011-08, Vol.111 (15), p.754-760 |
| issn | 0020-0190 1872-6119 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_889399248 |
| source | ScienceDirect Journals; Backfile Package - Computer Science (Legacy) [YCS]; Backfile Package - Mathematics (Legacy) [YMT] |
| subjects | Algorithmics. Computability. Computer arithmetics Applied sciences Arithmetic Arithmetic comparisons Combinatorics Combinatorics. Ordered structures Comparative analysis Complexity Computer science control theory systems Containment Decision trees Exact sciences and technology Fragmentation Graph theory Information systems. Data bases Mathematical problems Mathematics Memory organisation. Data processing Miscellaneous Query containment Query processing Sciences and techniques of general use Software Studies Theoretical computing Tree patterns Trees XPath queries |
| title | On the complexity of tree pattern containment with arithmetic comparisons |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T05%3A03%3A06IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=On%20the%20complexity%20of%20tree%20pattern%20containment%20with%20arithmetic%20comparisons&rft.jtitle=Information%20processing%20letters&rft.au=Afrati,%20Foto%20N.&rft.date=2011-08-15&rft.volume=111&rft.issue=15&rft.spage=754&rft.epage=760&rft.pages=754-760&rft.issn=0020-0190&rft.eissn=1872-6119&rft.coden=IFPLAT&rft_id=info:doi/10.1016/j.ipl.2011.04.014&rft_dat=%3Cproquest_cross%3E2373084601%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c386t-88367ab7d1b0ce973e7264ae4200ae91ce9ba6ae23b613484e814d407da66d513%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=871414242&rft_id=info:pmid/&rfr_iscdi=true |