File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient inference control for range Sum queries

TitleEfficient inference control for range Sum queries
Authors
Issue Date1984
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 1984, v. 32 n. 1-2, p. 77-86 How to Cite?
AbstractThe inference control technique called Auditing is discussed in this paper. Auditing is in many ways better than the previously known techniques. Auditing would log all answered queries, and use this information to decide whether answering a new query could lead to compromise. Unfortunately, expect for small databases, auditing may not be readily usable in practice because of its excessive time and space complexity in processing a new query. In this paper we restrict our study to Sum queries, if there are n records in the database, the problem of determining whether or not answering a new Sum query could lead to compromise may take O(n2) time and space. Furthermore, it is unrealistic to assume that the user can obtain statistical information of any subset of the records in the database; we assume that statistical information is only available for those subsets of records in which one of their attribute values lies within a certain range (range query). With the proper data structure, the time and space complexity for checking if a new range query could be answered can be reduced to O(n) time and space, or O(t log n) time with O(n2) space for t new range queries with t≥n. © 1984.
Persistent Identifierhttp://hdl.handle.net/10722/152215
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720

 

DC FieldValueLanguage
dc.contributor.authorChin, FYen_US
dc.contributor.authorKossowski, Pen_US
dc.contributor.authorLoh, SCen_US
dc.date.accessioned2012-06-26T06:36:35Z-
dc.date.available2012-06-26T06:36:35Z-
dc.date.issued1984en_US
dc.identifier.citationTheoretical Computer Science, 1984, v. 32 n. 1-2, p. 77-86en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/152215-
dc.description.abstractThe inference control technique called Auditing is discussed in this paper. Auditing is in many ways better than the previously known techniques. Auditing would log all answered queries, and use this information to decide whether answering a new query could lead to compromise. Unfortunately, expect for small databases, auditing may not be readily usable in practice because of its excessive time and space complexity in processing a new query. In this paper we restrict our study to Sum queries, if there are n records in the database, the problem of determining whether or not answering a new Sum query could lead to compromise may take O(n2) time and space. Furthermore, it is unrealistic to assume that the user can obtain statistical information of any subset of the records in the database; we assume that statistical information is only available for those subsets of records in which one of their attribute values lies within a certain range (range query). With the proper data structure, the time and space complexity for checking if a new range query could be answered can be reduced to O(n) time and space, or O(t log n) time with O(n2) space for t new range queries with t≥n. © 1984.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.titleEfficient inference control for range Sum queriesen_US
dc.typeArticleen_US
dc.identifier.emailChin, FY:chin@cs.hku.hken_US
dc.identifier.authorityChin, FY=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0021459073en_US
dc.identifier.volume32en_US
dc.identifier.issue1-2en_US
dc.identifier.spage77en_US
dc.identifier.epage86en_US
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChin, FY=7005101915en_US
dc.identifier.scopusauthoridKossowski, P=6506219724en_US
dc.identifier.scopusauthoridLoh, SC=36837897400en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats