The wide use of spreadsheet-based solutions for business processes illustrates the importance of giving business users simple mechanisms for specifying and managing their processes. However, spreadsheet-based solutions are hard to maintain, reuse, integrate, and scale. This paper describes an approach for supporting “DevOps for business users” that enables business-level users to manage the full lifecycle of a large class of cloud-hosted business processes. The approach builds on DevOps for software engineering, but removes software engineers from the loop. Unlike general-purpose “low code” business process management systems, the approach incorporates aspects of a processing domain (e.g., billing) to create a DevOps experience that business users can master easily. In the approach, business users follow an agile “specify-check-generate-deploy” methodology, enabling them to rapidly and iteratively generate and operationalize cloud-hosted processing systems, with little or no assistance from IT staff. We demonstrate and evaluate the approach using a system built for the billing application area, developed at IBM, which provides technology support and maintenance services for numerous clients, each with different billing needs and logic. The paper describes the system, requirements, empirical evaluation of key components, and lessons learned.

Adaptive Case Management (ACM) has emerged as a key BPM technology for supporting the unstructured business process. A key problem in ACM is that case schemas need to be changed to best fit the case at hand. Such changes are ad hoc, and may result in schemas that do not reflect the intended logic or properties. This article presents a formal approach for reasoning about which properties of a case schema are preserved after a modification, and describes change operations that are guaranteed to preserve certain properties. The approach supports reasoning about rollbacks. The Case Management model used here is a variant of the Guard-Stage-Milestone model for declarative business artifacts. A real-life example illustrates applicability.

We present a unique representation of data-centric workflows, designed to exploit the loosely coupled nature of publish/subscribe systems to enable their safe distribution and parallel execution. We argue for the practicality of our approach by mapping a standard and industry-strength data-centric workflow model, namely, IBM Business Artifacts with Guard-Stage-Milestone (GSM), into the publish/subscribe abstraction.

Automatic forecasting of time series data is a challenging problem in many industries. Current forecast models adopted by businesses do not provide adequate means for including data representing external factors that may have a significant impact on the time series, such as weather, national events, local events, social media trends, promotions, etc. This paper introduces a novel neural network attention mechanism that naturally incorporates data from multiple external sources without the feature engineering needed to get other techniques to work. We demonstrate empirically that the proposed model achieves superior performance for predicting the demand of 20 commodities across 107 stores of one of America’s largest retailers when compared to other baseline models, including neural networks, linear models, certain kernel methods, Bayesian regression, and decision trees. Our method ultimately accounts for a 23.9% relative improvement as a result of the incorporation of external data sources, and provides an unprecedented level of descriptive ability for a neural network forecasting model.

In this work, we develop an approach for the safe distribution and parallel execution of data-centric workflows over the publish/subscribe abstraction. In essence, we design a unique representation of data-centric workflows, specifically designed to exploit the loosely coupled and distributed nature of publish/subscribe systems. Furthermore, we argue for the practicality and expressiveness of our approach by mapping a standard and industry-strength data-centric workflow model, namely, IBM Business Artifacts with Guard-Stage-Milestone (GSM), into the publish/subscribe abstraction. In short, the contributions of this work are three-fold: (1) mapping of data-centric workflows into publish/subscribe to achieve distributed and parallel execution; (2) detailed theoretical analysis of the mapping; and (3) formulation of the complexity of the optimal workflow distribution over the publish/subscribe abstraction as an NP-hard problem.

Traditional approaches to Business Process Management (BPM) focus primarily on the process aspects, and treat the persistent data accessed and manipulated by the business processes as second class citizens. A recent approach to BPM, based on "business artifacts", is centered on a modeling framework that places data and process on an equal footing. The approach has been shown useful in various application domains, and one variant of business artifacts forms the basis of the emerging OMG Case Management Model and Notation (CMMN) standard. Research results have been developed around conceptual models, enterprise interoperation, business intelligence, and verification. This data-centric approach has the potential to provide the basis for a new generation of BPM technology in support of diverse application, and fueled by the insights into abstraction and data management that have been the hallmark of database research since the 70's.

