2026-07-23T19:58:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24458 2026-01-21T10:06:31Z ddc:004 open_access

On the Complexity of the Realisability Problem for Visit Events in Trajectory Sample Databases Jansen, Arthur Kuijpers, Bart Trajectory sample databases uncertain databases query languages complexity Trajectory sample databases store finite sequences of measured space-time locations of moving objects, along with a speed bound for each object. These databases can be seen as uncertain databases. We propose a language that allows the formulation of queries about the uncertainty in trajectory sample databases. As part of that language, we introduce the notion of visit events, which are used to describe certain constraints on the movement of an object. In our language, an atomic query asks whether a moving object can, given its limitations, realise such an event. We give complexity results for this realisability problem, in various settings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arthur Jansen and Bart Kuijpers 2025 Is Part Of LIPIcs, Volume 355, 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2025.12 urn:nbn:de:0030-drops-244586 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode