Department of Information and Software Systems Engineering
School of Information Technology and Engineering
George Mason University
Fairfax, Virginia 22030-4444, U.S.A.
brodsky@isse.gmu.edu
Alexander Brodsky
Department of Information and Software Systems Engineering
School of Information Technology and Engineering
George Mason University
Fairfax, Virginia 22030-4444, U.S.A.
brodsky@isse.gmu.edu
This position paper describes the potential of the Constraint Database (CDB) technology for electronic trade with complex objectives. CDB is a young discipline at the intersection of databases, constraint programming, computational geometry and operations research. Constraints in CDB are a basic data type and can play many modeling roles including interconnection between trade parameters, manufacturing capabilities and processes, and complex trade objectives. We motivate the potential use of the CDB's for systems of electronic trade by examples and furthermore identify major research challenges and directions. We argue that the emerging CDB technology, if properly applied, would have a substantial impact on systems of electronic trade.
A typical scenario of electronic trade over Internet is this: (1) products and services are specified and priced by numerous suppliers (or distributors/providers - whatever terminology is suitable); and (2) bids for products and services imposed by numerous consumers. Moreover, often the same organization plays a role of a supplier and a consumer at the same time. An example of a simple objective in such trades is achieving a deal with specified minimal or maximal prices as sufficient conditions.
In realistic situations, however, suppliers and consumers may have trade objectives, which are considerably more complex. To illustrate, consider a chemicals manufacturer M, capable of producing a variety of products using different raw materials. M has limitations in resources: materials in stock, ability to raise money for purchasing raw material, manufacturing capabilities due to restricted number of machines and operators, and so on. Furthermore, M can use a variety of manufacturing processes each corresponding to a possibly different profit function. An example of a complex trade objective for M could be finding a set of electronic bids for products M is capable of producing and a set of electronic trades of raw materials that will satisfy the existing business constraints and maximize the profit function. Furthermore, an analyst working for M may ask a variety of what-if questions, which go much beyond optimize-a-function-subject-to constraints, typical in operations research: For each electronic bid of a product M can produce, what is the relationship (described by constraints) among the required raw materials? Is it possible to improve profits by 5% by making an electronic trade with a raw material supplier, and then using a better manufacturing process? How much of each raw material should be purchased in order to satisfy all electronic bid with profitability more than 15%? What are the ranges of and the connection among the quantities of all products that can be produced using raw materials available in electronic market place with the investment x? What is the best manufacturing process for a given set of electronic bids? Can an electronic bid be filled purely from inventory? and so on. Product bids, invoicing and ordering of raw materials can be performed through a flexible ``Internet database'', whereas the choice of materials supplier, the warehousing strategy, the manufacturing process to use, and the scheduling of machines and orders on the factory floor are mathematical programming programs. An electronic trade system, built upon a constraint database, will provide a single efficient platform to all these aspects, which are deeply integrated.
The basic idea in CDBs is the introduction of
constraint formulae as a basic data type in databases.
The notion of constraint data relies on a simple and fundamental
duality: a constraint (formula) 
in free variables 
is interpreted
as a set of tuples 
over the schema
that satisfy ; and, conversely, a finitely representable
object in 
space can be viewed as a constraint.
That is, the syntax is constraints, i.e. symbolic
expressions; the semantics are the corresponding, possibly infinite,
relations.
For example, a constraint (formula) 
with variables ranging over reals is interpreted as a set
and describes, say, a relationship between quantities
of n products required to be produced and
quantities 
of m resources available in the
electronic marketplace.
Each inequality
says
that the amount of the i-th resource needed to produce
units of n products respectively must not
exceed the amount 
of this resource available.
A sub-family of first order logic, i.e. logical connectors and quantifiers, and some atomic constraint domains, such as polynomial or linear constraints over reals, are used for (1) representation of constraint formulae (or objects as we will call them) and (2) their manipulation. Existing relational or object-oriented models can be extended with constraint objects; and their query languages with constraint calculus as a sub-language.
Such extended models can capture information needed for applications of electronic trade, including description of products, suppliers and customers as well as constraint description of manufacturing capacities, processes and so on. Furthermore, their query languages extended with constraint objects are natural for asking questions related to trade with complex objectives of the kind listed in the example. Moreover, these queries can be efficiently answered, taking advantage, on one hand, of constraint and mathematical programming techniques to restrict the search space, and, on the other, database indexing and optimization to facilitate constraint manipulation. The use of constraints is not incidental for they constitute an ideal media for complex modeling, and a data-type which is (1) uniform, (2) expressive, (3) compact, and (4) deeply optimizable for many specific domains.
No technology for declarative and efficient querying
of databases involving constraint objects exists today.
Applications of the kind discussed are typically implemented by
special purpose programs; while these programs may use
database and constraint programming tools, they typically
require considerable programming effort and are not flexible
to changes. In addition, they do not perform overall
optimization that interleaves
database, mathematical programming and
computational geometry manipulation techniques.
Existing DBMS do not manage constraints as stored data
.
Constraint Logic Programming on the other hand, was not designed
to deal with large amounts of persistent data.
One important challenge is the development of flexible
operations paradigm for electronic traders and analysts.
The data model ought to be flexible and to enable update
the database and the schema dynamically without involvement
of a ``centralized'' system administrator.
The querying paradigm should be suitable for a (possibly sophisticated)
analyst, which is capable of understanding and describing complex
trade objectives, but is not a programmer.
Not only ad-hock queries should be allowed, but rather filtering
queries that will be periodically applied with new information
available from the Internet.
A probably more challenging is the question of query evaluation, which include indexing and filtering, constraint algebra algorithms, and global optimization. The practical feasibility of electronic trade systems rely heavily of the ability to deeply optimize queries. The algorithms for constraint algebra are significantly different from those in relational algebra, although many ideas are still applicable. The traditional database optimization, both compile-time algebraic simplification and run-time cost-based approach are not adequate in constraint databases dealing with information over Internet. The main reason is that both constraint manipulation and access to data over Internet is computationally expensive; thus a fine balance should be found between the cost of each. Even cost estimation of evaluation plans may be infeasible without spending considerable amount of work on constraint manipulation. For filtering queries, dynamic views maintenance in presence of large constraint data sets presents a particular difficulty.
Implementation of a prototype electronic trade system and
performing a case study would be of great interest.
This can be done on top of the constraint object-oriented
database system, 
, that has been implemented by the group
of the author at George Mason University.