Ontology-mediated queries for probabilistic databases
Probabilistic databases (PDBs) are usually incomplete, e.g., containing only the facts that have been extracted from the Web with high confidence. However, missing facts are often treated as being false, which leads to unintuitive results when querying PDBs. Recently, open-world probabilistic databa...
| Hoofdauteurs: | , , |
|---|---|
| Formaat: | Conference item |
| Gepubliceerd in: |
AAAI Press
2017
|
| _version_ | 1826285173275099136 |
|---|---|
| author | Borgwardt, S Ceylan, İ Lukasiewicz, T |
| author_facet | Borgwardt, S Ceylan, İ Lukasiewicz, T |
| author_sort | Borgwardt, S |
| collection | OXFORD |
| description | Probabilistic databases (PDBs) are usually incomplete, e.g., containing only the facts that have been extracted from the Web with high confidence. However, missing facts are often treated as being false, which leads to unintuitive results when querying PDBs. Recently, open-world probabilistic databases (OpenPDBs) were proposed to address this issue by allowing probabilities of unknown facts to take any value from a fixed probability interval. In this paper, we extend OpenPDBs by Datalog± ontologies, under which both upper and lower probabilities of queries become even more informative, enabling us to distinguish queries that were indistinguishable before. We show that the dichotomy between P and PP in (Open)PDBs can be lifted to the case of first-order rewritable positive programs (without negative constraints); and that the problem can become NPPP-complete, once negative constraints are allowed. We also propose an approximating semantics that circumvents the increase in complexity caused by negative constraints. |
| first_indexed | 2024-03-07T01:24:52Z |
| format | Conference item |
| id | oxford-uuid:91a01397-2020-4d88-b32b-23970838e76f |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:24:52Z |
| publishDate | 2017 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:91a01397-2020-4d88-b32b-23970838e76f2022-03-26T23:20:01ZOntology-mediated queries for probabilistic databasesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:91a01397-2020-4d88-b32b-23970838e76fSymplectic Elements at OxfordAAAI Press2017Borgwardt, SCeylan, İLukasiewicz, TProbabilistic databases (PDBs) are usually incomplete, e.g., containing only the facts that have been extracted from the Web with high confidence. However, missing facts are often treated as being false, which leads to unintuitive results when querying PDBs. Recently, open-world probabilistic databases (OpenPDBs) were proposed to address this issue by allowing probabilities of unknown facts to take any value from a fixed probability interval. In this paper, we extend OpenPDBs by Datalog± ontologies, under which both upper and lower probabilities of queries become even more informative, enabling us to distinguish queries that were indistinguishable before. We show that the dichotomy between P and PP in (Open)PDBs can be lifted to the case of first-order rewritable positive programs (without negative constraints); and that the problem can become NPPP-complete, once negative constraints are allowed. We also propose an approximating semantics that circumvents the increase in complexity caused by negative constraints. |
| spellingShingle | Borgwardt, S Ceylan, İ Lukasiewicz, T Ontology-mediated queries for probabilistic databases |
| title | Ontology-mediated queries for probabilistic databases |
| title_full | Ontology-mediated queries for probabilistic databases |
| title_fullStr | Ontology-mediated queries for probabilistic databases |
| title_full_unstemmed | Ontology-mediated queries for probabilistic databases |
| title_short | Ontology-mediated queries for probabilistic databases |
| title_sort | ontology mediated queries for probabilistic databases |
| work_keys_str_mv | AT borgwardts ontologymediatedqueriesforprobabilisticdatabases AT ceylani ontologymediatedqueriesforprobabilisticdatabases AT lukasiewiczt ontologymediatedqueriesforprobabilisticdatabases |