This paper addresses issues involved in applying the event-condition-action (ECA) rule paradigm of active databases to policies-collections of general principles specifying the desired behavior of a system. We use a declarative policy description language, PDL, in which policies are formulated as sets of ECA rules. The main contribution of the paper is a framework for detecting action conflicts and finding resolutions for them. Conflicts are captured as violations of action constraints. The semantics of rules and conflict detection and resolution are defined axiomatically using logic programs. Given a policy and a set of action constraints, the framework defines a range of monitors that filter the output of the policy to satisfy the constraints.

We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an integer programming approach to solve this problem, it quickly becomes intractable even for modest-sized networks. Instead, our topology design uses random graphs that we show to be nearly optimal in cost, highly connected, and computationally efficient even for large networks. We then formulate a quadratic assignment problem (QAP) to map the abstract topology into the physical network to achieve optimal load balancing for given demand forecasts, which we solve using randomized heuristics. Numerical results on several example networks illustrate the performance and computational efficiency of our method. A graphical design tool has been developed based on our algorithms.

In many cases, data networks need to be monitored to ensure that they stay within acceptable parameters. The monitoring consists of measuring properties of the network, and of inferring an aggregate predicate from these measurements. In many cases it is too complex, or too expensive, to conduct explicit monitoring at all times. In these cases, information (integrity constraints) on the evolution of the network status can often allow us to use past measurements to infer the future behavior, thus reducing the monitoring cost. We provide a formal description of the problem of monitoring rapidly changing data, which we call the monitoring problem. We then classify this problem in terms of the integrity constraints that govern the evolution of the environment, and propose different algorithms for each of these classes. For the most restricted case, we can find a greedy algorithm which is optimal, while for the more general cases, we use competitive analysis and show that optimal worst and average case cost measuring algorithms exist. We then present heuristics for low-cost low-complexity measuring algorithms. We believe that the results of this paper can serve as a framework for further studies.

Many rapidly-changing environments need to be monitored to ensure that they stay within acceptable parameters. The monitoring consists of measuring properties of the environment, and of inferring an aggregate predicate from these measurements. In many cases it is too complex, or too expensive to conduct explicit monitoring at all times. In these cases, information (integrity constraints) on the evolution of this environment can often allow us to use past measurements to infer the future behavior, thus reducing the monitoring cost. We provide a formal description of the problem of monitoring rapidly-changing data, which we call the monitoring problem. We then classify this problem in terms of the integrity constraints that govern the evolution of the environment, and propose different algorithms for each of these classes. For the most restricted case, we can find a greedy algorithm which is optimal, while for the more general cases we use competitive analysis and show that optimal worst- and average-case cost measurement algorithms exist. We then present heuristics for low-cost low-complexity measurement algorithms. We believe that the results of this paper can serve as a framework for further studies.

We propose a novel protocol for aggregating micropayments in a networked environment. The protocol is based on the idea of debt consolidation and is fully decentralized. We propose client server and serverless versions of the protocol. We also analyze the mathematical properties of the protocol. Finally, we show how basic cryptographic techniques can be used to support the operation of the protocol in an untrusted environment.

This paper describes the idea of a wide area information system based entirely on audio information (Audioweb).We address two issues.First, we address the issue of adding hyperaudio links to audio documents non-intrusively (Le., without the need to modify the audio track).By doing so, audio documents can be linked together to form the AudioWeb.Secondly, we show how, based on the audio format discussed previously, a series of interfaces (browsers), that enable the user to navigate a web of audio documents, can be implemented.l'miissiw 10 Ill:llic digilrlflinrd copk ol'all or psrJ oJ*lhis m;~Jgal Jijr pclsollid or dnw~oni LIW is gmalccl \bilhool Ike providsd Jhrl 111~ copi* QW 1101 lllmk Or disJrihukd br pmlil or rwaimcrci;d nd\:l~lJ~g~.111~ c"I,yridil noliw.IIlk! lilk Ol'llle publiolion mid ils cleIe ;jpp:nr.:Ind flalicc is Mn 1~11 rop~riglil ishy pcnnisir~n 1~1'tlw ..\CII.111~.'lb Lumpy o[[lc:n+a.JO rCpllhlid1.It1 pOSl 011 WITUS or III redis~rihuJrr Ju liti.

Presents first-hand experiences from an actual re-engineering project. Business re-engineering is a process affecting not only the software system involved, but the underlying business model as well. Indeed, it is the changed business model along with the new technologies that determine the design of the new system. This paper is a walkthrough of the design of PICSDESK, a prototype incorporating some modern technologies to support the old business model of its predecessor and its evolution to a new business model. PICSDESK may be thought of as an example of a new breed of inventory control systems.

We present a new principle for the development of database query languages that the primitive operations should be organized around types. Viewing a relational database as consisting of sets of records, this principle dectates that we should investigate separately operations for records and sets. There are two immediate advantages of this approach, which is partly inspired by basic ideas from category theoryl. First, it provides a language for structures in which record and set types may be freely combined: nested relations or complex objects. Second, the fundamental operations for sets are closely related to those for other “collection types” such as bags or lists, and this suggests how database languages may be uniformly extended to these new types. the most general operation on sets, that of structural recursion, is one in which not all programs are well-defined. In looking for limited forms of this operation that always give rise to well-defined operations, we find a number of close connection with exiting database languages, notably those developed for complex objects. Moreover, even though the general paradigm of structural recursion is shown to be no more expressive than one of the existing languages for complex objects, it possesses certain properties of uniformity that make it a better candidate for an efficient, practical language. Thus rather than developing query languages by extending, for example, relational calculus, we advocate a very powerful paradigm in which a number of well-known languages are to be found as natural sublanguages.

