On repairing and querying inconsistent probabilistic spatio-temporal databases. (English) Zbl 1419.68048
Summary: We formally introduce the concept of repair and consistent answer for inconsistent probabilistic spatio-temporal databases. We start by defining the syntax and semantics of SPOT databases, a declarative framework that has been explored in recent years for the representation of spatio-temporal data with uncertainty expressed as probability intervals. In this framework we define and study multiple types of repairs. We also extend the concept of consistent answer to this framework and find that this can be done in several different ways. In emphasizing tractable cases we propose polynomial-time algorithms for computing consistent answers and repairs based on probability interval expansion, and experimentally validate our approach.
MSC:
| 68P15 | Database theory |
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
References:
| [1] | Parisi, F.; Grant, J., Repairs and consistent answers for inconsistent probabilistic spatio-temporal databases, (Proc. of Int. Conf. on Scalable Uncertainty Management (SUM) (2014)), 265-279 |
| [2] | Pelanis, M.; Saltenis, S.; Jensen, C. S., Indexing the past, present, and anticipated future positions of moving objects, ACM Trans. Database Syst., 31, 1, 255-298 (2006) |
| [3] | Tao, Y.; Papadias, D.; Sun, J., The TPR*-tree: an optimized spatio-temporal access method for predictive queries, (VLDB (2003)), 790-801 |
| [4] | Kollios, G.; Gunopulos, D.; Tsotras, V. J., On indexing mobile objects, (Int. Symposium on Principles of Database Systems (PODS) (1999)), 261-272 |
| [5] | Agarwal, P. K.; Arge, L.; Erickson, J., Indexing moving points, J. Comput. Syst. Sci., 66, 1, 207-243 (2003) · Zbl 1026.68143 |
| [6] | Pfoser, D.; Jensen, C. S.; Theodoridis, Y., Novel approaches in query processing for moving object trajectories, (VLDB (2000)), 395-406 |
| [7] | Hadjieleftheriou, M.; Kollios, G.; Tsotras, V. J.; Gunopulos, D., Efficient indexing of spatiotemporal objects, (EDBT (2002)), 251-268 · Zbl 1054.68783 |
| [8] | Tao, Y.; Cheng, R.; Xiao, X.; Ngai, W. K.; Kao, B.; Prabhakar, S., Indexing multi-dimensional uncertain data with arbitrary probability density functions, (VLDB (2005)), 922-933 |
| [9] | Dai, X.; Yiu, M. L.; Mamoulis, N.; Tao, Y.; Vaitis, M., Probabilistic spatial queries on existentially uncertain data, (SSTD (2005)), 400-417 |
| [10] | Cao, H.; Wolfson, O.; Trajcevski, G., Spatio-temporal data reduction with deterministic error bounds, VLDB J., 15, 3, 211-228 (2006) |
| [11] | Benjelloun, O.; Sarma, A. D.; Halevy, A. Y.; Widom, J., ULDBs: databases with uncertainty and lineage, (VLDB (2006)), 953-964 |
| [12] | Ahson, S. A.; Ilyas, M., Location-Based Services Handbook: Applications, Technologies, and Security (2010), CRC Press: CRC Press Hoboken, NJ |
| [13] | Garcia Alvarez, M. G.; Ivanova, I.; Dilo, A.; Morales, J., Representing positional uncertainty of individual and aggregated trajectories of moving objects, (Proc. of ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2013)), 436-439 |
| [14] | Karimi, H. A., Advanced Location-Based Technologies and Services (2013), CRC Press: CRC Press Hoboken, NJ |
| [15] | Parker, A.; Subrahmanian, V. S.; Grant, J., A logical formulation of probabilistic spatial databases, IEEE Trans. Knowl. Data Eng., 1541-1556 (2007) |
| [16] | Mittu, R.; Ross, R., Building upon the coalitions agent experiment (COAX) - integration of multimedia information in GCCS-m using IMPACT, (Multimedia Inf. Syst. (2003)), 35-44 |
| [17] | Hammel, T.; Rogers, T. J.; Yetso, B., Fusing live sensor data into situational multimedia views, (Multimedia Information Systems (2003)), 145-156 |
| [18] | Bayir, M. A.; Demirbas, M.; Eagle, N., Mobility profiler: a framework for discovering mobility profiles of cell phone users, Pervasive Mob. Comput., 6, 4, 435-454 (2010) |
| [19] | Karbassi, A.; Barth, M., Vehicle route prediction and time of arrival estimation techniques for improved transportation system management, (Proceedings of the 2013 IEEE Intelligent Vehicles Symposium (2003)), 511-516 |
| [20] | Kurkovsky, S.; Harihar, K., Using ubiquitous computing in interactive mobile marketing, Pers. Ubiquitous Comput., 10, 4, 227-240 (2006) |
| [21] | Parker, A.; Infantes, G.; Grant, J.; Subrahmanian, V. S., SPOT databases: efficient consistency checking and optimistic selection in probabilistic spatial databases, IEEE Trans. Knowl. Data Eng., 21, 1, 92-107 (2009) |
| [22] | Parisi, F.; Parker, A.; Grant, J.; Subrahmanian, V. S., Scaling cautious selection in spatial probabilistic temporal databases, (Methods for Handling Imperfect Spatial Information. Methods for Handling Imperfect Spatial Information, Stud. Fuzziness Soft Comput., vol. 256 (2010), Springer), 307-340 |
| [23] | Grant, J.; Molinaro, C.; Parisi, F., Aggregate count queries in probabilistic spatio-temporal databases, (Int. Conf. on Scalable Uncertainty Management (SUM) (2013)), 255-268 |
| [24] | Grant, J.; Parisi, F.; Parker, A.; Subrahmanian, V. S., An AGM-style belief revision mechanism for probabilistic spatio-temporal logics, Artif. Intell., 174, 1, 72-104 (2010) · Zbl 1185.68673 |
| [25] | Sedky, M. H.; Moniri, M.; Chibelushi, C. C., Classification of smart video surveillance systems for commercial applications, (Proc. of IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS) (2005)), 638-643 |
| [26] | An, L.; Chen, X.; Kafai, M.; Yang, S.; Bhanu, B., Improving person re-identification by soft biometrics based reranking, (Proc. of International Conference on Distributed Smart Cameras (ICDSC) (2013)), 1-6 |
| [27] | Zhang, L.; Kalashnikov, D. V.; Mehrotra, S.; Vaisenberg, R., Context-based person identification framework for smart video surveillance, Mach. Vis. Appl., 25, 7, 1711-1725 (2014) |
| [28] | Bedagkar-Gala, A.; Shah, S. K., A survey of approaches and trends in person re-identification, Image Vis. Comput., 32, 4, 270-286 (2014) |
| [29] | Pfoser, D.; Jensen, C. S., Capturing the uncertainty of moving-object representations, (Proc. of International Symposium on Advances in Spatial Databases (SSD) (1999)), 111-132 |
| [30] | Zhang, B.; Trajcevski, G., The tale of (fusing) two uncertainties, (Proceedings of ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2014 (2014)), 521-524 |
| [31] | Bertossi, L., Database Repairing and Consistent Query Answering (2011), Morgan & Claypool Publishers |
| [32] | Arenas, M.; Bertossi, L. E.; Chomicki, J., Consistent query answers in inconsistent databases, (Int. Symposium on Principles of Database Systems (PODS) (1999)), 68-79 |
| [33] | Fazzinga, B.; Flesca, S.; Furfaro, F.; Parisi, F., Offline cleaning of RFID trajectory data, (Int. Conf. on Scientific and Statistical Database Management (SSDBM), vol. 5 (2014)) |
| [35] | Southey, F.; Loh, W.; Wilkinson, D. F., Inferring complex agent motions from partial trajectory observations, (IJCAI (2007)), 2631-2637 |
| [36] | Akdere, M.; Çetintemel, U.; Riondato, M.; Upfal, E.; Zdonik, S. B., The case for predictive database systems: opportunities and challenges, (CIDR (2011)), 167-174 |
| [37] | Agarwal, D.; Chen, D.; Lin, L. J.; Shanmugasundaram, J.; Vee, E., Forecasting high-dimensional data, (SIGMOD Conference (2010)), 1003-1012 |
| [38] | Parisi, F.; Sliva, A.; Subrahmanian, V. S., Embedding forecast operators in databases, (Int. Conf. on Scalable Uncertainty Management (SUM) (2011)), 373-386 |
| [39] | Parisi, F.; Sliva, A.; Subrahmanian, V. S., A temporal database forecasting algebra, Int. J. Approx. Reason., 54, 7, 827-860 (2013) · Zbl 1316.68049 |
| [40] | Papadimitriou, C. M., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049 |
| [41] | Arenas, M.; Bertossi, L. E.; Chomicki, J.; He, X.; Raghavan, V.; Spinrad, J., Scalar aggregation in inconsistent databases, Theor. Comput. Sci., 3, 296, 405-434 (2003) · Zbl 1045.68049 |
| [42] | Arenas, M.; Bertossi, L. E.; Chomicki, J., Answer sets for consistent query answering in inconsistent databases, Theory Pract. Log. Program., 3, 4-5, 393-424 (2003) · Zbl 1079.68026 |
| [43] | Rodríguez, M. A.; Bertossi, L. E.; Marileo, M. C., Consistent query answering under spatial semantic constraints, Inf. Syst., 38, 2, 244-263 (2013) |
| [44] | Lembo, D.; Lenzerini, M.; Rosati, R.; Ruzzi, M.; Savo, D. F., Inconsistency-tolerant semantics for description logics, (Proc. of International Conference on Web Reasoning and Rule Systems (RR) (2010)), 103-117 |
| [45] | Lukasiewicz, T.; Martinez, M. V.; Simari, G. I., Inconsistency handling in Datalog+/- ontologies, (Proceedings of ECAI 2012 (2012)), 558-563 · Zbl 1327.68280 |
| [46] | Zhang, M.; Chen, S.; Jensen, C. S.; Ooi, B. C.; Zhang, Z., Effectively indexing uncertain moving objects for predictive queries, Proc. VLDB Endow., 2, 1, 1198-1209 (2009) |
| [47] | Zheng, K.; Trajcevski, G.; Zhou, X.; Scheuermann, P., Probabilistic range queries for uncertain trajectories on road networks, (EDBT (2011)), 283-294 |
| [48] | Chung, B. S.E.; Lee, W.-C.; Chen, A. L.P., Processing probabilistic spatio-temporal range queries over moving objects with uncertainty, (EDBT (2009)), 60-71 |
| [49] | Yang, B.; Lu, H.; Jensen, C. S., Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space, (EDBT (2010)), 335-346 |
| [50] | Chen, Y.-F.; Qin, X.-L.; Liu, L., Uncertain distance-based range queries over uncertain moving objects, J. Comput. Sci. Technol., 25, 5, 982-998 (2010) |
| [51] | Fuxman, A.; Miller, R. J., First-order query rewriting for inconsistent databases, (ICDT (2005)), 337-351 · Zbl 1112.68367 |
| [52] | Fuxman, A.; Fazli, E.; Miller, R. J., ConQuer: efficient management of inconsistent databases, (SIGMOD Conference (2005)), 155-166 |
| [53] | Wijsen, J., On the consistent rewriting of conjunctive queries under primary key constraints, Inf. Syst., 34, 7, 578-601 (2009) |
| [54] | Wijsen, J., On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases, (PODS (2010)), 179-190 |
| [55] | Calì, A.; Lembo, D.; Rosati, R., On the decidability and complexity of query answering over inconsistent and incomplete databases, (PODS (2003)), 260-271 |
| [56] | Chomicki, J.; Marcinkowski, J., Minimal-change integrity maintenance using tuple deletions, Inf. Comput., 197, 1-2, 90-121 (2005) · Zbl 1075.68022 |
| [57] | Greco, G.; Greco, S.; Zumpano, E., A logical framework for querying and repairing inconsistent databases, IEEE Trans. Knowl. Data Eng., 15, 6, 1389-1408 (2003) |
| [58] | Barceló, P.; Bertossi, L. E., Logic programs for querying inconsistent databases, (PADL, 208-222 (2003)) · Zbl 1026.68761 |
| [59] | Franconi, E.; Palma, A. L.; Leone, N.; Perri, S.; Scarcello, F., Census data repair: a challenging application of disjunctive logic programming, (LPAR (2001)), 561-578 · Zbl 1275.68045 |
| [60] | Bertossi, L. E.; Bravo, L.; Franconi, E.; Lopatenko, A., The complexity and approximation of fixing numerical attributes in databases under integrity constraints, Inf. Syst., 33, 4-5, 407-434 (2008) |
| [61] | Bohannon, P.; Flaster, M.; Fan, W.; Rastogi, R., A cost-based model and effective heuristic for repairing constraints by value modification, (SIGMOD (2005)), 143-154 |
| [62] | Wijsen, J., Database repairing using updates, ACM Trans. Database Syst., 30, 3, 722-768 (2005) |
| [63] | Flesca, S.; Furfaro, F.; Parisi, F., Querying and repairing inconsistent numerical databases, ACM Trans. Database Syst., 35, 2 (2010) |
| [64] | Flesca, S.; Furfaro, F.; Parisi, F., Preferred database repairs under aggregate constraints, (Int. Conf. on Scalable Uncertainty Management (SUM) (2007)), 215-229 |
| [65] | Flesca, S.; Furfaro, F.; Parisi, F., Range-consistent answers of aggregate queries under aggregate constraints, (Int. Conf. on Scalable Uncertainty Manag. (SUM) (2010)), 163-176 |
| [66] | Flesca, S.; Furfaro, F.; Parisi, F., Consistent answers to Boolean aggregate queries under aggregate constraints, (DEXA, vol. 2 (2010)), 285-299 |
| [67] | Kolaitis, P. G.; Pema, E.; Tan, W., Efficient querying of inconsistent databases with binary integer programming, Proc. VLDB Endow., 6, 6, 397-408 (2013) |
| [68] | Greco, S.; Pijcke, F.; Wijsen, J., Certain query answering in partially consistent databases, Proc. VLDB Endow., 7, 5, 353-364 (2014) |
| [69] | Martinez, M. V.; Parisi, F.; Pugliese, A.; Simari, G. I.; Subrahmanian, V. S., Inconsistency management policies, (KR (2008)), 367-377 |
| [70] | Martinez, M. V.; Parisi, F.; Pugliese, A.; Simari, G. I.; Subrahmanian, V. S., Efficient policy-based inconsistency management in relational knowledge bases, (Proc. International Conference on Scalable Uncertainty Management (SUM) (2010)), 264-277 |
| [71] | Martinez, M. V.; Parisi, F.; Pugliese, A.; Simari, G. I.; Subrahmanian, V. S., Policy-based inconsistency management in relational databases, Int. J. Approx. Reason., 55, 2, 501-526 (2014) · Zbl 1316.68046 |
| [72] | Flesca, S.; Furfaro, F.; Parisi, F., Consistency checking and querying in probabilistic databases under integrity constraints, J. Comput. Syst. Sci., 80, 7, 1448-1489 (2014) · Zbl 1311.68053 |
| [73] | Mauder, M.; Reisinger, M.; Emrich, T.; Züfle, A.; Renz, M.; Trajcevski, G.; Tamassia, R., Minimal spatio-temporal database repairs, (Proc. of Advances in Spatial and Temporal Databases Symposium (SSTD) (2015)), 255-273 |
| [74] | Gabelaia, D.; Kontchakov, R.; Kurucz, Á.; Wolter, F.; Zakharyaschev, M., Combining spatial and temporal logics: expressiveness vs. complexity, J. Artif. Intell. Res., 23, 167-243 (2005) · Zbl 1080.68682 |
| [75] | Kontchakov, R.; Kurucz, A.; Wolter, F.; Zakharyaschev, M., Spatial logic + temporal logic = ?, (Handbook of Spatial Logics (2007), Springer), 497-564 |
| [76] | Merz, S.; Wirsing, M.; Zappe, J., A spatio-temporal logic for the specification and refinement of mobile systems, (FASE (2003)), 87-101 · Zbl 1032.03028 |
| [77] | Knapp, A.; Merz, S.; Wirsing, M.; Zappe, J., Specification and refinement of mobile systems in MTLA and mobile UML, Theor. Comput. Sci., 351, 2, 184-202 (2006) · Zbl 1086.68016 |
| [78] | Cohn, A. G.; Hazarika, S. M., Qualitative spatial representation and reasoning: an overview, Fundam. Inform., 46, 1-2, 1-29 (2001) · Zbl 0974.68206 |
| [79] | Renz, J.; Nebel, B., Qualitative spatial reasoning using constraint calculi, (Handbook of Spatial Logics (2007), Springer), 161-215 |
| [80] | Yaman, F.; Nau, D. S.; Subrahmanian, V. S., A logic of motion, (KR (2004)), 85-94 |
| [81] | Yaman, F.; Nau, D.; Subrahmanian, V., A motion closed world assumption, (IJCAI (2005)), 621-626 |
| [82] | Yaman, F.; Nau, D. S.; Subrahmanian, V. S., Going far, logically, (IJCAI (2005)), 615-620 |
| [83] | Parker, A.; Yaman, F.; Nau, D. S.; Subrahmanian, V. S., Probabilistic go theories, (IJCAI (2007)), 501-506 |
| [84] | Parker, A.; Infantes, G.; Subrahmanian, V. S.; Grant, J., An AGM-based belief revision mechanism for probabilistic spatio-temporal logics, (AAAI (2008)), 511-516 |
| [85] | Doder, D.; Grant, J.; Ognjanović, Z., Probabilistic logics for objects located in space and time, J. Log. Comput., 23, 3, 487-515 (2013) · Zbl 1267.03041 |
| [86] | Grant, J.; Parisi, F.; Subrahmanian, V. S., Research in probabilistic spatiotemporal databases: the SPOT framework, (Studies in Fuzziness and Soft Computing. Studies in Fuzziness and Soft Computing, Advances in Probabilistic Databases for Uncertain Information Management, vol. 304 (2013), Springer), 1-22 · Zbl 1269.68025 |
| [87] | Parisi, F.; Grant, J., Integrity constraints for probabilistic spatio-temporal knowledgebases, (Proc. of Int. Conf. on Scalable Uncertainty Management (SUM) (2014)), 251-264 |
| [88] | Parisi, F.; Grant, J., Knowledge representation in probabilistic spatio-temporal knowledge bases, J. Artif. Intell. Res., 55, 743-798 (2016) · Zbl 1352.68234 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
