No description available.

Dans cette thèse nous nous intéressons au problème d’analyse des spécifications des protocoles d’interactions des services Web orientés données. La spécification de ce type de protocoles inclut les données en plus de la signature des opérations et des contraintes d’ordonnancement des messages. L’analyse des services orientés données est complexe car l’exécution d’un service engendre une infinité d’états. Notre travail se concentre autour du problème d’existence d’une relation de simulation quand les spécifications des protocoles des services Web sont représentés en utilisant un système à transition orienté données. D’abord nous avons étudié le modèle Colombo [BCG+05]. Dans ce modèle, un service (i) échange des messages en utilisant des variables ; (ii) modifie une base de donnée partagée ; (iii) son comportement est modélisé avec un système à transition. Nous montrons que tester l’existence de la relation de simulation entre deux services Colombo non bornée est indécidable. Puis, nous considérons le cas où les services sont bornés. Nous montrons pour ce cas que le test de simulation est (i) exptime-complet pour les services Colombo qui n’accèdent pas à la base de donnée (noté ColomboDB=∅), et (ii) 2exptime-complet quand le service peut accéder à une base de donnée bornée (Colombobound). Dans la seconde partie de cette thèse, nous avons défini un modèle générique pour étudier l’impact de différents paramètres sur le test de simulation dans le contexte des services Web orientés données. Le modèle générique est un système à transition gardé qui peut lire et écrire à partir d’une base de donnée et échanger des messages avec son environnement (d’autres services ou un client). Dans le modèle générique toutes les actions sont des requêtes sur des bases de données (modification de la base de données, messages échangés et aussi les gardes). Dans ce contexte, nous avons obtenu les résultats suivant : (i) pour les services gardés sans mise à jour, le test de simulation est caractérisé par rapport à la décidabilité du test de satisfiabilité du langage utilisé pour exprimer les gardes augmenté avec une forme restrictive de négation, (ii) pour les services sans mise à jour mais qui peuvent envoyer comme message le résultat d’une requête, nous avons trouvé des conditions suffisantes d’indécidabilité et de décidabilité par rapport au langage utilisé pour exprimer l’échange de messages, et (iii) nous avons étudié le cas des services qui ne peuvent que insérer des tuples dans la base de donnée. Pour ce cas, nous avons étudié la simulation ainsi que la weak simulation et nous avons montré que : (a) la weak simulation est indécidable quand les requêtes d’insertion sont des requêtes conjonctives, (b) le test de simulation est indécidable si la satisfiabilité du langage de requête utilisé pour exprimer les insertions augmenté avec une certaine forme de négation est indécidable. Enfin, nous avons étudié l’interaction entre le langage utilisé pour exprimer les gardes et celui utilisé pour les insertions, nous exhibons une classe de service où la satisfiabilité des deux langages est décidable alors que le test de simulation entre les services qui leur sont associés ne l’est pas. / In this thesis we address the problem of analyzing specifications of data-centric Web service interaction protocols (also called data-centric business protocols). Specifications of such protocols include data in addition to operation signatures and messages ordering constraints. Analysis of data-centric services is a complex task because of the inherently infinite states of the underlying service execution instances. Our work focuses on characterizing the problem of checking a refinement relation between service interaction protocol specifications. More specifically, we consider the problem of checking the simulation preorder when service business protocols are represented using data-centric state machines. First we study the Colombo model [BCG+05]. In this framework, a service (i) exchanges messages using variables; (ii) acts on a shared database; (iii) has a transition based behavior. We show that the simulation test for unbounded Colombo is undecidable. Then, we consider the case of bounded Colombo where we show that simulation is (i) exptime-complete for Colombo services without any access to the database (noted ColomboDB=∅), and (ii) 2exptime-complete when only bounded databases are considered (the obtained model is noted Colombobound). In the second part of this thesis, we define a generic model to study the impact of various parameters on the simulation test in the context of datacentric services. The generic model is a guarded transition system acting (i.e., read and write) on databases (i.e., local and shared) and exchanging messages with its environment (i.e., other services or users). The model was designed with a database theory perspective, where all actions are viewed as queries (i.e modification of databases, messages exchanges and guards). In this context, we obtain the following results (i) for update free guarded services (i.e., generic services with guards and only able to send empty messages) the decidability of simulation is fully characterized w.r.t decidability of satisfiability of the query language used to express the guards augmented with a restrictive form of negation, (ii) for update free send services (i.e., generic services without guards and able to send as messages the result of queries over local and shared database), we exhibit sufficient conditions for both decidability and undecidability of simulation test w.r.t the language used to compute messages payloads, and (iii) we study the case of insert services (i.e., generic services without guards and with the ability of insert the result of queries into the local and the shared database). In this case, we study the simulation as well as the weak simulation relations where we show that: (i) the weak simulation is undecidable when the insertions are expressed as conjunctive queries, (ii) the simulation is undecidable if satisfiability of the query language used to express the insertion augmented with a restricted form of negation is undecidable. Finally, we study the interaction between the queries used as guards and the ones used as insert where we exhibit a class of services where satisfiability of both languages is decidable while simulation is undecidable.

Formal ontologies are of significant importance in artificial intelligence, playing a central role in the Semantic Web, ontology-based information integration, or peer-to-peer data management. In such scenarios, an especially prominent role is played by description logics (DLs) – a robust family of logical formalisms used to describe ontologies and serving as the logical underpinning of contemporary standardised ontology languages. To put knowledge bases to full use as core part of intelligent information systems, much attention is being devoted to the area of ontology-based data-access, with conjunctive queries and their generalisations such as positive conjunctive two-way regular path queries being employed as a fundamental querying formalism. The most expressive exemplars of description logics feature advanced constructors for roles and path expressions. Among the most powerful knowledge representation formalisms on the verge of decidability, are the DLs from the Z family. For its most expressive proponent, ZOIQ (a.k.a. ALCHbSelf reg OIQ), featuring nominals (O), role inverses (I), and number restrictions (Q), querying is undecidable and even decidability of knowledge-base satisfiability is open, owing to the intricate interplay of the three mentioned features. Restricting the interaction of O, I, and Q however (or excluding one of the features altogether) leads to beneficial model-theoretic properties, which give rise to upper bounds of ExpTime for knowledge-base satisfiability and 2ExpTime for querying. Aiming for better understanding of the “expressive power versus computational complexity” trade-off for the Z family of DLs, we provide a more fine-grained complexity analysis for the query entailment problem over ontologies. In the thesis we focus on tame fragments of ZOIQ, namely the fragments in which either one the three features from {I, O, Q} is dropped or the class of models is restricted to the so-called quasi-forests. We employ the query languages ranging from (unions of) conjunctive queries ((U)CQs) to positive two-way regular path queries (P2RPQs). We mostly follow the classical semantics of entailment, but we also provide several results in the “finite-model” scenario. The most important results of the thesis are summarised below. 1. We provide a complete classification of the complexity of the query entailment problem (for various query languages discussed above) for tamed fragments of ZOIQ under the classical semantics. This involves several new ingredients such as: (i) a uniform exponential-time algorithm based on Lutz’s spoiler technique for the entailment of unions of conjunctive queries for ALCHbreg, (ii) new lower bounds for (rooted and unrooted) conjunctive query entailment over ALCSelf ontologies, and (iii) a novel reduction from the entailment of P2RPQs to the satisfiability problem for tamed ZOIQ, yielding a uniform 2ExpTime upper bound for all the considered logics. As a preliminary step towards lifting the above results to the realm of data complexity, we establish that the satisfiability of tamed ZOIQ is NP-complete. 2. Under the finite model semantics, we focus on UCQs only. With the proviso that the finite satisfiability problem for ZIQ is ExpTime-complete, we also provide a complete picture of the complexity of the query entailment problems. The key insight is that ZOI and ZOQ are finitely controllable. 3. We conclude the thesis by investigating the decidability border of further extensions of the Z family of DLs. Our goal is to understand whether the class of regular languages present in path expressions in Z is maximal for guaranteeing decidability of the underlying logic. We provide a series of undecidability results involving simple, non-regular languages (a subclass of visibly pushdown languages). Our proofs rely on well-established model- and graph-theoretic definitions. What is more, most of them generalise (in a uniform way) and solidify multiple results known by the DL community. Our proofs are also easily adjustable to freshly defined logics, without the need to reproduce nearly-identical proofs.