Existing Web services standards consider data primarily on the level of inputs and outputs specifications, with the major focus on functional aspects of interactions. Majority of applications rely on data sources, but such data sources are not part of the Web service specifications and cannot be accessed directly by clients. The fact that data are treated independently or as second-class citizens severely limits re-use, flexibility, customization and integration options of current Web services. In this paper we suggest to extend the WS specifications by introducing a data-centric Web services model that integrates functional and data perspectives in one coherent framework. The approach is based on Business Artifacts and in particular on the declarative modular Guard-Stage-Milestone (GSM) model. We introduce a Web Data- and Artifact- centric Service (W-DAS) model using GSM in its core which in addition to usual application specific WS operations defines a set of data access interfaces including CRUD operations, artifacts retrieval interface for querying, filtering and sorting data, and operations for arbitrary custom defined ad hoc run-time queries. We discuss W-DAS publish-subscribe mechanisms and implementation.

No abstract available.

This short survey describes recent and on-going work in the area of "business artifacts", an approach to business process modeling centered around a holistic combination of data and process. This includes research aiming to enable support for service interoperation that is much more flexible than current SOA-based approaches.

In this paper we address the problem of modeling collaborative decision and knowledge intensive business processes (sometimes referred to as Decision Intensive Processes, or DIP processes). DIP processes assist users in performing decision intensive tasks, and provide users with a guidance relevant to process execution context. DIP processes are by nature collaborative, data-driven, need to support various kinds of flexibility at design and run time, and need to integrate with external services and information sources. Such a combination presents significant challenges for contemporary business processes technologies. We present a solution based on a business artifacts paradigm (a.k.a. business entities with lifecycles) using a Guard-Stage-Milestone (GSM) model for declarative lifecycles specification. We introduce a CoreControl - MicroProcess process design pattern, which allows a natural blending of a business functional process structure (usual for most business processes), with a decision & knowledge driven structure providing domain specific decision guidance to users. The proposed design pattern along with the declarative GSM BA approach provide suitable design primitives for DIP process, as demonstrated on a real problem from the supply chain solutions enablement domain.

Sender anonymity in location-based services (LBS) attempts to hide the identity of a mobile device user who sends requests to the LBS provider for services in her proximity (e.g. ¿find the nearest gas station¿ etc.). The goal is to keep the requester's interests private even from attackers who (via hacking or subpoenas) gain access to the request and to the locations of the mobile user and other nearby users at the time of the request. In an LBS context, the best-studied privacy guarantee is known as sender k-anonymity. We show that state-of-the art solutions for sender k-anonymity defend only against naive attackers who have no knowledge of the anonymization policy that is in use. We strengthen the privacy guarantee to defend against more realistic ¿policy-aware¿ attackers. We describe a polynomial algorithm to obtain an optimum anonymization policy. Our implementation and experiments show that the policy-aware sender k-anonymity has potential for practical impact, being efficiently enforceable, with limited reduction in utility when compared to policy-unaware guarantees.

We formalize and study business process systems that are centered around "business artifacts", or simply "artifacts". Artifacts are used to represent (real or conceptual) key business entities, including both their data schema and lifecycles. The lifecycle of an artifact type specifies the possible sequencings of services that can be applied to an artifact of this type as it progresses through the business process. The artifact-centric approach was introduced by IBM, and has been used to achieve substantial savings when performing business transformations.

Almost all medium- and large-scale businesses rely on electronic workflow systems to manage their business processes. A key challenge is to enable the easy re-use and modification of these workflow schemas and their piece-parts, so that they can be adapted to new business situations. This paper describes an approach for automatic construction (and thus, evolution) of a workflow schema that satisfies a specified condition (or "goal"), starting from a set of basic building block services (or "tasks"). We use a workflow model based on "business artifacts", which represent key (real or conceptual) business entities, and include both the business-relevant data about them and a specification of their lifecycle, that is, how they can evolve over time as they move through the workflow as the result of services being applied to them.

