{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T23:07:38Z","timestamp":1675724858217},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2001,9]]},"abstract":"Although there are many applications where an object-oriented data model is a good way of representing and querying data, current object database systems are unable to handle objects whose attributes are uncertain. In this article, we extend previous work by Kornatzky and Shimony to develop an algebra to handle object bases with uncertainty. We propose concepts of consistency for such object bases, together with an NP-completeness result, and classes of probabilistic object bases for which consistency is polynomially checkable. In addition, as certain operations involve conjunctions and disjunctions of events, and as the probability of conjunctive and disjunctive events depends both on the probabilities of the primitive events involved as well as on what is known (if anything) about the relationship between the events, we show how all our algebraic operations may be performed under arbitrary probabilistic conjunction and disjunction strategies. We also develop a host of equivalence results in our algebra, which may be used as rewrite rules for query optimization. Last but not least, we have developed a prototype probabilistic object base server on top of ObjectStore. We describe experiments to assess the efficiency of different possible rewrite rules.<\/jats:p>","DOI":"10.1145\/502030.502031","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:03Z","timestamp":1027769343000},"page":"264-312","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Probabilistic object bases"],"prefix":"10.1145","volume":"26","author":[{"given":"Thomas","family":"Eiter","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Wien, Wien, Austria"}]},{"given":"James J.","family":"Lu","sequence":"additional","affiliation":[{"name":"Bucknell University, Lewisburg, PA"}]},{"given":"Thomas","family":"Lukasiewicz","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Wien, Austria"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park"}]}],"member":"320","published-online":{"date-parts":[[2001,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"ABITEBOUL S.","unstructured":"ABITEBOUL , S. , HULL , R. , AND VIANU , V. 1995. Foundations of Databases . Addison-Wesley , Reading, Mass .]] ABITEBOUL, S., HULL, R., AND VIANU, V. 1995. Foundations of Databases. Addison-Wesley, Reading, Mass.]]"},{"key":"e_1_2_1_2_1","first-page":"40","volume-title":"Proceedings of DOOD-89","author":"ATKINSON M.","year":"1989","unstructured":"ATKINSON , M. , DEWITT , D. , MAIER , D. , BANCILHON , F. , DITTRICH , K. , AND ZDONIK , S. 1989 . The objectoriented database system manifesto . In Proceedings of DOOD-89 , Elsevier Science, Amsterdam, the Netherlands , 40 - 57 .]] ATKINSON, M., DEWITT, D., MAIER, D., BANCILHON, F., DITTRICH, K., AND ZDONIK, S. 1989. The objectoriented database system manifesto. In Proceedings of DOOD-89, Elsevier Science, Amsterdam, the Netherlands, 40-57.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"BANCILHON F. DELOBEL C. AND KANELLAKIS P. (Eds.) 1991. Building an Object-Oriented Database System: The Story of O2 . Morgan Kaufmann Los Altos Calif.]] BANCILHON F. DELOBEL C. AND KANELLAKIS P. (Eds.) 1991. Building an Object-Oriented Database System: The Story of O2 . Morgan Kaufmann Los Altos Calif.]]","DOI":"10.1145\/141484.130289"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.166990"},{"key":"e_1_2_1_5_1","volume-title":"Object Oriented Database Systems: Concepts and Architectures","author":"BERTINO E.","unstructured":"BERTINO , E. AND MARTINO , L. 1993. Object Oriented Database Systems: Concepts and Architectures . Addison-Wesley , Wokingham, UK .]] BERTINO,E.AND MARTINO, L. 1993. Object Oriented Database Systems: Concepts and Architectures. Addison-Wesley, Wokingham, UK.]]"},{"key":"e_1_2_1_6_1","volume-title":"The Laws of Thought","author":"BOOLE G.","unstructured":"BOOLE , G. 1854. The Laws of Thought . Macmillan , London .]] BOOLE, G. 1854. The Laws of Thought. Macmillan, London.]]"},{"key":"e_1_2_1_7_1","first-page":"71","volume-title":"Proceedings of VLDB-87","author":"CAVALLO R.","year":"1987","unstructured":"CAVALLO , R. AND PITTARELLI , M. 1987 . The theory of probabilistic databases . In Proceedings of VLDB-87 , Morgan Kaufmann, Los Altos, Calif. , 71 - 81 .]] CAVALLO,R.AND PITTARELLI, M. 1987. The theory of probabilistic databases. In Proceedings of VLDB-87, Morgan Kaufmann, Los Altos, Calif., 71-81.]]"},{"key":"e_1_2_1_8_1","first-page":"391","volume-title":"Proceedings of the Fourteenth International Conference on Logic Programming (ICLP '97 ), MIT Press","author":"DEKHTYAR A.","year":"1997","unstructured":"DEKHTYAR , A. AND SUBRAHMANIAN , V. S. 1997 . Hybrid probabilistic programs . In Proceedings of the Fourteenth International Conference on Logic Programming (ICLP '97 ), MIT Press , Cambridge, Mass. , 391 - 405 .]] DEKHTYAR,A.AND SUBRAHMANIAN, V. S. 1997. Hybrid probabilistic programs. In Proceedings of the Fourteenth International Conference on Logic Programming (ICLP '97 ), MIT Press, Cambridge, Mass., 391-405.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/232753.232796"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-023X(98)00015-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/288086.288087"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646203.682127"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Second World Conference on Integrated Design and Process Technology, Society for Design and Process Science, 17-30","author":"FUHR N.","year":"1996","unstructured":"FUHR , N. AND R~LLEKE , T. 1996 . A probabilistic NF2 relational algebra for integrated information retrieval and database systems . In Proceedings of the Second World Conference on Integrated Design and Process Technology, Society for Design and Process Science, 17-30 .]] FUHR,N.AND R~LLEKE, T. 1996. A probabilistic NF2 relational algebra for integrated information retrieval and database systems. In Proceedings of the Second World Conference on Integrated Design and Process Technology, Society for Design and Process Science, 17-30.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_2_1_18_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"GAREY M.R.","unstructured":"GAREY , M.R. AND JOHNSON , D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . Freeman , San Francisco .]] GAREY,M.R.AND JOHNSON, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.]]"},{"issue":"3","key":"e_1_2_1_19_1","first-page":"19","article-title":"The cascades framework for query optimization","volume":"18","author":"GRAEFE G.","year":"1995","unstructured":"GRAEFE , G. 1995 . The cascades framework for query optimization . Data Eng. Bull. 18 , 3 , 19 - 29 .]] GRAEFE, G. 1995. The cascades framework for query optimization. Data Eng. Bull. 18, 3, 19-29.]]","journal-title":"Data Eng. Bull."},{"key":"e_1_2_1_20_1","volume-title":"1997. The Handbook of Multimedia Information Management","author":"GROSKY W. I.","unstructured":"GROSKY , W. I. , JAIN , R. , AND MEHROTRA , R. (Eds.) 1997. The Handbook of Multimedia Information Management . Prentice-Hall , Englewoood Cliffs, NJ .]] GROSKY, W. I., JAIN, R., AND MEHROTRA, R. (Eds.) 1997. The Handbook of Multimedia Information Management. Prentice-Hall, Englewoood Cliffs, NJ.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115815"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2074394.2074428"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90019-V"},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of EDBT-92","author":"KIESSLING W.","unstructured":"KIESSLING , W. , TH~NE , H. , AND G~NTZER , U. 1992. Database support for problematic knowledge . In Proceedings of EDBT-92 , Lecture Notes in Computer Science , vol. 580 , Springer-Verlag , New York , 421-436.]] KIESSLING, W., TH~NE, H., AND G~NTZER, U. 1992. Database support for problematic knowledge. In Proceedings of EDBT-92, Lecture Notes in Computer Science, vol. 580, Springer-Verlag, New York, 421-436.]]"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of ICDT-88","author":"KIFER M.","unstructured":"KIFER , M. AND LI , A. 1988. On the semantics of rule-based expert systems with uncertainty . In Proceedings of ICDT-88 , Lecture Notes in Computer Science , vol. 326 , Springer-Verlag , New York , 102-117.]] KIFER,M.AND LI, A. 1988. On the semantics of rule-based expert systems with uncertainty. In Proceedings of ICDT-88, Lecture Notes in Computer Science, vol. 326, Springer-Verlag, New York, 102-117.]]"},{"key":"e_1_2_1_26_1","volume-title":"Introduction to Object-Oriented Databases","author":"KIM W.","unstructured":"KIM , W. 1990. Introduction to Object-Oriented Databases . MIT Press , Cambridge, Mass .]] KIM, W. 1990. Introduction to Object-Oriented Databases. MIT Press, Cambridge, Mass.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2074226.2074262"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90012-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/3468.487958"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/648308.754137"},{"key":"e_1_2_1_31_1","first-page":"254","volume-title":"Proceedings of the 1994 International Logic Programming Symposium (ILPS '94 ), MIT Press","author":"LAKSHMANAN L.V.","year":"1994","unstructured":"LAKSHMANAN , L.V. S. AND SADRI , F. 1994 b. Probabilistic deductive databases . In Proceedings of the 1994 International Logic Programming Symposium (ILPS '94 ), MIT Press , Cambridge, Mass. , 254 - 268 .]] LAKSHMANAN,L.V.S.AND SADRI, F. 1994b. Probabilistic deductive databases. In Proceedings of the 1994 International Logic Programming Symposium (ILPS '94 ), MIT Press, Cambridge, Mass., 254-268.]]"},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Workshop on Logic in Databases (LID '96 )","author":"LAKSHMANAN L.V.","unstructured":"LAKSHMANAN , L.V. S. AND SHIRI , N. 1996. A parametric approach to deductive databases with uncertainty . In Proceedings of the International Workshop on Logic in Databases (LID '96 ) , Lecture Notes in Computer Science , vol. 1154 , Springer-Verlag , New York , 61-81.]] LAKSHMANAN,L.V.S.AND SHIRI, N. 1996. A parametric approach to deductive databases with uncertainty. In Proceedings of the International Workshop on Logic in Databases (LID '96 ), Lecture Notes in Computer Science, vol. 1154, Springer-Verlag, New York, 61-81.]]"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261131"},{"key":"e_1_2_1_34_1","first-page":"334","volume-title":"Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI-97)","author":"LASKEY K.B.","year":"1997","unstructured":"LASKEY , K.B. AND MAHONEY , S. M. 1997 . Network fragments: Representing knowledge for constructing probabilistic models . In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI-97) , Morgan-Kaufmann, Los Altos, Calif. , 334 - 341 .]] LASKEY,K.B.AND MAHONEY, S. M. 1997. Network fragments: Representing knowledge for constructing probabilistic models. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI-97), Morgan-Kaufmann, Los Altos, Calif., 334-341.]]"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.277772"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/646636.700229"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/645475.654153"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/502030.502031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T20:43:50Z","timestamp":1672692230000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/502030.502031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,9]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2001,9]]}},"alternative-id":["10.1145\/502030.502031"],"URL":"https:\/\/doi.org\/10.1145\/502030.502031","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,9]]},"assertion":[{"value":"2001-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}