This research examines the history of a small Florida agricultural community over the course of the twentieth century from a rhetorical perspective in order to understand the technological and communicative transitions that governed the development of American agricultural production. By examining archival and oral histories, this research will add to our understandings of how written and oral communications temper the relationships and social situations of an agricultural community, including the knowledge-making and technological adaptation resulting from communications within the community and with outside institutions and entities. Agricultural villages are not isolated entities, but rather sites of multiple rhetorical situations, and farmers do not farm alone, but inside an ecosystem of networked knowledges, practices, and traditions. Thus, the history of a singular farming community may serve as a rhetorical microcosm of modern American agriculture's evolution over the course of the twentieth century, and provide some mindfulness concerning the social, technological, and natural ecologies that act and interact within modern farming communities. This dissertation will use rhetorical genre theory and ideas of local literacies to examine the written and oral discourses that run through these ecologies for the purpose of tracing the relationships between the sponsors of agricultural ideas and technologies and the local farmers who interpreted, employed, and modified them. In addition, this project purports to add to digital history-making research through the construction of an historical archival website to which community members can add their voices. The Samsula Historical Archive creates an online nexus where community members can document, organize, and preserve the history of the community, offering a portal supporting multiple narratives and perspectives. Each family has its own stories and perspectives on historical happenings; by bringing these together in one databased location, the layers and interconnections will become clearer and perhaps stimulate further memories and insights. A discussion of the rhetorical choices faced in constructing such an artifact may also help future researchers embarking on such a project.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: In this thesis we develop a self-dual categorical approach to some topics in non-abelian algebra, which is based on replacing the framework of a category with that of a category equipped with a functor to it. We also make some first steps towards a possible link between this theory and the theory of databases in computer science. Both of these theories are based around the study of Grothendieck bifibrations and their generalisations. The main results in this thesis concern correspondences between certain structures on a category which are relevant to the study of categories of non-abelian group-like structures, and functors over that category. An investigation of these correspondences leads to a system of dual axioms on a functor, which can be considered as a solution to the proposal of Mac Lane in his 1950 paper "Duality for Groups" that a self-dual setting for formulating and proving results for groups be found. The part of the thesis concerned with the theory of databases is based on a recent approach by Johnson and Rosebrugh to views of databases and the view update problem. / AFRIKAANSE OPSOMMING: In hierdie tesis word ’n self-duale kategoriese benadering tot verskeie onderwerpe in nie-abelse algebra ontwikkel, wat gebaseer is op die vervanging van die raamwerk van ’n kategorie met dié van ’n kategorie saam met ’n funktor tot die kategorie. Ons neem ook enkele eerste stappe in die rigting van ’n skakel tussen hierdie teorie and die teorie van databasisse in rekenaarwetenskap. Beide hierdie teorieë is gebaseer op die studie van Grothendieck bifibrasies en hul veralgemenings. Die hoof resultate in hierdie tesis het betrekking tot ooreenkomste tussen sekere strukture op ’n kategorie wat relevant tot die studie van nie-abelse groep-agtige strukture is, en funktore oor daardie kategorie. ’n Verdere ondersoek van hierdie ooreemkomste lei tot ’n sisteem van duale aksiomas op ’n funktor, wat beskou kan word as ’n oplossing tot die voorstel van Mac Lane in sy 1950 artikel “Duality for Groups” dat ’n self-duale konteks gevind word waarin resultate vir groepe geformuleer en bewys kan word. Die deel van hierdie tesis wat met die teorie van databasisse te doen het is gebaseer op ’n onlangse benadering deur Johnson en Rosebrugh tot aansigte van databasisse en die opdatering van hierdie aansigte.

Near real-time event streams are a key feature in many popular social media applications. These types of applications allow users to selectively follow event streams to receive a curated list of real-time events from various sources. Due to the emphasis on recency, relevance, personalization of content, and the highly variable cardinality of social subgraphs, it is extremely difficult to implement feed following at the scale of major social media applications. This leads to multiple architectural approaches, but no consensus has been reached as to what is considered to be an idiomatic solution. As of today, there are various theoretical approaches exploiting the dynamic nature of social graphs, but not all of them have been applied in practice. In this paper, large-cardinality graphs are placed in the context of existing research to highlight the exceptional data management challenges that are posed for large-scale real-time social media applications. This work outlines the key characteristics of data dissemination in large-cardinality social graphs, and overviews existing research and state-of-the-art approaches in industry, with the goal of stimulating further research in this direction.

<p>This paper describes the evolutionary development of an information system for a small company. The company performs overhaul of forklifts and cleaning machines. The company has already an information system that handles the reports from these overhauls but it needs a supplementary tool that assist the chief planner to plan forthcoming overhauls.</p><p>It should be able to display coming overhauls in a timetable and eventually print them, either to a PDF file or to a document. The timetables this function produces will help the chief planner and the assemblers to get a good overview of their day-to-day work.</p><p>The tool needs to be intelligent in that way that it takes into consideration were in the country different assignments will be performed. So that time consuming travels over great distances can be avoided. This coordination will lead to higher profitability for the company and more satisfied customers.</p><p>The paper contains theoretic background about what models and methods that are used in the development of an information system. This theoretic background is then used when developing a system in practise and the result of this is then showed. In the end the results are compared to the demands, goals and requirements stated in the beginning of the paper, to see if they are fulfilled.</p><p>This is a degree thesis at the S c ho o l o f E n gineering, Jö nkö pin g U niversity. It’s a part of the programme: Communication and Information Technology, and are mainly based on knowledge from the following courses: Programming Methods, Database Systems and Trends, Software Engineering Methods and Systems Analysis and Design with a Concept of Quality.</p> / <p>Det här examensarbetet beskriver vidareutvecklandet av ett befintligt informationssystem som hanterar servicerapporter på truckar och städmaskiner. Det befintliga systemet har behov av att kompletteras med ett verktyg som skall kunna lägga till kommande service, visa dessa i ett schema och sedan skriver ut denna planering som scheman i en PDF-fil och/eller på papper. Dessa scheman är till för att chef och de montörer som utför arbetet ska få en bra överblick över vad för arbete som skall göras under en vecka. Verktyget behöver vara smart så till vida att det måste veta var någonstans i landet montörer arbetar för att tidsförlust på grund av resor över stora geografiska avstånd minimeras. Effekten av införandet av verktyget är bättre lönsamhet för företaget och bättre kundrelationer.</p><p>Examensarbetet kommer att innehålla teoretisk bakgrund om vilka metoder som används i alla steg i ett informationssystems utveckling och hur de sedan kan kopplas till det praktiska arbetet. Den teoretiska bakgrunden kommer att användas i praktiken och resultatet blir ett fungerande informationssystem. Resultatet av utvecklingen av systemet kommer att relateras till de syften, mål och krav som anges i början av rapporten för att se om målen med rapporten uppnås.</p><p>Arbetet fokuserar på det praktiska arbete det innebär att utveckla ett informationssystem för ett mindre företag.</p><p>Examensarbetet skrivs vid IIngee njjörrsshögsskollaan, Högskolan i Jönköping och är en del av programmet Datateknik: Kommunikation och Informationskunskap. Arbetet bygger på kunskap främst från kurserna Programmeringsmetoder, Databas Internet, Systemutveckling, Teknisk information och Informationssystems användbarhet.</p>