This paper describes a novel approach for gathering profile information about mobile phone users. The focus is on information that can be used to enhance targeting of advertisements. (The ads might be delivered into the mobile phones, or to other devices such as the user's IPTV.) Unlike previous approaches, we use a two-tiered approach for learning end-user habits and preferences. In this approach the first tier involves statistical learning from network observable data (in the current paper, primarily logs of cell towers visited), and the second tier involves explicit queries to the user (in the current paper, to ask, e.g., what kinds of activities the user does in a given region that he frequents). The user might be willing to answer occasional queries of this sort through offers of service discounts, or to be able to receive more relevant ads. The paper focuses on two key aspects of our approach, which correspond to how the two tiers are instantiated in the current version of the prototype system that we have developed at Bell Labs. The first concerns the statistical techniques used to determine information about regions visited, along with the frequency of visits, typical durations, and typical visit times. These techniques were developed based on a training set consisting of logs of 6 users with mobile devices over a period of several months. The techniques address issues that arise when a given small region is serviced by multiple cell towers (in which case oscillations between cell towers can be confused with movement between regions). The second key aspect concerns optimizing the order in which queries are presented to users, in a context where different query answers have different value for the advertising process. (The values of answers might be influenced by the mix of advertising campaigns from which ads are to be matched against users.) Optimization is NP-complete in a relatively general context. We develop a polynomial time algorithm which yields optimal sequences for the case where the family of queries to be asked satisfies a tree-based property. This is extended to create a heuristic polynomial time algorithm for the general case.

Provides an abstract of the keynote presentation and a brief professional biography of the presenter. The complete presentation was not made available for publication as part of the conference proceedings.

A key research challenge in Web services concerns (semi-) automatic discovery and composition of Web services, in order to construct new Web services with desired properties or capabilities. This talk provides a survey of key developments that work towards this ambitious goal. The fundamental work in this area has centered on three models, each coming with a different approach to the composition problem. The OWL-S model for Web services focuses on how Web services interact with the "real world," represented abstractly using (time-varying) first-order logic predicates and terms. A representative composition result here uses a translation into Petri nets. The "Roman" model for services focuses on an abstract notion of "activities" (without modeling how they impact the world), and in essence model Web services as finite state automata with transitions labeled by these activities. A powerful composition result is obtained using a reduction to propositional dynamic logic (PDL). The conversation model focuses on messages passed between Web services, and again uses finite state automata to model the internal processing of a service, with transitions labeled by message sends and message reads. A key result here concerns determination of the "local" behavior of individual services, if they are required to conform to a given "global" behavior. The talk also discusses two ongoing efforts to unify the three models just described. One activity, by the semantic Web services intiative (SWSI), is to develop a semantic Web services ontology (SWSO). This is based on the Process Specification Language (PSL), a first-order ontology for sharing descriptions of manufacturing processes, which recently became an ISO standard.

The web and converged services paradigm promises tremendous flexibility in the creation of rich composite services for enterprises and end users. The flexibility and richness offers the possibility of highly customized, individualized services for the end user and hence revenue generating services for service providers (e.g. ASPs, telecom network operators, ISPs). But how can end users (and enterprises) specify their preferences when a myriad of possibilities and potential circumstances need to be addressed? In this paper, we advocate a solution based on policy management where user preferences are specified through forms but translated into rules in a high-level policy language. This paper identifies the requirements for this kind of interpretation, and describes the Houdini system (developed at Bell Labs) which offers a rich rule-based language and a framework that supports intuitive, forms-based provisioning interfaces.

The web services paradigm holds the promise of tremendous flexibility in how services are combined to meet the needs of individual end-users. The “convergence” of networks (wireline telephony, wireless, data) further enhances the web services paradigm, by enabling the incorporation of real time contextual information (e.g., presence and location) along with opportunities for web services to impact the physical world more immediately (e.g., a vending machine delivering a soda based on a purchase via a cell phone). But it will not be possible for most end-users to enjoy the rich and intricate possibilities, unless a broad variety of personalization technologies are available and respect the end user’s legitimate need for privacy. This seminar begins with examples illustrating why personalization will be so important for the emerging web and converged services. The main body of the seminar focuses on 3 inter-related technologies. First is profile data management, the ability for services to share and access end-user profile data (including address, credit card, “simple” preferences, current location, current presence, ...) as appropriate for the services to be provided. Second is preference and policy management, the ability to store and execute on intricate, interrelated preferences that end-users may have (e.g., “during working hours, calls from strangers should be routed to voice-mail”; “I usually work from 9 to 6, but on Thursdays it is from 8 to 4”; ...). And third is personalized and privacy-conscious data sharing of profile data and preferences, the notion that an end-user should have complete control over what profile and preference data is shared with whom and under what circumstances and how it is interpreted. In addition to describing emerging approaches for providing these capabilities, the seminar will describe how to add value to applications by using personalization, from both the end-user and the application provider perspectives.

The e-services paradigm promises to enable rich, flexible, and dynamic inter-operation of highly distributed, heterogeneous network-enabled services. Among the challenges, a fundamental question concerns the design and analysis of composite e-services. This paper proposes techniques towards automated design of composite e-services. We consider the Roman model which represents e-services as activity-based finite state automata. For a given set of existing e-services and a desired e-service, does there exist a "mediator" which delegates activities in the desired e-service to existing e-services? The question was raised in an early study by Berardi et. al. for a restricted subclass of delegators which does not take into consideration of future activities. In this paper, we define a more general class of delegators called "lookahead" delegators and we show that the hierarchy based on the amount of lookahead is strict. We, then, study the complexity of constructing such delegators. We prove that in the case of deterministic e-services, a k-lookahead delegator can be computed in time polynomial in the size of target and subcontractor e-services, and exponential in k and the number of subcontractor e-services. We also present Wozart, an automated mediator construction tool implemented to realize our approaches.

This paper provides detail on two key components of the Houdini framework under development at Bell Labs, that enable context-aware and privacy-conscious user data sharing appropriate for mobile and/or ubiquitous computing. The framework includes an approach for integrating data from diverse sources, for gathering user preferences for what data to share and when to share it, and a policy management infrastructure in the network for enforcing those preferences. The current paper focuses on two components of this infrastructure that are essential for mobile and ubiquitous computing, namely the framework to support self-provisioning of preferences, and the performance of the underlying rules engine.

The web services paradigm promises to enable rich, exible, and dynamic interoperation of highly distributed and heterogeneous web-hosted services. Substantial progress has already been made towards this goal (e.g., emerging standards such as SOAP, WSDL,

The emerging paradigm of electronic services promises to bring to distributed computation and services the flexibility that the web has brought to the sharing of documents. An understanding of fundamental properties of e-service composition is required in order to take full advantage of the paradigm. This paper examines proposals and standards for e-services from the perspectives of XML, data management, workflow, and process models. Key areas for study are identified, including behavioral service signatures, verification and synthesis techniques for composite services, analysis of service data manipulation commands, and XML analysis applied to service specifications. We give a sample of the relevant results and techniques in each of these areas.

This paper introduces a framework for modeling and specifying the global behavior of e-service compositions. Under this framework, peers (individual e-services) communicate through asynchronous messages and each peer maintains a queue for incoming messages. A global "watcher" keeps track of messages as they occur. We propose and study a central notion of a "conversation", which is a sequence of (classes of) messages observed by the watcher. We consider the case where the peers are represented by Mealy machines (finite state machines with input and output). The sets of conversations exhibit unexpected behaviors. For example, there exists a composite e-service based on Mealy peers whose set of conversations is not context free (and not regular). (The set of conversations is always context sensitive.) One cause for this is the queuing of messages; we introduce an operator "prepone" that simulates queue delays from a global perspective and show that the set of conversations of each Mealy e-service is closed under prepone. We illustrate that the global prepone fails to completely capture the queue delay effects and refine prepone to a "local" version on conversations seen by individual peers. On the other hand, Mealy implementations of a composite e-service will always generate conversations whose "projections" are consistent with individual e-services. We use projection-join to reflect such situations. However, there are still Mealy peers whose set of conversations is not the local prepone and projection-join closure of any regular language. Therefore, we propose conversation specifications as a formalism to define the conversations allowed by an e-service composition. We give two technical results concerning the interplay between the local behaviors of Mealy peers and the global behaviors of their compositions. One result shows that for each regular language, its local prepone and projection-join closure corresponds to the set of conversations by some Mealy peers effectively constructed from . The second result gives a condition on the shape of a composition which guarantees that the set of conversations that can be realized is the local prepone and projection-join closure of a regular language.

Article Personalizing E-commerce applications with on-line heuristic decision making Share on Authors: Vinod Anupam Bell Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJ Bell Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJView Profile , Richard Hull Bell Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJ Bell Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJView Profile , Bharat Kumar Bell Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJ Bell Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJView Profile Authors Info & Claims WWW '01: Proceedings of the 10th international conference on World Wide WebMay 2001 Pages 296–307https://doi.org/10.1145/371920.372073Online:01 April 2001Publication History 5citation1,182DownloadsMetricsTotal Citations5Total Downloads1,182Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

For an enterprise to take advantage of the opportunities afforded by electronic commerce it must be able to make decisions about business transactions in near-real-time. In the coming era of segment-of-one marketing, these decisions will be quite intricate, so that customer treatments can be highly personalized, reflecting customer preferences, the customer's history with the enterprise, and targeted business objectives. This paper describes a paradigm called "decision flows" for specifying a form of incremental decision-making that can combine diverse business factors in near-real-time. This paper introduces and empirically analyzes a variety of optimization strategies for decision flows that are "data-intensive", i.e. that involve many database queries. A primary focus is on the use of parallelism and eagerness (a.k.a. speculative execution) to minimize work and/or reduce response time. A family of optimization techniques is developed, including algorithms and heuristics for scheduling tasks of the decision flow. Using a prototype execution engine the techniques are compared and analyzed in connection with decision-making applications having differing characteristics.

Previous work on long-running transactions for multi-database environments relaxes the isolation requirement of conventional ACID transactions. However, most of that work does not provide mechanisms to explicitly enforce isolation. This paper proposes a framework in which long-running transactions can specify global predicate-based locks to enforce limited forms of isolation between selected transactions. The framework appears to be especially useful in contexts where there is a class of transactions with stringent deadlines, and another class of transactions making multi-database updates that do not have stringent deadlines. This report motivates and presents the framework, and illustrates its use in connection with maintaining inter-database constraints.

Modern database management systems essentially solve the problem of accessing and managing large volumes of related data on a single platform, or on a cluster of tightly-coupled platforms.But many problems remain when two or more databases need to work together.A fundamental problem is raised by semantic heterogeneity -the fact that data duplicated across multiple databases is represented differently in the underlying database schemas.This tutorial describes fundamental problems raised by semantic heterogeneity and surveys theoretical frameworks that can provide solutions for them.The tutorial considers the following topics: (1) representative architectures for supporting database interoperation; (2) notions for comparing the "information capacity" of database schemas; (3) providing support for read-only integrated views of data, including the .virtualand materialized approaches; (4) providing support for read-write integrated views of data, including the issue of workflows on heterogeneous databases; and (5) research and tools for accessing and effectively using meta-data, e.g., to identify the relationships between schemas of different databases.' t '.'.

Previous approaches to supporting hypothetical queries have been “eager”: some representation of the hypothetical state (or the corresponding delta) is materialized, and query evaluation is filtered through that representation. This paper develops a framework for evaluating hypothetical queries using a “lazy” approach, or using a hybrid of eager and lazy approaches.

No abstract available.

Support for virtual states and deltas between them is useful for a variety of database applications, including hypothetical database access, version management, simulation, and active databases. The Heraclitus paradigm elevates delta values to be "first-class citizens" in database programming languages, so that they can be explicitly created, accessed and manipulated.A fundamental issue concerns the trade-off between the "accuracy" or "robustness" of a form of delta representation, and the ease of access and manipulation of that form. At one end of the spectrum, code-blocks could be used to represent delta values, resulting in a more accurate capture of the intended meaning of a proposed update, at the cost of more expensive access and manipulation. In the context of object-oriented databases, another point on the spectrum is "attribute-granularity" deltas which store the net changes to each modified attribute value of modified objects.This paper introduces a comprehensive framework for specifying a broad array of forms for representing deltas for complex value types (tuple, set, bag, list, o-set and dictionary). In general, the granularity of such deltas can be arbitrarily deep within the complex value structure. Applications of this framework in connection with hypothetical access to, and "merging" of, proposed updates are discussed.

This paper presents a framework for data integration currently under development in the Squirrel project. The framework is based on a special class of mediators, called Squirrel integration mediators. These mediators can support the traditional virtual and materialized approaches, and also hybrids of them.In the Squirrel mediators, a relation in the integrated view can be supported as (a) fully materialized, (b) fully virtual, or (c) partially materialized (i.e., with some attributes materialized and other attributes virtual). In general, (partially) materialized relations of the integrated view are maintained by incremental updates from the source databases. Squirrel mediators provide two approaches for doing this: (1) materialize all needed auxiliary data, so that data sources do not have to be queried when processing the incremental updates; or (2) leave some or all of the auxiliary data virtual, and query selected source databases when processing incremental updates.The paper presents formal notions of consistency and "freshness" for integrated views defined over multiple autonomous source databases. It is shown that Squirrel mediators satisfy these properties.

Traditional database systems provide a user with the ability to query and manipulate one database state, namely the current database state. However, in several emerging applications, the ability to analyze “what-if” scenarios in order to reason about the impact of an update (before committing that update) is of paramount importance. Example applications include hypothetical database access, active database management systems, and version management, to name a few. The central thesis of the Heraclitus paradigm is to provide flexible support for applications such as these by elevating deltas , which represent updates proposed against the current database state, to be first-class citizens. Heraclitus[Alg,C] is a database programming language that extends C to incorporate the relational algebra and deltas. Operators are provided that enable the programmer to explicitly construct, combine, and access deltas. Most interesting is the when operator, that supports hypothetical access to a delta: the expression E when σ yields the value that side effect free expression E would have if the value of delta expression σ were applied to the current database state. This article presents a broad overview of the philosophy underlying the Heraclitus paradigm, and describes the design and prototype implementation of Heraclitus[Alg, C]. A model-independent formalism for the Heraclitus paradigm is also presented. To illustrate the utility of Heraclitus, the article presents an in-depth discussion of how Heraclitus[Alg, C] can be used to specify, and thereby implement, a wide range of execution models for rule application in active databases; this includes both prominent execution models presented in the literature, and more recent “customized” execution models with novel features.

A novel execution model for rule application in active databases is developed and applied to the problem of updating derived data in a database represented using a semantic, object-based database model. The execution model is based on the use of “limited ambiguity rules” (LARs), which permit disjunction in rule actions. The execution model essentially performs a breadth-first exploration of alternative extensions of a user-requested update. Given an object-based database schema, both integrity constraints and specifications of derived classes and attributes are compiled into a family of limited ambiguity rules. A theoretical analysis shows that the approach is sound: the execution model returns all valid “completions” of a user-requested update, or terminates with an appropriate error notification. The complexity of the approach in connection with derived data update is considered.

Article Free Access Share on Safety and translation of calculus queries with scalar functions Authors: Martha Escobar-Molano View Profile , Richard Hull View Profile , Dean Jacobs View Profile Authors Info & Claims PODS '93: Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsAugust 1993Pages 253–264https://doi.org/10.1145/153850.153909Published:01 August 1993Publication History 19citation245DownloadsMetricsTotal Citations19Total Downloads245Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on On the equivalence of database restructurings involving object identifiers (extended abstract) Authors: Richard Hull Computer Science Department, University of Southern California, Los Angeles, CA Computer Science Department, University of Southern California, Los Angeles, CAView Profile , Masatoshi Yoshikawa Department of Information and Communication Sciences, Kyoto Sangyo University, Kamigamo, Kita-ku, Kyoto 603, Japan Department of Information and Communication Sciences, Kyoto Sangyo University, Kamigamo, Kita-ku, Kyoto 603, JapanView Profile Authors Info & Claims PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsApril 1991 Pages 328–340https://doi.org/10.1145/113413.113443Published:01 April 1991Publication History 17citation258DownloadsMetricsTotal Citations17Total Downloads258Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Conventional database query languages are considered in the context of untyped sets. The algebra without while has the expressive power of the typed complex object algebra. The algebra plus while, and COL with untyped sets (under stratified semantics or inflationary semantics) have the power of the computable queries. The calculus has power beyond the computable queries; and is characterized using the typed complex object calculus with invention. The Bancilhon-Khoshafian calculus is also discussed. A technical tool, called “generic Turing machine”, is introduced and used in several of the proofs.

A formal framework for studying the expressive power and complexity of OODB queries is developed. Three approaches to modeling sets are articulated and compared. The class of regular OODB schemas supports the explicit representation of set-valued types. Using an object-based semantics for sets, the regular schemas correspond to most implemented OODB systems in the literature; a value-based semantics for sets is also introduced. Without restrictions, both of these approaches support the specification of all computable queries. Assuming that the new operator is prohibited, the query language of the regular OODB schemas under the object-based semantics is complete in PSPACE; and under the value-based semantics it has hyper-exponential complexity. The third approach to modeling sets is given by the algebraic OODB model, in which multi-valued attributes rather than set-valued types are supported. method implementations can use operators stemming from the relational algebra, and do not have side-effects. The query language of algebraic OODBs is more powerful than the relational algebra but has complexity bounded by PTIME. The expressive power and complexity of data access for other variations of OODBs are also considered. Finally, a new relational query language, called algebra + pointwise recursion, is introduced. This is equivalent to the algebraic OODB language, and can compute generalized transitive closure.

The set-height of a complex object type is defined to be its level of nesting of the set construct. In a query of the complex object calculus which maps a database D to an output type T, an intermediate type is a type which is used by some variable of the query, but which is not present in D or T. For each k, i ≥ 0 we define CALCk,i to be the family of calculus queries mapping from and to types with set-height ≤ k and using intermediate types with set-height ≤ i In particular, CALC0,0 is the relational calculus, and CALC0,1 is equivalent to the family of second-order (relational) queries

A new, formally defined database model is introduced that combines fundamental principles of “semantic” database modeling in a coherent fashion. Using a graph-based formalism, the IFO model provides mechanisms for representing structured objects, and functional and ISA relationships between them. A number of fundamental results concerning semantic data modeling are obtained in the context of the IFO model. Notably, the types of object structure that can arise as a result of multiple uses of ISA relationships and object construction are described. Also, a natural, formal definition of update propagation is given, and it is shown that (under certain conditions) a correct update always exists.

The SNAP system provides interactive, graphics-based access to Schemas of the IFO database model, supporting the varied activities of schema design, schema browsing, and the specification of selection-type queries. The system uses a novel representation for Schemas and includes a variety of abstraction mechanisms which encourage users to design and view Schemas in a modular fashion. It also supports numerous capabilities for the simultaneous display of large amounts of information about the underlying schema, queries being specified, and answers to those queries. A prototype of the system which demonstrates the basic features of the user interface has been implemented.

Article Positivism vs minimalism in deductive databases Share on Authors: Nicole Bidoit View Profile , Richard Hull View Profile Authors Info & Claims PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systemsJune 1985 Pages 123–132https://doi.org/10.1145/6012.15409Online:01 June 1985Publication History 24citation589DownloadsMetricsTotal Citations24Total Downloads589Last 12 Months30Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The notion ofsort setis introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways to enhance the efficiency of an implemented database. A characterization of when order dependency implies the existence of sort sets in a database is presented, along with several corollaries concerning complexity, Armstrong relations, and cliques of certain graphs. Sort-set dependencies are then introduced. A (finite) sound and complete set of inference rules for sort-set dependencies is presented, as well as a proof that there is no such set for functional and sort-set dependencies taken together. Deciding logical implication for sort-set dependencies is proved to be polynomial, but if functional dependencies are included the problem is co-NP-complete. Each set of sort-set and functional dependencies is shown to have an Armstrong relation. A natural generalization of Armstrong relation, here calledseparator, is given and then used to study the relationship between order and sort-set dependencies.

Fundamental notions of relative information capacity between database structures are studied in the context of the relational model. Four progressively less restrictive formal definitions of “dominance” between pairs of relational database schemata are given. Each of these is shown to capture intuitively appealing, semantically meaningful properties which are natural for measures of relative information capacity between schemata. Relational schemata, both with and without key dependencies, are studied using these notions. A significant intuitive conclusion concerns the informal notion of relative information capacity often suggested in the conceptual database literature, which is based on accessibility of data via queries. Results here indicate that this notion is too general to accurately measure whether an underlying semantic connection exists between database schemata. Another important result of the paper shows that under any natural notion of information capacity equivalence, two relational schemata (with no dependencies) are equivalent if and only if they are identical (up to re-ordering of the attributes and relations). The approach and definitions used here can form part of the foundation for a rigorous investigation of a variety of important database problems involving data relativism, including those of schema integration and schema translation.

A new, formally defined database model is introduced which combines fundamental principles of "semantic" database modeling in a coherent fashion. The model provides mechanisms for representing structured objects and functional and ISA relationships between them. It is anticipated that the model can serve as the foundation for a theoretical investigation into a wide variety of fundamental issues concerning the logical representation of data in databases. Preliminary applications of the model include an efficient algorithm for computing the set of object types which can occur in a given entity set, even in the presence of a complex set of ISA relationships. The model can also be applied to precisely articulate "good" design policies.

Fundamental notions of relative information capacity between database structures are studied in the context of the relational model. Four progressively less restrictive formal definitions of "dominance" between pairs of relational database schemata are given. Each of these is shown to capture intuitively appealing, semantically meaningful properties which are natural for measures of relative information capacity between schemata. Relational schemata, both with and without key dependencies, are studied using these notions. A significant intuitive conclusion concerns the informal notion of relative information capacity often suggested in the conceptual database literature, which is based on accessability of data via queries. Results here indicate that this notion is too general to accurately measure whether an underlying semantic connection exists between database schemata. Another important result of the paper shows that under any natural notion of information capacity equivalence, two relational schemata (with no dependencies) are equivalent if and only if they are identical (up to re-ordering of the attributes and relations). The approach and definitions used here can form part of the foundation for a rigorous investigation of a variety of important database problems involving data relativism, including those of schema integration and schema translation.

article Free Access Share on Finitely Specifiable Implicational Dependency Families Author: Richard Hull University of Southern California, Los Angeles, California University of Southern California, Los Angeles, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 31Issue 2April 1984 pp 210–226https://doi.org/10.1145/62.2162Published:30 March 1984Publication History 26citation303DownloadsMetricsTotal Citations26Total Downloads303Last 12 Months4Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A mathematical theory for the study of data representation in databases is introduced and developed. The theory focuses on three data constructs (collection, composition and classification). "Formats" with semantically rich yet tractable structure are built recursively using these constructs. Using formats, we obtain several nontrivial results concerning notions of relative information capacity and restructuring of data sets. As such, the format model provides a new approach for the formal study of the construction of "user views" and other data manipulations in databases.

The notion of "sort set" is introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways to enhance the efficiency of an implemented database. A characterization of when order dependency implies the existence of sort sets in a database is presented, along with several corollaries concerning conplexlty, Armstrong relations and cliques of certain graphs.Sort-set dependencies are then introduced A (finite) sound and complete set of inference rules for sort-set deoendencies is presented, but there is no such set for functional and sort-set dependencies taken together. Deciding logical immplication for sort-set dependencies is proved to be polynomial, but if functional dependencies are included the problem is co-NP complete. Each set of sort-set and functional dependencies is shown to have an Armstrong relation A natural generalization of Armstrong relation, here called "separator," is given and then used to study the relationship between order and sort-set dependencies.

A new theory of data representation involving "formats", which are based on three recurrent and prominent data-structuring concepts, is introduced. In a mathematically rigorous way, a notion of "equivalent" information capacity is defined and shown to be natural in a wide range of contexts. A normal form is introduced, and each equivalence class of formats is shown to have a unique representative in normal form. Finally, a natural way of comparing the information capacity of (non-equivalent) formats is formalized and studied.

The recently introduced notion of order dependency in the relational model is generalized to include situations where order dependency is satisfied in an approximate way. Two fundamental types of approximate satisfaction are distinguished and analyzed. It is shown for both types that such approximate satisfaction of order dependencies can be applied to substantially reduce indexing space without significantly increasing access time.