Nondeterministic databases store disjunctive data using OR-objects. For example, data such as "Part#1 is implementable using Nickel or Cobalt" is stored as Implement(Part#1, o/sub 1/) where Dom(o/sub 1/)={Nickel, Cobalt} is the domain of the OR-object o/sub 1/. A possible world of a database is obtained by replacing every OR-object by a member from its domain, and it is said to be conforming if it satisfies all the FDs (functional dependencies) associated with the database. A database D is said to fully incorporate a set F of FDs if every possible world of D is conforming. This paper studies the problem of preprocessing databases to achieve full incorporation, and also the problem of incrementally maintaining a database fully incorporated under insertions and deletions. We first define a certain property called goodness of a class D of databases for a set F of FDs; goodness can be tested efficiently and enforced easily at schema design time. For any class D of databases that is good for F, we present: 1) a quadratic time algorithm for fully incorporating F; 2) efficient algorithms for maintaining full incorporation under updates; and 3) lower-bounds for the algorithms of (1) and (2). Next, we show that, for classes of databases that are not good, the problem of full incorporation is, in general, coNP-complete. We also examine the complexity when OR-objects are restricted to have no more than two members, and obtain some interesting tractable algorithms, and intractability results.

We are motivated by applications within design, planning in an object-oriented setting, and provide a complexity characterization for our queries.

The logic data language (LDL) system provides a declarative logic-based language and integrates relational database and logic programming technologies so as to support advanced data and knowledge-based applications. A comprehensive overview of the system and a description of LDL language and the compilation techniques employed to translate LDL queries into target query execution plans on the stored data are presented. The architecture and runtime environment of the system and the optimization techniques employed in order to improve the performance and assure the safety of the compiled queries are given. The experience gained so far with the system and application areas where the LDL approach appears to be particularly effective are discussed.>

In this paper we argue with a basic premise in logic programming research that the meaning of a program can be inferred from its syntax alone. We show that users may have a variety of intended models for programs and that a single program may give different intended models under different assumptions of semantics. Our conclusion is that it is impossible to infer the intended model from the syntax of the program and no single semantics will capture all the intended models. We propose as a solution an explicit specification of control. Towards this purpose we define a rule algebra. The user formulates a program as an algebraic specification that directs the execution towards the intended model. The interesting question at that point is how to efficiently implement such programs. We show a natural and easy transformation such that it takes as input an algebraic specification and produces as output a program belonging to a subclass of locally stratified programs. Moreover, there is a homomorphic correspondence between the algebraic expressions and their translations.

The need for control in logic programs is now being recognized. This is particularly evident when one focuses on allowing updates in logic programs. In this paper we propose a language DatalogA which is an extension of Datalog with updates to base relations. We define some procedural constructs to allow update programs to be written in an easy manner. The (W,p) scheme of Dynamic Logic fits nicely into the semantics of DatalogA programs in which W is taken to be the set of all possible states of the program and p is the accessibility relation between states. We give declarative semantics and equivalent constructed model semantics for DatalogA programs. We show that in the absence of updates our semantics reduce to the classical semantics of Datalog. Finally, we show some examples of non-stratified programs expressed in DatalogA.

In this paper we extend LDL, a Logic Based Database Language, to include finite sets and negation. The new language is called LDL1. We define the notion of a model and show that a negation-free program need not have a model, and that it may have more than one minimal model. We impose syntactic restriction in order to define a deterministic language. These restrictions allow only layered (stratified) programs. We prove that for any program satisfying the syntactic restrictions of layering, there is a minimal model, and that this model can be constructed in a bottom-up fashion. Extensions to the basic grouping mechanism are proposed. We show that these extensions can be translated into equivalent LDL1 programs. Finally, we show how the technique of magic sets can be extended to translate LDL1 programs into equivalent programs which can often be executed more efficiently

Motivation The "negation by failure" rule forms the basis of negation in logic programming Languages based on definite clauses such as Prolog.Apt and van Emden's theory of finite failure sets provides a theoretical basis for this "negation by failure" rule.This rule is known to be unsatisfactory in logical query languages for databases for several reasons.We propose a "negation by failure" rule for database applications and develop it analogously to Apt and Van Emden's theory.Our rule is applicable for databases containing first-order universally quantified clauses.When the database is Horn, our rule can be compiled into the database in a reasonably efficient manner; for first-order databases the implementation appears to be expensive.

A first-order database ~s defined as a function-free first-order theory in which the ground units serve as the extensional database and the proper noniogical axioms serve as the intensional database.The following problem is addressed: "Given a recurswe nonlogical axiom and the form of a potential query, can one describe a set of database retrieval requests that gives the correct answers and is guaranteed to terminate."The solution uses resolution-proof techmques over connection graphs to derive a program of relational database operations that gives all the answers to a query and has a welldefined termmatton condiUon.