Langages de requêtes temporels, extraction de connaissances temporelles et application aux flux de données
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
A temporal database can be seen as a finite sequence of classical relational databases. Within this framework, we first consider an open problem concerning the relative expressive power of some known temporal query languages: mu-TL (Vardi, 1988) on the one hand, and T-FIXPOINT and T-WHILE (Abiteboul et al. , 1999) on the other hand. We prove that these languages are equivalent over most temporal databases. On the basis that known temporal query languages do not allow to extract temporal information, we then introduce and define query languages able to extract such information, and we analyse their properties. Finally, we consider data streams. In the literature, two paradigms have been introduced to continuously query streams: the single-data approach and the window approach. We formalize both paradigms by the way of Turing-like state machines, and we show that the machines have the same expressive power, under some hypothesis.
Abstract FR:
Une base de données temporelle est vue comme une suite finie de bases de données relationnelles classiques. Dans ce cadre, nous considérons tout d'abord un problème ouvert concernant l'expressivité relative de langages de requêtes temporels connus : le langage mu-TL d'une part (Vardi, 1988), et les langages T-FIXPOINT et T-WHILE d'autre part (Abiteboul et al. , 1999). Nous montrons que ces langages sont équivalents pour la majorité des bases de données temporelles. Nous partons ensuite du constat que les langages temporels connus ne permettent pas d'extraire des informations qui sont elles-mêmes temporelles. Nous proposons des langages qui réalisent cette extraction, et nous en analysons les propriétés. Enfin, nous considérons le traitement des flux de données. Dans la littérature, deux paradigmes ont été introduit pour poser des requêtes continues sur les flux : les approches mono-données et les approches avec fenêtre. Nous formalisons ces deux paradigmes par des machines à états inspirées de la machine de Turing, et nous montrons que ces machines ont la même expressivité relative, sous certaines hypothèses