This paper describes the evolutionary development of an information system for a small company. The company performs overhaul of forklifts and cleaning machines. The company has already an information system that handles the reports from these overhauls but it needs a supplementary tool that assist the chief planner to plan forthcoming overhauls. It should be able to display coming overhauls in a timetable and eventually print them, either to a PDF file or to a document. The timetables this function produces will help the chief planner and the assemblers to get a good overview of their day-to-day work. The tool needs to be intelligent in that way that it takes into consideration were in the country different assignments will be performed. So that time consuming travels over great distances can be avoided. This coordination will lead to higher profitability for the company and more satisfied customers. The paper contains theoretic background about what models and methods that are used in the development of an information system. This theoretic background is then used when developing a system in practise and the result of this is then showed. In the end the results are compared to the demands, goals and requirements stated in the beginning of the paper, to see if they are fulfilled. This is a degree thesis at the S c ho o l o f E n gineering, Jö nkö pin g U niversity. It’s a part of the programme: Communication and Information Technology, and are mainly based on knowledge from the following courses: Programming Methods, Database Systems and Trends, Software Engineering Methods and Systems Analysis and Design with a Concept of Quality. / Det här examensarbetet beskriver vidareutvecklandet av ett befintligt informationssystem som hanterar servicerapporter på truckar och städmaskiner. Det befintliga systemet har behov av att kompletteras med ett verktyg som skall kunna lägga till kommande service, visa dessa i ett schema och sedan skriver ut denna planering som scheman i en PDF-fil och/eller på papper. Dessa scheman är till för att chef och de montörer som utför arbetet ska få en bra överblick över vad för arbete som skall göras under en vecka. Verktyget behöver vara smart så till vida att det måste veta var någonstans i landet montörer arbetar för att tidsförlust på grund av resor över stora geografiska avstånd minimeras. Effekten av införandet av verktyget är bättre lönsamhet för företaget och bättre kundrelationer. Examensarbetet kommer att innehålla teoretisk bakgrund om vilka metoder som används i alla steg i ett informationssystems utveckling och hur de sedan kan kopplas till det praktiska arbetet. Den teoretiska bakgrunden kommer att användas i praktiken och resultatet blir ett fungerande informationssystem. Resultatet av utvecklingen av systemet kommer att relateras till de syften, mål och krav som anges i början av rapporten för att se om målen med rapporten uppnås. Arbetet fokuserar på det praktiska arbete det innebär att utveckla ett informationssystem för ett mindre företag. Examensarbetet skrivs vid IIngee njjörrsshögsskollaan, Högskolan i Jönköping och är en del av programmet Datateknik: Kommunikation och Informationskunskap. Arbetet bygger på kunskap främst från kurserna Programmeringsmetoder, Databas Internet, Systemutveckling, Teknisk information och Informationssystems användbarhet.

With the amount of data in current data warehouse databases growing steadily, random sampling is continuously gaining in importance. In particular, interactive analyses of large datasets can greatly benefit from the significantly shorter response times of approximate query processing. Typically, those analytical queries partition the data into groups and aggregate the values within the groups. Further, with the commonly used roll-up and drill-down operations a broad range of group-by queries is posed to the system, which makes the construction of highly-specialized synopses difficult. In this paper, we propose a general-purpose sampling scheme that is biased in order to answer group-by queries with high accuracy. While existing techniques focus on the size of the group when computing its sample size, our technique is based on its standard deviation. The basic idea is that the more homogeneous a group is, the less representatives are required in order to give a good estimate. With an extensive set of experiments, we show that our approach reduces both the estimation error and the construction cost compared to existing techniques.

This dissertation concerns the development of the MicroWave Radiometer (MWR) brightness temperature (Tb) algorithm and the associated algorithm validation using on-orbit MWR Tb measurements. This research is sponsored by the NASA Earth Sciences Aquarius Mission, a joint international science mission, between NASA and the Argentine Space Agency (Comision Nacional de Actividades Espaciales, CONAE). The MWR is a CONAE developed passive microwave instrument operating at 23.8 GHz (K-band) H-pol and 36.5 GHz (Ka-band) H- and V-pol designed to complement the Aquarius L-band radiometer/scatterometer, which is the prime sensor for measuring sea surface salinity (SSS). MWR measures the Earth's brightness temperature and retrieves simultaneous, spatially collocated, environmental measurements (surface wind speed, rain rate, water vapor, and sea ice concentration) to assist in the measurement of SSS. This dissertation research addressed several areas including development of: 1) a signal processing procedure for determining and correcting radiometer system non-linearity; 2) an empirical method to retrieve switch matrix loss coefficients during thermal-vacuum (T/V) radiometric calibration test; and 3) an antenna pattern correction (APC) algorithm using Inter-satellite radiometric cross-calibration of MWR with the WindSat satellite radiometer. The validation of the MWR counts-to-Tb algorithm was performed using two years of on-orbit data, which included special deep space calibration measurements and routine clear sky ocean/land measurements.