Informatik
Refine
Year of publication
Document Type
- Preprint (759)
- Article (402)
- Working Paper (119)
- Doctoral Thesis (93)
- Diploma Thesis (47)
- Conference Proceeding (41)
- Book (37)
- Bachelor Thesis (36)
- diplomthesis (28)
- Report (25)
Has Fulltext
- yes (1619)
Is part of the Bibliography
- no (1619)
Keywords
Institute
- Informatik (1619)
- Frankfurt Institute for Advanced Studies (FIAS) (1008)
- Physik (986)
- Mathematik (56)
- Präsidium (41)
- Medizin (25)
- Biowissenschaften (21)
- Exzellenzcluster Makromolekulare Komplexe (8)
- Psychologie (8)
- Deutsches Institut für Internationale Pädagogische Forschung (DIPF) (5)
- Geowissenschaften (5)
- Senckenbergische Naturforschende Gesellschaft (5)
- Biochemie und Chemie (4)
- Geographie (4)
- Hochschulrechenzentrum (4)
- Pharmazie (4)
- Goethe-Zentrum für Wissenschaftliches Rechnen (G-CSC) (3)
- Universitätsbibliothek (3)
- Biodiversität und Klima Forschungszentrum (BiK-F) (2)
- Center for Membrane Proteomics (CMP) (2)
- Institut für Ökologie, Evolution und Diversität (2)
- Sportwissenschaften (2)
- Wirtschaftswissenschaften (2)
- Center for Scientific Computing (CSC) (1)
- E-Finance Lab e.V. (1)
- Erziehungswissenschaften (1)
- Geschichtswissenschaften (1)
- Gesellschaftswissenschaften (1)
- Informatik und Mathematik (1)
- Institut für Bienenkunde (1)
- Kulturwissenschaften (1)
- MPI für Biophysik (1)
- Neuere Philologien (1)
- Zentrum für Arzneimittelforschung, Entwicklung und Sicherheit (ZAFES) (1)
- Zentrum für Weiterbildung (1)
Retiming is a widely investigated technique for performance optimization. In general, it performs extensive modifications on a circuit netlist, leaving it unclear, whether the achieved performance improvement will still be valid after placement has been performed. This paper presents an approach for integrating retiming into a timing-driven placement environment. The experimental results show the benefit of the proposed approach on circuit performance in comparison with design flows using retiming only as a pre- or postplacement optimization method.
One of the most severe short-comings of currently available equivalence checkers is their inability to verify integer multipliers. In this paper, we present a bit level reverse-engineering technique that can be integrated into standard equivalence checking flows. We propose a Boolean mapping algorithm that extracts a network of half adders from the gate netlist of an addition circuit. Once the arithmetic bit level representation of the circuit is obtained, equivalence checking can be performed using simple arithmetic operations. Experimental results show the promise of our approach.
Syntactic coindexing restrictions are by now known to be of central importance to practical anaphor resolution approaches. Since, in particular due to structural ambiguity, the assumption of the availability of a unique syntactic reading proves to be unrealistic, robust anaphor resolution relies on techniques to overcome this deficiency.
This paper describes the ROSANA approach, which generalizes the verification of coindexing restrictions in order to make it applicable to the deficient syntactic descriptions that are provided by a robust state-of-the-art parser. By a formal evaluation on two corpora that differ with respect to text genre and domain, it is shown that ROSANA achieves high-quality robust coreference resolution. Moreover, by an in-depth analysis, it is proven that the robust implementation of syntactic disjoint reference is nearly optimal. The study reveals that, compared with approaches that rely on shallow preprocessing, the largely nonheuristic disjoint reference algorithmization opens up the possibility/or a slight improvement. Furthermore, it is shown that more significant gains are to be expected elsewhere, particularly from a text-genre-specific choice of preference strategies.
The performance study of the ROSANA system crucially rests on an enhanced evaluation methodology for coreference resolution systems, the development of which constitutes the second major contribution o/the paper. As a supplement to the model-theoretic scoring scheme that was developed for the Message Understanding Conference (MUC) evaluations, additional evaluation measures are defined that, on one hand, support the developer of anaphor resolution systems, and, on the other hand, shed light on application aspects of pronoun interpretation.
In contrast to the symbolic approach, neural networks seldom are designed to explain what they have learned. This is a major obstacle for its use in everyday life. With the appearance of neuro-fuzzy systems which use vague, human-like categories the situation has changed. Based on the well-known mechanisms of learning for RBF networks, a special neuro-fuzzy interface is proposed in this paper. It is especially useful in medical applications, using the notation and habits of physicians and other medically trained people. As an example, a liver disease diagnosis system is presented.
Wir haben Interaktion in der Kommunikationskomplexität untersucht und dabei die drei Modi probabilistische, (beschränkt) nichtdeterministische und quantenmechanische Kommunikation betrachtet. Bei allen drei Modi haben wir herausgefunden, dass Interaktion für Effzienz oft unerlässlich ist, im nichtdeterministischen Fall gibt es eine Abhängigkeit zwischen dem Einfluss der Interaktion und der erlaubten Anzahl der nichtdeterministischen Ratebits. Abgesehen von dem erreichten besseren Verständnis des Kommunikationsmodells haben wir verschiedene Anwendungen auf andere Berechnungsmodelle beschrieben, bei denen untere Schranken der Kommunikation zu unteren Schranken für andere Ressourcen in diesen Modellen geführt haben. Ein Beispiel eines kommunikations- und interaktionsbeschränkten Modells sind endliche Automaten, welche wir in allen drei Modi untersucht haben. Ein weiteres Beispiel sind Formeln, für die wir eine Verbindung zwischen Einweg Kommunikation und Formellänge herstellen konnten. Diese Verbindung führte zu unteren Schranken für probabilistische, nichtdeterministische und Quanten Formeln. Dabei sind die unteren Schranken für Quanten Formeln und probabilistische Formeln im wesentlichen gleich. Für monotone Schaltkreise haben wir gezeigt, wie nichtdeterministisches Raten die Tiefe drastisch reduzieren kann, und wie eine geringfügige Einschränkung der nichtdeterministischen Ratebits zu einer Tiefenhierarchie führt. Insgesamt lässt sich feststellen, dass die Schwäche interaktionsbeschränkter Kommunikation mathematisch nachvollziehbar ist. Außerdem scheint ein solches Verhalten in der Welt einfacher Berechnungsmodelle häufig aufzutreten. Oder anders gesagt, viele Berechnungsmodelle sind deshalb einfacher zu verstehen, weil sie durch interaktionsbeschränkte Kommunikation analysierbar sind.
Schemaevolution in objektorientierten Datenbanksystemen auf der Basis von Versionierungskonzepten
(2000)
Gegenstand dieses Kapitels ist zunächst die Zusammenfassung der in dieser Arbeit erreichten Ergebnisse im Hinblick auf die ursprüngliche Zielsetzung, also die Unterstützung von Schema evolution in objektorientierten Datenbanksystemen. Anschließend folgen Überlegungen, welche der erzielten Ergebnisse zur Lösung von Problemen in anderen Arbeitsbereichen herangezogen werden können und auf welche Weise dies geschehen kann. Die Arbeit schlie?t mit einem Ausblick auf weitere Arbeiten im von uns bearbeiteten Themengebiet. Erreichte Ziele Ausgangspunkt unserer Arbeit war die Beobachtung, dass die Evolution von Datenbankschema ta, welche zur Anpassung an sich ändernde funktionale und nichtfunktionale Anforderungen 130 der Diskurswelt benötigt wird, durch die gegenwärtig verfügbaren Modelle und Systeme nicht adäquat unterstützt wird. Wir stellten daraufhin die Hypothese auf, dass ein Modell auf der Basis der Versionierung von Schemata mit einer entsprechenden Abbildung der Änderungen auf die Objektebene dies leisten kann. Wir konnten in dieser Abhandlung zeigen, dass das nach diesen Gesichtspunkten entworfene COASTModell die daran gestellten Erwartungen erfüllt und Sche maänderungen in Gegenwart existierender Objekte und Applikationen erfolgreich realisierbar sind. Die einzelnen Arbeitsschritte und Ergebnisse ergaben sich dabei wie folgt: - Problemanalyse und grober Modellentwurf: Die Notwendigkeit einer Unterstützung für Schemaevolutionsprozesse ergab sich aus der Beobachtung, dass vor allem moderne An wendungsbereiche eine flexible Anpassung an ständig veränderliche Umstände erfordern. Während des Betriebs einer Datenbank aufkommende Änderungsanforderungen lassen sich zur Entwurfszeit nicht vorhersehen und sind im Rahmen fest vorgegebener Datenbanksche mata nur schwerlich adäquat umsetzbar. Wir konnten in diesem Zusammenhang bei den vorhandenen Systemen zur Unterstützung der Schemaevolution das Fehlen einer Berück sichtigung im Betrieb beøndlicher Datenbankapplikationen feststellen. Gleichzeitig blieben Anforderungen an flexibel koppelbare Datenbankzustände für verschiedene Schemaausprä gungen bisher unberücksichtigt. Das an dieser Stelle grob skizzierte Modell zur Lösung des Problems beruhte folgerichtig auf dem Einsatz von Versionierungskonzepten auf der Ebene der Datenbankschemata. Solche Versionierungskonzepte hatten ihre Fähigkeiten zur Unterstützung von Evolutionsprozessen insbesondere auch im Zusammenhang mit Entwurfsaufgaben bereits zuvor sowohl auf der Ebene kompletter Datenbanken als auch auf der einzelner Objekte nachgewiesen. - Untersuchung bestehender Lösungsansätze: Wir konnten für das Lösungsmodell vier ele mentare Aspekte identiøzieren: Durchführung von Änderungen auf Schemaebene unter Verwendung von Versionierungskonzepten, Erzeugung und Verwaltung der Abhängigkeits beziehungen zwischen den Schemaversionen, Abbildung der Änderungen auf die Objekt ebene sowie flexible Konzepte zur Steuerung und Durchführung der Objektpropagation. Da kein Modell existierte, das all diese Punkte berücksichtigt, mussten wir uns in der Literatur recherche auf Ansätze beschränken, die sich mit einzelnen Aspekten unserer Aufgabenstel lung befassen. Aus dieser Perspektive stellt sich unser Modell zu einem Teil als Integration früherer Arbeiten dar. Zum anderen Teil beruht unser Modell in den grundlegenden Aspek ten der Behandlung von Ableitungsbeziehungen sowie der Steuerung und Durchführung der Objektpropagation auf gänzlich neuen Ansätzen. Die wesentliche Erkenntnis dieses Arbeitsschrittes ist somit die Feststellung, dass einerseits verschiedene Konzepte bestehen der Ansätze übernommen werden konnten, obwohl keine Arbeit alle Anforderungen an unser Modell erfüllte, und andererseits einige Aspekte bislang nahezu vollständig ignoriert wurden. - Detaillierte Modellbildung: Aufgrund der Erkenntnisse über bestehende Arbeiten entwarfen wir in diesem Arbeitsschritt COAST als Modell zur Durchführung von Schemaänderun gen in Anwesenheit von Objekten und Applikationen. Grundbestandteile unseres Ansatzes sind die Schemaversionen, die vergleichbar einer Konøgurationsverwaltung semantisch in Zusammenhang stehende Klassenversionen zu konsistenten Teilstrukturen zusammenset zen. Für die Durchführung von Schemaänderungen haben wir zwei grundsätzlich verschiedene Wege analysiert und resultierende Konsequenzen studiert. Dem internen Ansatz folgend wird eine von dem jeweiligen Einsatzgebiet des Systems unabhängige, fest vorgegebene und konzeptionell vollständige Taxonomie von Schemaänderungsprimitiven bereitgestellt, de ren Semantik a priori bekannt ist und demzufolge bei allen weiteren Schritten auf Schema und Objektebene berücksichtigt werden kann. Der externe Ansatz, als Alternative, erlaubt die Durchführung applikationsspezifischer Schemaänderungen und erhöht damit die Flexi bilität. Der Prozess des Einbringens extern erstellter Schemaversionen in das System kann dabei in vielfältiger Weise unterstützt werden. Bemerkenswerterweise fanden sich die auf Schemaebene angewandten Konzepte analog auf Instanzenebene wieder und zwar bei den Objektversionen, deren Zusammenhang sich in Form von Propagationsgraphen widerspiegelt ähnlich den Ableitungsbeziehungen auf Sche maebene. Die Steuerung der Objektpropagation sowohl zum Zeitpunkt der Schemaände rung als auch später, als Reaktion auf verändernde Datenbankzugrioee ist im behandelten Umfeld mit Sicherheit einzigartig. - Validierung des Modells: Aussagen zur Tauglichkeit des Modells im Hinblick auf seine Kon zeptionsziele konnten wir durch eine Evaluierung anhand unserer sehr detailliert beschrie benen Vorgaben erhalten. Damit ist gleichzeitig ein Vergleich mit bisherigen Lösungswegen insgesamt und mit einzelnen Vertretern davon gegeben. Die Evaluierung konnte in allen Aspekten belegen, dass das COASTModell zur Unterstützung von Schemaänderungen in Benutzung befindlicher Datenbanksysteme gut geeignet ist. Wir möchten an dieser Stelle nochmals betonen, dass COAST in vielerlei Hinsicht einfach erweitert werden kann und im Vergleich zu bisherigen Systemen durch erheblich flexiblere Möglichkeiten der Einflussnahme und eine verbesserte Tauglichkeit ausgezeichnet wird. Zu nächst sind sowohl die hier vorgestellte Schemaänderungstaxonomie als auch die damit ver bundene Propagationssprache vielfältig um komplexe Operationen erweiterbar. Weiterhin kann die Menge verwendbarer Propagationsflags insbesondere mit Blick auf das Verhalten bei komplexen Schemaänderungen hin ergänzt werden. Aber bereits die hier dargestell ten Möglichkeiten der Propagationssteuerung decken das gesamte Spektrum von isolierten Schemaversionen am einen Ende bis hin zur kompletten Propagation am anderen Ende ab. In Erweiterung der Konzepte auf der Basis von Sichtenmechanismen können durch die Objektversionierung beliebige Änderungen des Datenbankzustandes durchgeführt wer den. Damit wird ein erheblicher Beitrag für die Transparenz der Schemaevolution für die Applikationsentwickler geleistet. Die für die Tauglichkeit wichtigste Eigenschaft besteht zweifelsfrei in der Möglichkeit, be stehende Applikationen auch noch nach der Durchführung von Schemaänderungen ohne Anpassung weiterverwenden zu können. Damit erweitert sich der Einsatzbereich von Sche maänderungen auf sehr große, komponentenbasierte Systeme auf der Basis zahlreicher Einzelapplikationen. - Hinweise für den Datenbankentwurf: Um den Schemaversionierungmechanismus adäquat einsetzen zu können, erweisen sich Aussagen über den Schemaänderungsprozess als notwen dig. Daher haben wir diesen Prozess systematisch in Teilschritte zerlegt, die nacheinander betrachtet werden können. Bereits während der Modellbildung haben wir dort, wo sich ei nem Schemaentwickler Alternativen im Umgang mit COAST bieten, diese aufgezeigt und ihre jeweiligen Konsequenzen untersucht. Im Ergebnis resultiert für den Schemaentwick ler im Vergleich zu unversionierten Systemen ein zusätzlicher Spezifikationsaufwand. Dies ist jedoch für die Erreichung unserer Ziele unvermeidbar und der Gesamtaufwand für die Durchführung einer Schemaänderung reduziert sich dem Versionierungskonzept folgend er heblich, nicht zuletzt, weil aus der Sicht der Applikationsentwickler die volle Transparenz gewährleistet wird. - Realisierungsbetrachtungen: Um Erkenntnisse über den Realisierungsaufwand sowie die zu erwartenden Leistungsmerkmale zu erhalten, haben wir zweierlei Ansätze für eine pro totypische Realisierung untersucht. Zum einen haben wir einen Schemaversionierungsme chanismus als Aufsatz auf dem kommerziellen Objektdatenbanksystem O 2 implementiert. Auch wenn sich dies konzeptionell als möglich erwiesen hat, so haben sich dort an mehre ren Stellen erhebliche Einbußen bezüglich der Transparenz gezeigt [Wöh96]. Daher haben wir uns verstärkt mit dem zweiten, deutlich aufwendigeren Weg beschäftigt: die Eigenent wicklung eines kompletten, objektorientierten Datenbankmanagementsystems, bei dem die Konzepte von COAST transparent und von Anfang an im Kern integriert werden konnten. Die Realisierung der verzögerten Propagation kann bei realistischen Zugriffsprofilen mit einer gewissen Lokalität bezüglich der Schemaversionen größenordnungsmäßig mit unver sionierten Systemen vergleichbare Laufzeiten erreichen. Konzeptionell bedingt muss zwar ein größerer Platzbedarf als bei einem statischen System (ohne Schemaänderungen) in Kauf genommen werden. Im Vergleich zu anderen Konzepten der Schemaevolution, etwa den Ansätzen auf der Basis von isolierten Datenbanken oder mit materialisierten Sichten tritt aber kein Mehraufwand auf. In all diesen Varianten wird, ähnlich wie bei Puffern absichtlich Platz zugunsten einer erhöhten Zugriffsgeschwindigkeit investiert. Je ähnlicher sich verschiedene Schemaversionen sind und je intensiver die Propagation zwischen ihnen demnach ausfällt, desto besser sind die Voraussetzungen für platzsparende Mechanismen auf der Basis von mehreren Schemaversionen gemeinsam genutzter Objektversionen. In die sem Zusammenhang konnten wir eine Reihe von Verbesserungsmöglichkeiten identifizieren, die den COASTPrototyp Systemen auf der Basis von Sichtenmechanismen gleichstellen würden. Übertragbarkeit der Ergebnisse Die Tragfähigkeit der Konzepte des COASTModells für die Unterstützung evolutionärer Sche maänderungen haben wir erfolgreich belegen können. Im folgenden sprechen wir noch einige Möglichkeiten an, die in dieser Abhandlung gewonnenen Erkenntnisse auch im Zusammenhang mit anderen Konzepten einzusetzen. - Abschnitt 2.2 hatte allgemeine Versionierungskonzepte vorgestellt, wie sie typischerweise auf Objekte angewendet werden, um deren inhaltliche Evolution abzubilden. Wir haben dieselben Konzepte in der vorliegenden Arbeit auf Schemata als Instanzen der Metaebene angewendet, um deren evolutionäre Entwicklung zu unterstützen. Dabei hat sich die Ver wendung versionierter Datenbankobjekte ebenfalls als sehr hilfreich erwiesen. Die Versio nen eines Objektes bei der Schemaversionierung repräsentieren ein Objekt in verschiedenen Datentypen. Von Situationen abgesehen, in denen das Modifikationsflag abgeschaltet ist und Änderungen daher gewollt nicht propagiert werden, repräsentieren die Versionen eines Objektes denselben logischen Objektwert. Damit unterscheiden sich die hier verwendeten Objektversionen von denen der klassischen Objektversionierung. Letztere stellen nämlich verschiedene logische Objektwerte dar, die allerdings alle demselben Datentyp entsprechen. Die vorangegangene, vergleichende Betrachtung zeigt einerseits, dass die beiden Formen der Versionierung unterschiedliche Ziele verfolgen, und andererseits legt sie die Vermutung nahe, dass es sich um orthogonale und damit gewinnbringend kombinierbare Ansätze han delt. Verschiedene Typen zur Darstellung desselben logischen Objektwertes hier stehen verschiedenen Objektwerten desselben Typs dort gegenüber. Tatsächlich lässt sich unser Ansatz um Mechanismen zur Objektversionierung erweitern, indem jede unserer Objektversionen nun durch verschiedene klassische Objektversionen ersetzt wird. Damit entsteht ein zweidimensionaler Raum von Objektversionen: entlang der einen Dimension liegt jeweils ein logischer Objektwert in verschiedenen Typen, entlang der anderen Dimension liegen jeweils verschiedene logische Zustände eines Objektes, die durch denselben Typ repräsentiert werden. Um die Kombination der beiden Versionierungskonzepte zu erreichen, sind allerdings noch einige Fragen näher zu untersuchen. Diese beschäftigen sich beispielsweise mit dem Zu sammenhang zwischen den Objektversionen entlang der beiden Dimensionen und mit der Propagation versionierter Objekte. Hier ist beispielsweise zu klären, ob alle, oder wenn nicht welche der logischen Objektwerte eines Objektes in andere Schemaversionen zu pro pagieren sind. Schließlich bietet die Realisierung des integrierten Gesamtkonzeptes zahl reiche Ansatzpunkte für technische Optimierungen und erfordert diese auch, um sowohl den Zeitaufwand für die Propagation als auch den Platzbedarf für die Speicherung der zweidimensional versionierten Objekte zu reduzieren. - Wir waren in der Literaturrecherche auf das Sichtenkonzept als Grundlage zur Simulati on von Schemaänderungen eingegangen und hatten dabei einige Deøzite bei der Lösung der hier betrachteten Aufgabenstellung identiøziert. Dies impliziert jedoch keine Aussa ge über die Tragfähigkeit von Sichten in dem Umfeld, für das sie ursprünglich konzipiert worden waren. Aufgrund der mit COAST erzielten Transparenz, die eine Schemaversion nach außen hin wie ein Schema eines unversionierten Systems erscheinen läßt, kann ein Sichtenkonzept auf dem COASTModell aufgesetzt werden. Konzeptionelle Schwierigkei ten sind durch die Kombination von Sichten und Schemaversionen nicht zu erwarten: Beim Ableiten neuer Schemaversionen können auf den Vorgängern definierte Sichten bei Bedarf mitintegriert werden und das Anlegen, Ändern und Löschen von Sichten kann durch die Primitive des Sichtenmechanismus erfolgen. In einem beide Konzepte integrierenden System kann entsprechend der gestellten Anforderungen entschieden werden, ob diese besser durch Anlegen einer neuen Sicht oder durch Ableiten einer neuen Schemaversion erfüllt werden. - Einen Schritt über die Integration eines separaten Sichtensystems hinaus geht die Über legung, ob Sichten nicht sogar durch Schemaversionen simuliert werden können. Damit wäre dann auch eine vollständig homogene Integration beider Konzepte in einem System erreicht. Um diese Überlegung zu verfolgen, betrachten wir die konzeptionellen Kompo nenten eines Sichtensystems und analysieren kurz, wie diese auf die Konzepte von COAST abgebildet werden können. Die für den Schemaentwickler zu verwendende Schnittstelle eines Sichtensystems ist durch die Sichtendefinitionssprache gegeben. Die dort zur Verfügung stehenden Konstrukte die nen zunächst der Definition des Sichtschemas und sind insoweit durch die Primitive der COASTODL abgedeckt. Darüber hinaus bestimmt eine Sichtendefinition die Extension der Sichtklassen durch Angabe je einer Anfrage, wobei das Ergebnis dieser Anfrage dem Schema der definierten Sichtklasse entsprechen muss bzw. dieses implizit erst bestimmt. Um diesen Teil eines Sichtenkonzeptes zu simulieren, sind in COAST zwei Erweiterungen not wendig. Zum einen wird eine Anfragesprache benötigt. Diese wäre für die Vervollständigung von COAST sowieso erforderlich und könnte sich konzeptionell sehr stark an bestehenden objektorientierten Anfragesprachen orientieren. Ein Anfragesystem muss zu jeder Anfrage zunächst das Schema ihres Resultates ermitteln und dieses könnte dann mit den Primiti ven der COASTODL erstellt werden. Daraufhin muss das Anfragesystem die eigentliche Durchführung der Anfrage auf der Datenbank erledigen. Dies beschreibt gleichzeitig die zweite in COAST erforderliche Erweiterung. Für die Durchführung der Anfrage und ins besondere der darin ggf. enthaltenen Selektion von Objekten müsste eine entsprechende Erweiterung der Propagationssprache von COAST vorgenommen werden. Änderungen von Objekten in Sichtklassen sind aufgrund des Sichtenänderungsproblems i.Allg. nicht durchführbar, da in der Sichtendefinitionssprache keine Möglichkeit besteht, die Auswirkungen einer solchen Änderung auf die Objekte des Basisschemas zu spezifi zieren. Daher bieten einige Konzepte Erweiterungen an, die man in COAST durch Ver wendung von Rückwärtskonvertierungsfunktionen bereits hat. Durch die Vorwärts und Rückwärtskonvertierungsfunktionen können beide Richtungen von Abbildungen zwischen (simuliertem) Basisschema und (simuliertem) Sichtschema sogar homogen durch dasselbe Konzept spezifiziert werden. Die Propagationsflags wären zur Simulation alle eingeschaltet und durch die Verwendung der verzögerten Propagationsmechanismen von COAST liefert die Simulation von Sich ten durch Schemaversionen zusätzlich ein optimiertes Konzept der Materialisierung von Sichten. - Das Konzept der direkten Schemaevolution hatte sich bei der Anwendung in dem hier beschriebenen Einsatzgebiet als zu restriktiv erwiesen. Nichtsdestotrotz kann die direkte Schemaevolution in Einzelfällen für die Durchführung von Schemaänderungen genügen, insbesondere solange noch keine Applikationen für eine Schemaversion implementiert sind. Folgerichtig können Situationen entstehen, wo selbst eingefrorene Schemaversionen noch in eingeschränktem Umfang änderbar wären, auch wenn dies i.Allg. nicht der Fall ist. Daher haben wir eine Kombination der direkten Schemaänderung mit dem Versionierungsansatz auf der Basis des Datenmodells von O 2 untersucht [FL96] (siehe Abschnitt 5.4.2). Dort konnten wir durch eine Klassiøkation der Schemaänderungsprimitive feststellen, ob den im Einzelfall gegebenen Umständen zufolge die Ableitung einer neuen Schemaversion erfor derlich ist oder nicht. Auf diesem Wege kann die Zahl entstehender Schemaversionen und damit auch der sich ergebende Verwaltungsaufwand reduziert werden. - Die in Datenbanksystemen benötigten Änderungsoperationen lassen sich drei elementaren Kategorien zuordnen:
The efficient management of large multimedia databases requires the development of new techniques to process, characterize, and search for multimedia objects. Especially in the case of image data, the rapidly growing amount of documents prohibits a manual description of the images’ content. Instead, the automated characterization is highly desirable to support annotation and retrieval of digital images. However, this is a very complex and still unsolved task. To contribute to a solution of this problem, we have developed a mechanism for recognizing objects in images based on the query by example paradigm. Therefore, the most salient image features of an example image representing the searched object are extracted to obtain a scale-invariant object model. The use of this model provides an efficient and robust strategy for recognizing objects in images independently of their size. Further applications of the mechanism are classical recognition tasks such as scene decomposition or object tracking in video sequences.
Assuming a cryptographically strong cyclic group G of prime order q and a random hash function H, we show that ElGamal encryption with an added Schnorr signature is secure against the adaptive chosen ciphertext attack, in which an attacker can freely use a decryption oracle except for the target ciphertext. We also prove security against the novel one-more-decyption attack. Our security proofs are in a new model, corresponding to a combination of two previously introduced models, the Random Oracle model and the Generic model. The security extends to the distributed threshold version of the scheme. Moreover, we propose a very practical scheme for private information retrieval that is based on blind decryption of ElGamal ciphertexts.
Zunächst wurde die Notwendigkeit von Schemaänderungen erläutert und verschiedene Ansätze aus der Literatur beschrieben, Schemaänderungen in laufenden Systeme so durchzuführen, dass eine möglichst einfache und automatisch stattfindende Konvertierung der betroffenen Datenobjekte erfolgen kann. Beim Vergleich erweist sich das Konzept der Schemaversionierung als die leistungsfähigste Lösung. Der Grundgedanke der Schemaversionierung ist, durch jede Schemaänderung eine neue Schemaversion zu erstellen, wobei die alte Schemaversion weiterhin benutzt werden kann. Die Datenobjekte liegen ebenfalls in mehreren Versionen vor und die Schemaänderung wird auf Objektebene nachempfunden, indem Datenänderungen propagiert, d.h. die Daten automatisch konvertiert werden. Für die Propagation werden die Beziehungen zwischen den Schemaversionen ausgenutzt. Mit dem Konzept der Schemaversionierung ist es möglich, mehrere Versionen eines Schemas parallel zu benutzen und nur die auf die Datenbank zugreifenden Applikationen anzupassen, die auch wirklich von der Schemaänderung betroffen sind. Diese Diplomarbeit ist Teil des COAST-Projekts, das die Schemaversionierung als Prototyp umsetzt. In COAST existierte vor dieser Diplomarbeit nur die Möglichkeit, einfache Schemaanderungen durchzuführen. Neu wurden komplexe Schemaanderungsoperationen eingeführt und das Konzept der Propagation entsprechend erweitert. Komplexe Schemaänderungen unterscheiden sich von einfachen Schemaänderungen dadurch, dass sie Attribute aus mehreren Quellklassen in einer Zielklasse (oder andersherum) vereinen können. Die bereits in kurz angeschnittenen Default-Konvertierungsfunktionen wurden genauer untersucht und konkret eingeführt. Es wurden mehrere typische Schemaänderungsoperationen vorgestellt und darauf untersucht, ob sie mit den bisherigen einfachen Schemaänderungsoperationen durchführbar waren oder ob dazu komplexe Schemaänderungsoperationen nötig sind. Außerdem wurde analysiert, ob das System für die entsprechenden Operationen automatisch sinnvolle Defaultkonvertierungsoperationen generieren kann oder ob ein Eingriff des Schemaentwicklers notwendig ist. Dazu wurden sie in eine von vier Kategorien eingeteilt, die aussagen, ob einfache oder komplexe Schemaänderungsoperationen nötig sind und ob sinnvolle Default-Konvertierungsfunktionen ohne Eingriff des Schemaentwicklers erzeugt werden können oder nicht. Zu jeder der aufgezahlten Schemaänderungsoperationen wurde die entsprechende vom System erzeugte Default-Konvertierungsfunktion aufgeführt und im Falle, dass sie der Schemaentwickler uberprüfen muss, angegeben, wo noch potenzieller Bedarf für manuelle Änderungen vorliegt. Die Auswirkungen der Einführung von komplexen Schemaänderungsoperationen auf die Propagation wurde im nächsten Kapitel analysiert und dabei festgestellt, dass das bisherige Konzept der Propagationskanten zwischen je zwei Objektversionen desselben Objekts nicht mehr ausreicht. Entsprechend wurde das neue Konzept von kombinierten Propagationskanten entwickelt, das Kanten zwischen mehr als nur zwei Objektversionen zulässt. Dazu wurden verschiedene Lösungsmöglichkeiten miteinander verglichen. Weiter wurden verschiedene Ansätze fur die Darstellung und Speicherung von Konvertierungsfunktionen vorgestellt und entschieden, die Konvertierungsfunktionen konkret in textueller Darstellung in den Propagationskanten zu speichern. Fur die Spezifizierung der gewünschten Konvertierungen bei der Propagation wurde eine Konvertierungssprache entwickelt und nach verschiedenen Gesichtspunkten konzipiert. Diese Gesichtspunkte umfassen sowohl den nötigen Funktionsumfang der Sprache wie auch entwurfstechnische Aspekte. Sämtliche Befehle der entwickelten Sprache wurden detailliert vorgestellt und abschließend die Sprache in BNF (Backus-Naur-Form) präsentiert. COAST ist inzwischen als Prototyp implementiert und wurde u.a. auf der CeBIT '99 vorgestellt (s. [Lau99b] und [LDHA99]). Nach einer Beschreibung der Funktionsweise und des Aufbaus von COAST und insbesondere des Propagationsmanagers wurden einige Implementierungsdetails vorgestellt und verschiedene Betrachtungen zur moglichen Optimierung beschrieben. Die Ziele der Diplomarbeit wurden damit erreicht: Die Schemaevolution kann mit den Vorzügen der Versionierung durchgeführt werden. Komplexe Schemaänderungen sind nun möglich und wurden ins Modell integriert. Die Propagation wurde entsprechend erweitert und eine Sprache zur Spezifikation der Propagation entwickelt.
We present efficient non-malleable commitment schemes based on standard assumptions such as RSA and Discrete-Log, and under the condition that the network provides publicly available RSA or Discrete-Log parameters generated by a trusted party. Our protocols require only three rounds and a few modular exponentiations. We also discuss the difference between the notion of non-malleable commitment schemes used by Dolev, Dwork and Naor [DDN00] and the one given by Di Crescenzo, Ishai and Ostrovsky [DIO98].
Erkennung kritischer Zustände von Patienten mit der Diagnose "Septischer Schock" mit einem RBF-Netz
(2000)
Es wurde gezeigt, dass der Arzt mit dem wachsenden RBF-Netz durch die Ausgabe von verlässlichen Warnungen unterstützt werden kann. Wie in der Clusteranalyse erläutert, leiden die Ergebnisse jedoch unter den wenigen Patienten und unter der ungenauen zeitlichen Erfassung der Daten. Da jeder Patient sehr individuelle Zustände annimmt, ist ein größeres Patientenkollektiv notwendig, um eine umfassende Wissensbasis zu lernen. Eine medizinische Nachbearbeitung der Wissensbasis durch die Analyse der Fälle ließe eine weitere Verbesserung des Ergebnisses erwarten. Somit könnten unbekannte Zusammenhänge durch das Lernen aus Beispielen und medizinisches Fachwissen kombiniert werden. Abstraktere Merkmale, die weniger abhängig von individuellen Zuständen sind, könnten eine Klassifikation noch weiter verbessern. Ein Ansatzpunkt ist z.B. die Abweichung der Messwerte vom gleitenden Mittelwert. Dieses Maß ist unempfindlicher gegenüber den individuellen Arbeitspunkten der Patienten und bildet auch die Basis von relativen Abhängigkeiten zwischen zwei Variablen, die in einem weiteren Schritt ebenfalls als Merkmal herangezogen wurden. Obwohl die Verwendung der relativen Abhängigkeiten zwischen zwei Variablen als Merkmal nicht deutlichere oder häufigere Warnungen hervorbringen konnte, weist doch die Clusteranalyse auf eine bessere Verteilung der Patienten hin. Einige Cluster sind besser für die Vorhersage geeignet, als dieses bei einer Clusterung auf Basis der Zustände erreicht werden kann. Unterstützt wird dieses Ergebnis auch durch den größeren Unterschied der Sicherheiten von falschen und richtigen Klassifikationen. Neben den bisher untersuchten Merkmalen scheinen auch die Variablen interessant zu sein, bei denen festgestellt wurde, dass sie sich trotz Medikamentengabe und adäquater Behandlung schwer stabilisieren lassen. Durch den behandelnden Arzt werden diese Werte üblicherweise in einem gewissen Bereich gehalten. Falls sich das Paar Medikament/physiologischer Parameter nicht mehr in einem sinnvollen Verhältnis befindet, kann dieses ein wichtiger Indikator sein. Nach dem Aufbau der grundlegenden Funktionalität der hier untersuchten Methoden ist die Suche nach geeigneten Merkmalen als Eingabe für ein neuronales Netz ein wesentlicher Bestandteil folgender Arbeiten. Abgesehen von dem generell anspruchsvollen Vorhaben aus Klinikdaten deutliche Hinweise für die Mortalität septischer-Schock-Patienten zu erhalten, liegen die wesentlichen Probleme in dem Umfang und der Messhäufigkeit der Frankfurter Vorstudie begründet, so dass eine Anwendung von Klassifikationsverfahren auf das umfassendere Patientenkollektiv der MEDAN Multicenter-Studie klarere Ergebnisse erwarten lässt. Eine weitere, für medizinische Anwendungen interessante, Analysemöglichkeit ist die Regelgenerierung, die zur Zeit in einem anderen Teilprojekt in der MEDAN-Arbeitsgruppe bearbeitet wird. Hier können im Fall metrischer Daten zusätzliche Hinweise für die Leistung eines reinen Klassifikationsverfahrens gewonnen werden mit dem Vorteil einer expliziten Regelausgabe. Zum anderen werden in diesem Teilprojekt auch Verfahren zur Regelgenerierung eingesetzt, die ordinale und nominale Variablen wie Diagnosen, Operationen, Therapien und Medikamentenangaben (binär, ohne genaue Dosis) auswerten können. Diese werden in den Multicenter-Daten vorhanden sein. Durch Kopplung der Regelgeneratoren für metrische Daten auf der einen Seite und für diskrete Variablen auf der anderen Seite, besteht durchaus die Hoffnung bessere Ergebnisse zu erzielen. Da der Regelgenerator für metrische Daten auf dem RBF-DDA (Abk. für: Dynamic Decay Adjustment)-Netz [BERTHOLD und DIAMOND, 1995] beruht, bietet es sich innerhalb des MEDAN-Projekts an, einen (bislang nicht durchgeführten) Vergleich mit dem hier verwendeten Netztyp durchzuführen. Der Vergleich ist allerdings nur von prinzipiellem Interesse und kann auf den hier betrachteten Daten kein grundsätzlich besseres Ergebnis liefern als die bislang durchgeführten Analysen; er kann aber zu einer umfangreichen Bewertung der Ergebnisse beitragen.
Context unification is a variant of second order unification. It can also be seen as a generalization of string unification to tree unification. Currently it is not known whether context unification is decidable. A specialization of context unification is stratified context unification, which is decidable. However, the previous algorithm has a very bad worst case complexity. Recently it turned out that stratified context unification is equivalent to satisfiability of one-step rewrite constraints. This paper contains an optimized algorithm for strati ed context unification exploiting sharing and power expressions. We prove that the complexity is determined mainly by the maximal depth of SO-cycles. Two observations are used: i. For every ambiguous SO-cycle, there is a context variable that can be instantiated with a ground context of main depth O(c*d), where c is the number of context variables and d is the depth of the SO-cycle. ii. the exponent of periodicity is O(2 pi ), which means it has an O(n)sized representation. From a practical point of view, these observations allow us to conclude that the unification algorithm is well-behaved, if the maximal depth of SO-cycles does not grow too large.
Ziel dieser Arbeit war es, ein System zu entwickeln, mit dem Sätze von Reduktionsdiagrammen auf ihre Vollständigkeit überprüft werden können. Das System sollte in der puren, funktionalen Programmiersprache Haskell realisiert werden und speziell auf einen nichtdeterministischen Kalkül mit Konstruktoren, einem case-Konstrukt und einem rekursiven let- Ausdruck (letrec) ausgerichtet sein. Dazu wurde in Kapitel 2 der lambda-Kalkül und funktionale Programmiersprachen eingeführt, um die Entwicklung der Kalküle lambda-nd und lambda-nd,rec zu motivieren. Die Basis-Kalküle lambda-nd und lamda-nd,rec wurden in Kapitel 3 bezüglich ihrer Sprachdefinition und Reduktionsregeln vorgestellt. Die Implementierung der beiden Kalküle und der Parser für die verwendete Kernsprache wurden ebenso angegeben wie die Mechanismen zur Markierung und Reduktion der Terme. Die Unterscheidung eines reduzierbaren Terms in NO- und internen Redex, sowie deren Erkennung wurde in diesem Kapitel besonders herausgestellt, da sie die Grundlage für die zu validierenden Reduktionsdiagramme darstellt. Damit ist der Grundstock für diese Arbeit gelegt worden. In Kapitel 4 haben wir kurz Methoden vorgestellt, die lamda-Kalkülen und deren Derivate eine Bedeutung zuzumessen versuchen, um Programme oder Terme miteinander vergleichen zu können. Also nicht nur ihre Termstruktur, sondern ihr Verhalten zu vergleichen. Dabei ist festgestellt worden, daß für nichtdeterministische Kalküle nur eine Methode verfügbar ist, und zwar die der kontextuellen Äquivalenz. Da wir gängige Programmtransformationen dahingehend überprüfen wollten, ob sie der kontextuellen Äquivalenz genügen, also nicht die Auswertung oder das Ergebnis derselben verändern, haben wir ein Kontext-Lemma vorgestellt. Mit Hilfe des Kontext-Lemmas ist es uns möglich gewesen, die Gültigkeit von Beweisen in Reduktionskontexten auf beliebige Kontexte auszudehnen. Für die eigentlichen Beweise werden Reduktionsdiagramme benötigt, die Reduktionsfolgen in verschiedener Weise umstellen. Wir haben die Reduktionsdiagramme ebenfalls in Kapitel 4 definiert. Die Reduktionsdiagramme müssen an jeder Stelle einer Reduktionsfolge anwendbar sein, da sonst die Äquivalenz-Beweise nicht möglich sind. D. h. es müßte bewiesen werden, daß mindestens ein Reduktionsdiagramm einer definierten Menge von Reduktionsdiagrammen für jeden Term und jede seiner Reduktionsfolgen anwendbar ist. Der naive Weg wäre, alle Terme und seine Reduktionsfolgen dahingehend zu überprüfen. Da dies jedoch nicht möglich ist, haben wir uns dazu entschlossen so viele Terme wie möglich zu untersuchen, nicht um die Vollständigkeit der Diagramme zu beweisen, sondern um zu zeigen, daß auf viele verschiedenartige Terme Reduktionsdiagramme erfolgreich angewendet werden können. Die Generierung der Terme haben wir in Kapitel 5 ausführlich dargestellt. In Kapitel 6 haben wir die Sprache zur Darstellung von Reduktionsdiagrammen und die Implementierung der Diagramm-Validierung beschrieben. Weiterhin haben wir ein Verfahren vorgestellt, mit dem wir fehlende Diagramme für Terme suchen und meist auch finden können. Das gesamte System haben wir so aufgebaut, daß eine große Menge an Termen generiert wird, für die Diagramme anwendbar sein müssen. Wenn keines der Diagramme auf einen Term anwendbar ist, also nicht validiert werden kann, dann wird ein passendes Diagramm gesucht. Mit Hilfe des entwickelten Systems Jonah sind in Kapitel 7 verschiedene Programmtransformationen dahingehend überprüft worden, ob die angegebenen Reduktionsdiagramme für große Mengen von Termen gültig sind. Dabei ist als Ergebnis herausgekommen, daß ein vollständiger Satz an Reduktionsdiagrammen für die (cp)-Reduktion nur sehr schwer zu finden ist. Selbst neu hinzugefügte Transformationen, die dabei helfen sollten, die Schwierigkeiten zu umgehen, konnten nicht verwendet werden, da es uns ebenfalls nicht möglich gewesen ist, für sie vollständige Diagrammsätze zu finden. Daraufhin haben wir den Basis-Kalkül zweimal erweitert, um die Schwierigkeiten der (cp)-Diagramme in den Griff zu bekommen. Aber auch diese Ansätze haben kein zufriedenstellendes Ergebnis geliefert. Als positives Ergebnis dieser Arbeit kann aber festgestellt werden, daß das System Jonah bei der Entwicklung nichtdeterministischer Kalküle auf Basis von lambda-Kalkülen eine sehr gute Hilfestellung sein kann, auch wenn es nicht zum vollständigen Beweis der Gültigkeit von Reduktionsdiagrammen dienen kann.
We present a theoretical analysis of structural FSM traversal, which is the basis for the sequential equivalence checking algorithm Record & Play presented earlier. We compare the convergence behaviour of exact and approximative structural FSM traversal with that of standard BDD-based FSM traversal. We show that for most circuits encountered in practice exact structural FSM traversal reaches the fixed point as fast as symbolic FSM traversal, while approximation can significantly reduce in the number of iterations needed. Our experiments confirm these results.
Diese Arbeit plädiert für eine rationale Behandlung von Patientendaten und untersucht dazu die Analyse der Daten mit Hilfe neuronale Netze etwas näher. Erfolgreiche Beispielanwendungen zeigen, daß die menschlichen Diagnosefähigkeiten deutlich schlechter sind als neuronale Diagnosesysteme. Für das Beispiel der neueren Architektur mit RBF-Netzen wird die Funktionalität näher erläutert und gezeigt, wie menschliche und neuronale Expertise miteinander gekoppelt werden kann. Der Ausblick deutet Anwendungen und Praxisproblematik derartiger Systeme an.
This paper describes the use of a Radial Basis Function (RBF) neural network in the approximation of process parameters for the extrusion of a rubber profile in tyre production. After introducing the rubber industry problem, the RBF network model and the RBF net learning algorithm are developed, which uses a growing number of RBF units to compensate the approximation error up to the desired error limit. Its performance is shown for simple analytic examples. Then the paper describes the modelling of the industrial problem. Simulations show good results, even when using only a few training samples. The paper is concluded by a discussion of possible systematic error influences, improvements and potential generalisation benefits. Keywords: Adaptive process control; Parameter estimation; RBF-nets; Rubber extrusion
The prevention of credit card fraud is an important application for prediction techniques. One major obstacle for using neural network training techniques is the high necessary diagnostic quality: Since only one financial transaction of a thousand is invalid no prediction success less than 99.9% is acceptable. Due to these credit card transaction proportions complete new concepts had to be developed and tested on real credit card data. This paper shows how advanced data mining techniques and neural network algorithm can be combined successfully to obtain a high fraud coverage combined with a low false alarm rate.
For the efficient management of large image databases, the automated characterization of images and the usage of that characterization for searching and ordering tasks is highly desirable. The purpose of the project SEMACODE is to combine the still unsolved problem of content-oriented characterization of images with scale-invariant object recognition and modelbased compression methods. To achieve this goal, existing techniques as well as new concepts related to pattern matching, image encoding, and image compression are examined. The resulting methods are integrated in a common framework with the aid of a content-oriented conception. For the application, an image database at the library of the university of Frankfurt/Main (StUB; about 60000 images), the required operations are developed. The search and query interfaces are defined in close cooperation with the StUB project “Digitized Colonial Picture Library”. This report describes the fundamentals and first results of the image encoding and object recognition algorithms developed within the scope of the project.