Loading…
Bounds in Ontology-Based Data Access via Circuit Complexity
Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one that can be answered without any use of theory. Thus the problem reduces to the standard dat...
Saved in:
Published in: | Theory of computing systems 2017-08, Vol.61 (2), p.464-493 |
---|---|
Main Author: | |
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-c316t-a00c0e8520d570087d074c8e5693e675eaeb56273c38c51880712163db6a14dc3 |
---|---|
cites | cdi_FETCH-LOGICAL-c316t-a00c0e8520d570087d074c8e5693e675eaeb56273c38c51880712163db6a14dc3 |
container_end_page | 493 |
container_issue | 2 |
container_start_page | 464 |
container_title | Theory of computing systems |
container_volume | 61 |
creator | Podolskii, Vladimir V. |
description | Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one that can be answered without any use of theory. Thus the problem reduces to the standard database setting. However, the size of the query may increase substantially during the reformulation. In this survey we review a recently developed framework on proving lower and upper bounds on the size of this reformulation by employing methods and results from Boolean Circuit Complexity. The survey does not assume from the reader any prior knowledge on ontology-based data access. |
doi_str_mv | 10.1007/s00224-016-9707-z |
format | article |
fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_1917626755</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1917626755</sourcerecordid><originalsourceid>FETCH-LOGICAL-c316t-a00c0e8520d570087d074c8e5693e675eaeb56273c38c51880712163db6a14dc3</originalsourceid><addsrcrecordid>eNp1kDtPwzAUhS0EEqXwA9gsMRuu7fgRMbXhKVXqArPlOm6VKo2DnSDaX09KGFiY7hnOd670IXRN4ZYCqLsEwFhGgEqSK1DkcIImNOOcQJbD6U9mJOMCztFFSlsA4Bpggu7noW_KhKsGL5su1GGzJ3ObfIkfbGfxzDmfEv6sLC6q6Pqqw0XYtbX_qrr9JTpb2zr5q987Re9Pj2_FC1ksn1-L2YI4TmVHLIADrwWDUigArUpQmdNeyJx7qYS3fiUkU9xx7QTVGhRlVPJyJS3NSsen6GbcbWP46H3qzDb0sRleGppTJdkwIoYWHVsuhpSiX5s2Vjsb94aCOToyoyMzODJHR-YwMGxk0tBtNj7-Wf4X-gYO8meY</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1917626755</pqid></control><display><type>article</type><title>Bounds in Ontology-Based Data Access via Circuit Complexity</title><source>ABI/INFORM global</source><source>Access via Business Source (EBSCOhost)</source><source>Springer Nature</source><creator>Podolskii, Vladimir V.</creator><creatorcontrib>Podolskii, Vladimir V.</creatorcontrib><description>Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one that can be answered without any use of theory. Thus the problem reduces to the standard database setting. However, the size of the query may increase substantially during the reformulation. In this survey we review a recently developed framework on proving lower and upper bounds on the size of this reformulation by employing methods and results from Boolean Circuit Complexity. The survey does not assume from the reader any prior knowledge on ontology-based data access.</description><identifier>ISSN: 1432-4350</identifier><identifier>EISSN: 1433-0490</identifier><identifier>DOI: 10.1007/s00224-016-9707-z</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Boolean algebra ; Circuits ; Complexity ; Computer Science ; Knowledge representation ; Ontology ; Theory ; Theory of Computation ; Upper bounds</subject><ispartof>Theory of computing systems, 2017-08, Vol.61 (2), p.464-493</ispartof><rights>Springer Science+Business Media New York 2016</rights><rights>Theory of Computing Systems is a copyright of Springer, 2017.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c316t-a00c0e8520d570087d074c8e5693e675eaeb56273c38c51880712163db6a14dc3</citedby><cites>FETCH-LOGICAL-c316t-a00c0e8520d570087d074c8e5693e675eaeb56273c38c51880712163db6a14dc3</cites><orcidid>0000-0001-7154-138X</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/1917626755/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/1917626755?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,44363,74895</link.rule.ids></links><search><creatorcontrib>Podolskii, Vladimir V.</creatorcontrib><title>Bounds in Ontology-Based Data Access via Circuit Complexity</title><title>Theory of computing systems</title><addtitle>Theory Comput Syst</addtitle><description>Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one that can be answered without any use of theory. Thus the problem reduces to the standard database setting. However, the size of the query may increase substantially during the reformulation. In this survey we review a recently developed framework on proving lower and upper bounds on the size of this reformulation by employing methods and results from Boolean Circuit Complexity. The survey does not assume from the reader any prior knowledge on ontology-based data access.</description><subject>Boolean algebra</subject><subject>Circuits</subject><subject>Complexity</subject><subject>Computer Science</subject><subject>Knowledge representation</subject><subject>Ontology</subject><subject>Theory</subject><subject>Theory of Computation</subject><subject>Upper bounds</subject><issn>1432-4350</issn><issn>1433-0490</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kDtPwzAUhS0EEqXwA9gsMRuu7fgRMbXhKVXqArPlOm6VKo2DnSDaX09KGFiY7hnOd670IXRN4ZYCqLsEwFhGgEqSK1DkcIImNOOcQJbD6U9mJOMCztFFSlsA4Bpggu7noW_KhKsGL5su1GGzJ3ObfIkfbGfxzDmfEv6sLC6q6Pqqw0XYtbX_qrr9JTpb2zr5q987Re9Pj2_FC1ksn1-L2YI4TmVHLIADrwWDUigArUpQmdNeyJx7qYS3fiUkU9xx7QTVGhRlVPJyJS3NSsen6GbcbWP46H3qzDb0sRleGppTJdkwIoYWHVsuhpSiX5s2Vjsb94aCOToyoyMzODJHR-YwMGxk0tBtNj7-Wf4X-gYO8meY</recordid><startdate>20170801</startdate><enddate>20170801</enddate><creator>Podolskii, Vladimir V.</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>PYYUZ</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0001-7154-138X</orcidid></search><sort><creationdate>20170801</creationdate><title>Bounds in Ontology-Based Data Access via Circuit Complexity</title><author>Podolskii, Vladimir V.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c316t-a00c0e8520d570087d074c8e5693e675eaeb56273c38c51880712163db6a14dc3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Boolean algebra</topic><topic>Circuits</topic><topic>Complexity</topic><topic>Computer Science</topic><topic>Knowledge representation</topic><topic>Ontology</topic><topic>Theory</topic><topic>Theory of Computation</topic><topic>Upper bounds</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Podolskii, Vladimir V.</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Access via ABI/INFORM (ProQuest)</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies & Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer science database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering 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><collection>ABI/INFORM global</collection><collection>Computing Database</collection><collection>Science Database</collection><collection>Engineering Database</collection><collection>ProQuest advanced technologies & aerospace journals</collection><collection>ProQuest Advanced Technologies & Aerospace Collection</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering collection</collection><collection>ABI/INFORM Collection China</collection><collection>ProQuest Central Basic</collection><jtitle>Theory of computing systems</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Podolskii, Vladimir V.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Bounds in Ontology-Based Data Access via Circuit Complexity</atitle><jtitle>Theory of computing systems</jtitle><stitle>Theory Comput Syst</stitle><date>2017-08-01</date><risdate>2017</risdate><volume>61</volume><issue>2</issue><spage>464</spage><epage>493</epage><pages>464-493</pages><issn>1432-4350</issn><eissn>1433-0490</eissn><abstract>Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one that can be answered without any use of theory. Thus the problem reduces to the standard database setting. However, the size of the query may increase substantially during the reformulation. In this survey we review a recently developed framework on proving lower and upper bounds on the size of this reformulation by employing methods and results from Boolean Circuit Complexity. The survey does not assume from the reader any prior knowledge on ontology-based data access.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s00224-016-9707-z</doi><tpages>30</tpages><orcidid>https://orcid.org/0000-0001-7154-138X</orcidid></addata></record> |
fulltext | fulltext |
identifier | ISSN: 1432-4350 |
ispartof | Theory of computing systems, 2017-08, Vol.61 (2), p.464-493 |
issn | 1432-4350 1433-0490 |
language | eng |
recordid | cdi_proquest_journals_1917626755 |
source | ABI/INFORM global; Access via Business Source (EBSCOhost); Springer Nature |
subjects | Boolean algebra Circuits Complexity Computer Science Knowledge representation Ontology Theory Theory of Computation Upper bounds |
title | Bounds in Ontology-Based Data Access via Circuit Complexity |
url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T11%3A00%3A04IST&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=Bounds%20in%20Ontology-Based%20Data%20Access%20via%20Circuit%20Complexity&rft.jtitle=Theory%20of%20computing%20systems&rft.au=Podolskii,%20Vladimir%20V.&rft.date=2017-08-01&rft.volume=61&rft.issue=2&rft.spage=464&rft.epage=493&rft.pages=464-493&rft.issn=1432-4350&rft.eissn=1433-0490&rft_id=info:doi/10.1007/s00224-016-9707-z&rft_dat=%3Cproquest_cross%3E1917626755%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c316t-a00c0e8520d570087d074c8e5693e675eaeb56273c38c51880712163db6a14dc3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1917626755&rft_id=info:pmid/&rfr_iscdi=true |