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...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2017-08, Vol.61 (2), p.464-493
Main Author: Podolskii, Vladimir V.
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 &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; 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 &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; 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