File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A framework for conditioning uncertain relational data

TitleA framework for conditioning uncertain relational data
Authors
KeywordsBoolean expressions
Concise representations
Functional dependency
Global constraints
Non-existence
Issue Date2012
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 23rd International Conference on Database and Expert Systems Applications (DEXA 2012), Vienna, Austria, 3-6 September 2012. In Lecture Notes in Computer Science, 2012, v. 7447 pt. 2, p. 71-87 How to Cite?
AbstractWe propose a framework for representing conditioned probabilistic relational data. In this framework the existence of tuples in possible worlds is determined by Boolean expressions composed from elementary events. The probability of a possible world is computed from the probabilities associated with these elementary events. In addition, a set of global constraints conditions the database. Conditioning is the formalization of the process of adding knowledge to a database. Some worlds may be impossible given the constraints and the probabilities of possible worlds are accordingly re-defined. The new constraints can come from the observation of the existence or non-existence of a tuple, from the knowledge of a specific rule, such as the existence of an exclusive set of tuples, or from the knowledge of a general rule, such as a functional dependency. We are therefore interested in computing a concise representation of the possible worlds and their respective probabilities after the addition of new constraints, namely an equivalent probabilistic database instance without constraints after conditioning. We devise and present a general algorithm for this computation. Unfortunately, the general problem involves the simplification of general Boolean expressions and is NP-hard. We therefore identify specific practical families of constraints for which we devise and present efficient algorithms. © 2012 Springer-Verlag.
DescriptionLNCS v. 7447 has title: Database and expert systems applications : 23rd international conference, DEXA 2012 ... proceedings
Persistent Identifierhttp://hdl.handle.net/10722/164907
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606

 

DC FieldValueLanguage
dc.contributor.authorTang, Ren_US
dc.contributor.authorCheng, Ren_US
dc.contributor.authorWu, Hen_US
dc.contributor.authorBressan, Sen_US
dc.date.accessioned2012-09-20T08:12:20Z-
dc.date.available2012-09-20T08:12:20Z-
dc.date.issued2012en_US
dc.identifier.citationThe 23rd International Conference on Database and Expert Systems Applications (DEXA 2012), Vienna, Austria, 3-6 September 2012. In Lecture Notes in Computer Science, 2012, v. 7447 pt. 2, p. 71-87en_US
dc.identifier.isbn9783642325960-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/164907-
dc.descriptionLNCS v. 7447 has title: Database and expert systems applications : 23rd international conference, DEXA 2012 ... proceedings-
dc.description.abstractWe propose a framework for representing conditioned probabilistic relational data. In this framework the existence of tuples in possible worlds is determined by Boolean expressions composed from elementary events. The probability of a possible world is computed from the probabilities associated with these elementary events. In addition, a set of global constraints conditions the database. Conditioning is the formalization of the process of adding knowledge to a database. Some worlds may be impossible given the constraints and the probabilities of possible worlds are accordingly re-defined. The new constraints can come from the observation of the existence or non-existence of a tuple, from the knowledge of a specific rule, such as the existence of an exclusive set of tuples, or from the knowledge of a general rule, such as a functional dependency. We are therefore interested in computing a concise representation of the possible worlds and their respective probabilities after the addition of new constraints, namely an equivalent probabilistic database instance without constraints after conditioning. We devise and present a general algorithm for this computation. Unfortunately, the general problem involves the simplification of general Boolean expressions and is NP-hard. We therefore identify specific practical families of constraints for which we devise and present efficient algorithms. © 2012 Springer-Verlag.-
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectBoolean expressions-
dc.subjectConcise representations-
dc.subjectFunctional dependency-
dc.subjectGlobal constraints-
dc.subjectNon-existence-
dc.titleA framework for conditioning uncertain relational dataen_US
dc.typeConference_Paperen_US
dc.identifier.emailTang, R: tangruiming@nus.edu.sgen_US
dc.identifier.emailCheng, R: ckcheng@cs.hku.hk-
dc.identifier.emailWu, H: huwu@i2r.a-star.edu.sg-
dc.identifier.emailBressan, S: steph@nus.edu.sg-
dc.identifier.authorityCheng, R=rp00074en_US
dc.identifier.scopuseid_2-s2.0-84866036956-
dc.identifier.hkuros206210en_US
dc.identifier.hkuros224494-
dc.identifier.volume7447-
dc.identifier.issuept. 2-
dc.identifier.spage71-
dc.identifier.epage87-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 130417-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats