Enterprise networks are traditionally mapped via layers two or three, providing a view of what devices are connected to different parts of the network infrastructure. A method was developed to map connections at layer four, providing a view of interconnected systems and services instead of network infrastructure. This data was graphed and displayed in a web application. The information proved beneficial in identifying connections between systems or imbalanced clusters when troubleshooting problems with enterprise applications.

Les dépendances fonctionnelles fournissent une information sémantique sur les données d’une table en mettant en lumière les liens de corrélation qui les unient. Dans cette thèse, nous traitons du problème de l’extraction de ces dépendances en proposant un contexte unifié permettant la découverte de n’importe quel type de dépendances fonctionnelles (dépendances de clé, dépendances fonctionnelles conditionnelles, que la validité soit complète ou approximative). Notre algorithme, ParaCoDe, s’exécute en parallèle sur les candidats, réduisant ainsi le temps global de calcul. De ce fait, il est très compétitif vis-à-vis des approches séquentielles connues à ce jour. Les dépendances satisfaites sur une table nous servent à résoudre le problème de la matérialisation partielle du cube de données. Nous présentons une caractérisation de la solution optimale dans laquelle le coût de chaque requête est borné par un seuil de performance fixé préalablement et dont la taille est minimale. Cette spécification de la solution donne un cadre unique pour décrire et donc comparer formellement les techniques de résumé de cubes de données. / Functional dependancies provide a semantic information over data from a table to exhibit correlation links. In this thesis, we deal with the dependancy discovery problem by proposing a unified context to extract any type of functional dependencies (key dependencies, conditional functional dependencies, with an exact or an approximate validity). Our algorithm, ParaCoDe, runs in parallel on candidates there by reducing the global time of computations. Hence, it is very competitive comparated to sequential appoaches known today. Satisfied dependencies on a table are used to solve the problem of partial materiali-zation of data cube. We present a characterization of the optimal solution in which the cost of each query is bounded by a before hand fixed performance threshold and its size is minimal. This specification of the solution gives a unique framework to describe and formally compare summarization techniques of data cubes.

Data integration aims to combine data of different sources and to provide users with a unified view on these data. This task is as challenging as valuable. In this thesis we propose algorithms for dependency discovery to provide necessary information for data integration. We focus on inclusion dependencies (INDs) in general and a special form named conditional inclusion dependencies (CINDs): (i) INDs enable the discovery of structure in a given schema. (ii) INDs and CINDs support the discovery of cross-references or links between schemas. An IND “A in B” simply states that all values of attribute A are included in the set of values of attribute B. We propose an algorithm that discovers all inclusion dependencies in a relational data source. The challenge of this task is the complexity of testing all attribute pairs and further of comparing all of each attribute pair's values. The complexity of existing approaches depends on the number of attribute pairs, while ours depends only on the number of attributes. Thus, our algorithm enables to profile entirely unknown data sources with large schemas by discovering all INDs. Further, we provide an approach to extract foreign keys from the identified INDs. We extend our IND discovery algorithm to also find three special types of INDs: (i) Composite INDs, such as “AB in CD”, (ii) approximate INDs that allow a certain amount of values of A to be not included in B, and (iii) prefix and suffix INDs that represent special cross-references between schemas. Conditional inclusion dependencies are inclusion dependencies with a limited scope defined by conditions over several attributes. Only the matching part of the instance must adhere the dependency. We generalize the definition of CINDs distinguishing covering and completeness conditions and define quality measures for conditions. We propose efficient algorithms that identify covering and completeness conditions conforming to given quality thresholds. The challenge for this task is twofold: (i) Which (and how many) attributes should be used for the conditions? (ii) Which attribute values should be chosen for the conditions? Previous approaches rely on pre-selected condition attributes or can only discover conditions applying to quality thresholds of 100%. Our approaches were motivated by two application domains: data integration in the life sciences and link discovery for linked open data. We show the efficiency and the benefits of our approaches for use cases in these domains. / Datenintegration hat das Ziel, Daten aus unterschiedlichen Quellen zu kombinieren und Nutzern eine einheitliche Sicht auf diese Daten zur Verfügung zu stellen. Diese Aufgabe ist gleichermaßen anspruchsvoll wie wertvoll. In dieser Dissertation werden Algorithmen zum Erkennen von Datenabhängigkeiten vorgestellt, die notwendige Informationen zur Datenintegration liefern. Der Schwerpunkt dieser Arbeit liegt auf Inklusionsabhängigkeiten (inclusion dependency, IND) im Allgemeinen und auf der speziellen Form der Bedingten Inklusionsabhängigkeiten (conditional inclusion dependency, CIND): (i) INDs ermöglichen das Finden von Strukturen in einem gegebenen Schema. (ii) INDs und CINDs unterstützen das Finden von Referenzen zwischen Datenquellen. Eine IND „A in B“ besagt, dass alle Werte des Attributs A in der Menge der Werte des Attributs B enthalten sind. Diese Arbeit liefert einen Algorithmus, der alle INDs in einer relationalen Datenquelle erkennt. Die Herausforderung dieser Aufgabe liegt in der Komplexität alle Attributpaare zu testen und dabei alle Werte dieser Attributpaare zu vergleichen. Die Komplexität bestehender Ansätze ist abhängig von der Anzahl der Attributpaare während der hier vorgestellte Ansatz lediglich von der Anzahl der Attribute abhängt. Damit ermöglicht der vorgestellte Algorithmus unbekannte Datenquellen mit großen Schemata zu untersuchen. Darüber hinaus wird der Algorithmus erweitert, um drei spezielle Formen von INDs zu finden, und ein Ansatz vorgestellt, der Fremdschlüssel aus den erkannten INDs filtert. Bedingte Inklusionsabhängigkeiten (CINDs) sind Inklusionsabhängigkeiten deren Geltungsbereich durch Bedingungen über bestimmten Attributen beschränkt ist. Nur der zutreffende Teil der Instanz muss der Inklusionsabhängigkeit genügen. Die Definition für CINDs wird in der vorliegenden Arbeit generalisiert durch die Unterscheidung von überdeckenden und vollständigen Bedingungen. Ferner werden Qualitätsmaße für Bedingungen definiert. Es werden effiziente Algorithmen vorgestellt, die überdeckende und vollständige Bedingungen mit gegebenen Qualitätsmaßen auffinden. Dabei erfolgt die Auswahl der verwendeten Attribute und Attributkombinationen sowie der Attributwerte automatisch. Bestehende Ansätze beruhen auf einer Vorauswahl von Attributen für die Bedingungen oder erkennen nur Bedingungen mit Schwellwerten von 100% für die Qualitätsmaße. Die Ansätze der vorliegenden Arbeit wurden durch zwei Anwendungsbereiche motiviert: Datenintegration in den Life Sciences und das Erkennen von Links in Linked Open Data. Die Effizienz und der Nutzen der vorgestellten Ansätze werden anhand von Anwendungsfällen in diesen Bereichen aufgezeigt.

