A Framework for Conditioning Uncertain
| dc.contributor.author | TANG, Ruiming | en_US |
| dc.contributor.author | CHENG, Reynold | en_US |
| dc.contributor.author | WU, Huayu | en_US |
| dc.contributor.author | BRESSAN, Stephane | en_US |
| dc.date.accessioned | 2012-02-22T06:41:47Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:05Z | |
| dc.date.available | 2012-02-22T06:41:47Z | en_US |
| dc.date.available | 2017-01-23T07:00:05Z | |
| dc.date.issued | 2012-01-25 | en_US |
| dc.description.abstract | We 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. | en_US |
| dc.format.extent | 572066 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/3584 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRB1/12 | en_US |
| dc.title | A Framework for Conditioning Uncertain | en_US |
| dc.type | Technical Report | en_US |