This thesis investigates the practical aspects of implementing Query Containment algorithms for the query language XPath. Query Containment is the problem to decide if the results of one query are a subset of the results of another query for any database. Query Containment algorithms can be used for the purpose of optimising the querying process in database systems. Two algorithms have been implemented and compared, The Canonical Model and The Homomorphism Technique. The algorithms have been compared with respect to speed, ease of implementation, accuracy and usability in database systems. Benchmark tests were developed to measure the execution times of the algorithms on a specific set of queries. A simple database system was developed to investigate the performance gain of using the algorithms. It was concluded that The Homomorphism Technique outperforms The Canonical Model in every test case with respect to speed. The Canonical Model is however more accurate than The Homomorphism Technique. Both algorithms were easy to implement, but The Homomorphism Technique was easier. In the database system, there was performance to be gained by using Query Containment algorithms for a certain type of queries, but in most cases there was a performance loss. A database system that utilises Query Containment algorithms for optimisation would for every issued query have to evaluate if such an algorithm should be used. / Denna rapport undersöker de praktiska aspekterna av att implementera Query Containment-algoritmer för queryspråket XPath. Query Containment är problemet att avgöra om resultaten av en query är en delmängd av resultaten av en annan query, oavsett databas. Query Containment-algoritmer kan användas för ändamålet att optimera queryingprocessen i databassystem. Två algoritmer har implementerats och jämförts, The Canonical Model och The Homomorphism Technique. Algoritmerna har jämförts med avseende på hastighet, lätthet att implementera, exakthet och användbarhet i riktiga databassystem. Prestandatester utvecklades för att mäta exekveringstider för algoritmerna på specifikt framtagna queries. Ett enkelt databassystem utvecklades för att undersöka prestandavinsten av att använda algoritmerna. Slutsatsen att The Homomorphism Technique presterar bättre än The Canonical Model i samtliga testfall med avseende på hastighet drogs. The Canonical Model är dock mer exakt än The Homomorphism Technique. Båda algoritmerna var lätta att implementera, men The Homomorphism Technique var lättare. I databassystemet fanns det en prestandavinst i att använda Query Containment-algoritmer för en viss typ av queries, men i de flesta fall var det en prestandaförlust. Ett databassystem som använder Query Containment-algoritmer för optimering bör för varje query avgöra om en sådan algoritm ska användas.

One of the difficulties of human figure tracking is that humans move their bodies in complex, non-linear ways. An effective computational model of human motion could therefore be of great benefit in figure tracking. We are interested in the use of a class of dynamic models called switching linear dynamic systems for figure tracking. This thesis makes two contributions. First, we present an empirical analysis of some of the technical issues involved with applying linear dynamic systems to figure tracking. The lack of high-level theory in this area makes this type of empirical study valuable and necessary. We show that sensitivity of these models to perturbations in input is a central issue in their application to figure tracking. We also compare different types of LDS models and identification algorithms. Second, we describe 2-DAFT, a flexible software framework we have created for figure tracking. 2-DAFT encapsulates data and code involved in different parts of the tracking problem in a number of modules. This architecture leads to flexibility and makes it easy to implement new tracking algorithms.

Rough Description Logics have recently been studied as a means for representing and reasoning with imprecise knowledge. Real-world applications need to exploit reasoning over such knowledge in an efficient way. We describe how the combined approach to query answering can be extended to the rough setting. In particular, we extend both the canonical model and the rewriting procedure such that rough queries over rough EL ontologies can be answered by considering this information alone.

Ontology-based query answering augments classical query answering in databases by adopting the open-world assumption and by including domain knowledge provided by an ontology. We investigate temporal query answering w.r.t. ontologies formulated in DL-Lite, a family of description logics that captures the conceptual features of relational databases and was tailored for efficient query answering. We consider a recently proposed temporal query language that combines conjunctive queries with the operators of propositional linear temporal logic (LTL). In particular, we consider negation in the ontology and query language, and study both data and combined complexity of query entailment.

Cette thèse analyse le rôle de l’apprentissage dans deux cadres de modélisation distincts. Dans le cas dunouveau modèle canonique avec apprentissage adaptatif, les caractéristiques les plus marquantes des dynamiquesd’apprentissage concernent la capacité des règles de politique monétaire à assurer la convergencevers l’équilibre en anticipations rationnelles. Le mécanisme de transmission de la politique monétaire estcelui de l’effet de substitution associé au canal de la consommation. Dans le cas d’un modèle multi-agentsqui relâche des hypothèses restrictives du nouveau modèle canonique, tout en restant structurellementproche de celui-ci, les variables agrégées évoluent à bonne distance de cet équilibre, et on observe desdynamiques nettement différentes. La politique monétaire influence les variables agrégées de manièremarginale via l’effet de revenu du canal de la consommation. En présence d’un processus d’apprentissagesocial évolutionnaire, l’économie converge vers un faible niveau d’activité économique. L’introductiond’un processus caractérisé par le fait que les agents apprennent individuellement à l’aide de leurs modèlesmentaux atténue le caractère dépressif des dynamiques d’apprentissage. Ces différences entre les deuxcadres de modélisation démontrent la difficulté de généraliser les résultats du nouveau modèle canonique. / This thesis analyses the role of learning in two different modelling frameworks. In the new canonicalmodel with adaptive learning, the most remarkable characteristics of the learning dynamics deal withthe capacity of monetary policy rules to guaranty convergence to the rational expectations equilibrium.The transmission mechanism of the monetary policy is based on the substitution effect associated to theconsumption channel. In the case of an agent-based model which relaxes some restrictive assumptionsof the new canonical model - but is endowed with a similar structure - aggregate variables evolve atsome distance from the rational expectations equilibrium. Monetary policy has a marginal impact onthe agregated variables via the wealth effect of the consumption channel. When agents learn accordingto an evolutionnary social learning process, the economy converges to regions of low economic activity.The introduction of a process where agents learn individually by using their mental models induces lessdepressive learning dynamics. These differences between the two modelling frameworks show that thegeneralisation of the results of the new canonical model is not easy to achieve.