Modern-day vehicles consist of numerous electronic computing devices with accompanying software. Since vehicles are generally classified as safety-critical systems, rigorous testing strategies have to be deployed to ensure correct operation of the embedded software. Testing in an active sense is understood to be the main testing method for software in general. The main characteristic of active testing is that test cases have complete control over the system under test, warranting sequential execution of test cases. To complement active testing a method called passive testing is being researched, where the main benefit compared to active testing is that the evaluation of test cases becomes parallelizable. As passive testing opens up for concurrency, the issue of not recognizing faulty behavior arises. This could be the case when simultaneously testing functions which share an output, and the incorrect behavior of a function is being masked by the correct behavior of another function. To avoid vacuous test results, the evaluation of dependent test cases can be separated. Previous work describes the process of extracting dependencies between test cases from requirement specifications. However, this approach is not suitable when test cases are derived from various artifacts. In this thesis we present a syntax-based approach for dependency discovery between test cases. The approach was evaluated through a case study using integration test cases developed for active hardware-in-the-loop testing at Scania CV. Dependencies between 946 test cases have been extracted and the test cases were grouped into three categories, with 286 test cases being identified as independent. The approach shows some potential for evaluating test cases written for active testing, but the results indicate that using test cases written specifically for passive testing may yield better results. The approach also proved to be useful for finding bugs and deviations in scripts. Thus, the method has proven useful for discovering dependencies from syntax, but the results are strongly dependent on the complexity and commonality of the scripts. / Moderna fordon innehåller åtskilliga elektroniska kontrollenheter med medföljande programvara. Eftersom fordon ofta anses vara säkerhetskritiska system krävs robusta teststrategier av den inbyggda mjukvaran för att säkerställa korrekt drift. Aktiv testning är för nuvarande den vanligaste metoden för att testa mjukvara. Den huvudsakliga egenskapen för aktiv testning är att testfall har total kontroll över systemet som är satt under test, vilket medför sekventiell utvärdering av testfall. För att komplettera aktiv testning undersöks en metod som kallas passiv testning, där den största fördelen gentemot aktiv testning är att utvärderingen av testfall kan ske parallellt. Att utvärdera testfall samtidigt medför dock att felaktigt beteende i mjukvaran potentiellt kan maskeras. Detta kan ske då flera funktioner delar utsignaler, och en funktions felaktiga beteende maskeras av en annan funktions korrekta beteende. För att undvika tomma sanningar som testresultat, kan utvärderingen av testfall som har ett beroende mellan dem separeras. Föregående arbeten inom området beskriver processen för att extrahera beroenden mellan testfall från kravspecifikationer. Denna metod är dock inte lämplig när testfall är baserade på flera olika artefakter. I detta examensarbete presenterar vi en syntaxbaserad metod för att hitta beroenden mellan testfall. Metoden utvärderades genom en fallstudie på Scania CV, där aktiva integrationstestfall för hardware-in-the-loop användes för analys. Beroenden mellan 946 testfall kunde extraheras och testfallen grupperades i tre olika kategorier, där 286 klassificerades som oberoende. Metoden visar potential för att analysera testfall skrivna för aktiv testning, men resultaten indikerar att testfall skrivna specifikt för passiv testning kan generera ett bättre resultat. Ett oväntat men positivt utfall är att metoden i viss grad kan användas för att hitta buggar och avvikelser i skript. Således har metoden visats användbar för att hitta beroenden från syntax, men resultatet beror starkt på skriptens komplexitet och gemensamhet.