Verifying Integrity Constraints on Web Sites

1 Introduction

Data-intensive Web sites have created a new form of knowledge base. They typically contain and integrate several bodies of data about the enterprise they are de­ scribing, and these bodies of data are linked into a rich structure. For example, a company's internal Web site may contain data about its employees , linked to data about the products they produce and/or to the cus­ tomers they serve. The data in a Web site and the structure of the links in the site can be viewed as a richly structured knowledge base.

The management of data-intensive Web sites has re­ ceived significant attention in the database commu­ nity [Fernandez et al., 1998; Atzeni et al., 1998; Arocena and Mendelzon , 1998; Cluet et al., 1998; Paolini and Fraternali, 1998]. The key insight of recent systems is to specify the structure and content of sites declaratively. These systems separate and provide direct support for the three primary steps of site creation: (1) identify­ ing and accessing the data served at the site, (2) defin­ ing the site's structure (i.e. , the pages, the data in each page, and the links between pages), and (3) specifying

Alon Levy

Dan Suciu

Dept. of Computer Science

Seattle, WA. 98195 USA Florham Park, NJ 07932 USA

University of Washington alonOcs.washington.edu AT&T Research 180 Park Ave. suciuOresearch.att.com

the HTML rendering of the site's pages . Step 2 is usually supported by a declarative, specification language.

Web-site management systems based on declarative representations offer several benefits. First, since a site's structure and content are defined declaratively, not pro­ cedurally by a program, it is easy to create multiple versions of a site. For example, it is possible to build internal and external views of an organization's site or to build sites tailored to novice or expert users. Cur­ rently, creating multiple versions requires writing multi­ ple sets of programs or manually creating different sets of HTML files. Second, these systems support the evo­ lution of a site's structure. For example, to reorganize pages based on frequent usage patterns or to extend the site's content, we simply rewrite the site's specification. Another advantage is efficient update of a site when its data sources change.

Declarative Web-site management systems also allow us to view a site's definition and its content as a knowl­ edge base. A natural next step is to consider how reason­ ing techniques can further improve the process of build­ ing and maintaining Web sites. We consider the reason­ ing problem of verifying integrity constraints over Web sites . Specifically, when the structure of a site becomes complex, it is hard for a designer to ensure that the site will satisfy a set of desired properties. For example, we may want to enforce that all pages are reachable from the root , every organization homepage points to the home­ pages of its sub-organizations, or proprietary data is not displayed on the external version of the site. A study on the usability of on-line stores [Lohse and Spiller, 1998] provides other constraints that if followed, would im­ prove the site design.

For a verification tool to be useful, it must verify con­ straints against a site definition, not a particular in­ stance of the site, becau~e (1) we do not want to verify the constraints every time the site instance changes, and (2) if a Web site is dynamically generated, an instance is never completely materialized making it is impossible to check the constraints. Verifying the constraints on the site definition ensures that as long as the site is generated according to the definition, the constraints will be sat­ isfied. For this reason, the verification problem requires reasoning, and not just applying a procedure to the site. Furthermore, when the integrity constraints are not verified, the system should automatically propose a set of candidate modifications to the site definition. This raises a search problem in the space of possible modifications.

This paper makes the following contributions. First, we identify an important class of integrity constraints relevant to Web sites. Second, we describe a sound and complete algorithm for verifying the integrity constraints and an analysis of their complexity. The key feature of our algorithms is that they consider only the specifica­ tion of the site's structure and content, not a particular instance of a site. Hence, the· verification is independent of changes to the underlying site, as long as they are gen­ erated by the same specification. Finally, in cases where the verification algorithm shows that the constraints may be violated, it proposes a set of corrections to the Web site's definition.

The problem we consider is closely related to the prob­ lem of knowledge-base verification (see [VVT'98, 1998] for a recent workshop). We follow the paradigm pro­ posed in [Levy and Rousset , 1998], where algorithms for verification are based on query containment. However, whereas in [Levy and Rousset , 1998] there was a 1-1 translation between the verification problem and query containment, a challenge in our case is to perform the appropriate transformation.

We believe that Web-site management tools based on declarative specifications will pose several important AI research problems in the near future. Hence, one of the contributions of this paper is to bring the problem to the attention of our community. In the last section, we mention other research problems in this context .

2 Declarative Management of Web Sites

Declarative systems for Web-site management are based on the principle of separating three tasks: (1) the man­ agement of the data underlying the site, (2) the defini­ tion of the site's structure. and the content, and (3) the graphical presentation of the site. The first step requires identifying the sources that contain the site's data. We refer to this data as the raw data . These sources may include databases , structured files, or pre-existing sites. We assume that we interact with each of these sources via a wrapper program that produces the necessary data in tabular form. Here , we assume that the raw data is stored in a single relational database system. In the rest of the paper, we use an example that is a small fragment of a publication's Web site. Fig. 1 contains the schema of the raw data and sample data.

The second step in building a Web site requires spec­ ifying the site's structure. We describe a formalism for specifying this structure that captures features com­ mon to many declarative systems for Web-site man­ agement [Fernandez et al., 1998; Atzeni et al., 1998; Arocena and Mendelzon, 1998; Cluet et al. , 1998; Paolini and Fraternali , 1998]. We emphasize that the declara­ tive specification is concerned with the logical model of the site as a set of nodes and links, not its graphical presentation (i.e., how each node is translated to HTML). When using the systems above, the site designer also specifies the graphical presentation of each page, usually by a set of HTML templates, each of which applies to a group of related pages.

2.1 Specifying Web-site Structure

In order to specify a site's structure, we need to state (1) what pages exist (2) what data is available in each page, and (3) what links exist between pages. We specify the structure of site in a site definition. Given a site defi­ nition and a database instance, applying the definition to the database produces an instance of the site, called a site graph. Fig. 2 contains our example site definition and Fig. 3 contains the resulting site graph .

A site definition is a graph whose nodes are labeled by variables or by functional terms of the form f(X), where X is a (possibly empty) tuple of variables. Functional nodes in the site definition represent sets of pages in the site graph. In our· example, the node PersonPage(Y) rep­ resents the set of pages PersonPage(p) where pis a con­ stant in the database. Non-functional nodes are leaves and have one incoming edge. They represent the data contained in the page that points to them. For example, the node N represents the name of the person Y. Func­ tional nodes that have no arguments represent unique pages, such as the root.

Each functional node is labeled with a Horn rule that defines the conditions for the existence of instances of the node. A rule's head is an atom of the form Node(f(X)), where Node is a special predicate. For example, the rule for Year Page specifies that there will be a node for a year Z if some article was published in year Z. The rules for our example site are:

Node(Root()): -true. Node(Publications()): -true. Node(People()): -true. Node(YearPage(Z)): -Article(_,_, Z). Node(PersonPage(Y)): -Person(Y, _) . N ode(ArticlePage( X)) : -Article( X,-) ·

Edges in the site definition represent sets of links in the site graph. Each edge has an associated a Horn rule, which specifies the conditions for existence of a link be­ tween instances of source and destination nodes. The Horn rules use the special predicate Link. For example, the rule fourth below specifies that there is a link in the site graph between the page PersonPage(Y) and the page ArticlePage(X) if Y is an author of paper X. The third argument of the predicate Link is the link's label in the site graph. 1 We assume that in all of the rules this ar­ gument is always a constant. The rules for the links in our example are given below.

Link(Root(), Publications(), "publications") : -true. Link( Root(), People(), "people"): -true. Link( Publications(), Year Page(Z), "year") : -Article(_,_, Z). Link(People(), PersonPage(Y), "person") : -Person(Y, _). Link(PersonPage(Y), ArticlePage(X), "article"):- Author(Y, X), Article( X,_,_) . Link(YearPage(Z), ArticlePage(X), "article"):­ Article( X,_, Z). Link(ArticlePage(X), PersonPage(Y), "author") : - Author(Y, X), Person(Y, _).

Finally, the data contained in each page is also specified by Horn rules. For every leaf associated with a functional node, we associate a Horn rule defining the contents of the leaf. The first rule below specifies that the name of a person will be contained in the appropriate person page:

Link(PersonPage(Y), N, "name"): -Person(Y, N). Link(ArticlePage(X), T, "title") : -Article( X, T, _). Link(ArticlePage(X), PS, "ps") : -Article(X, _, -) , PsFile(X, PS).

1 This string denotes the name of the relationship between the nodes in the site graph, and not the anchor that will appear on the link in the actual site. Anchors are omitted for clarity.

Declarative specification of a Web site offers many ad­ vantages: rapid modification of the site's structure; cre­ ation of multiple versions of the site for different classes of users; and, as we explore next, the ability to reason globally about the site's structure. In principle, restruc­ turing a site or building another version requires mod­ ifying the set of rules that define the site, instead of modifying each page and its hard-wired links.

3 Specifying Integrity Constraints

Although declarative specification can simplify the task of creating complex sites, the specification of a richly structured site can be long. For example, the specifica­ tion of a customer-billing site using the Strudel specifi­ cation language [Fernandez et al., 1998] is 474lines. The specification is more concise than the equivalent imple­ mentation in a scripting language, but still too large to determine without automated reasoning whether global constraints on the site are satisfied. [Lohse and Spiller, 1998] describes Web sites for on-line stores . They argue that enforcing integrity constraints on such sites is crit­ ica:I to customer satisfaction and describe a set of such constraints. Our goal is to take advantage of a site's declarative definition and develop algorithms for verify­ ing that a given definition only produces sites that sat­ isfy the given set of constraints. For our example, some possible constraints include:

• ICl: All article pages are reachable from the root page.
• IC2: For every article, there is a link from its article page to its PostScript source.
• IC3: If two articles have a common author, there is a path between the corresponding article pages.
• IC4: If two articles have been published in the same year , there is a path between the corresponding article pages.

We may also want to specify constraints that limit the length of a path between two nodes, or that force every path to a node to go through some distinguished set of nodes. We define our language for specifying these kinds of integrity constraints and formally define the verifica­ tion problem.

Integrity constraints express properties we would like the Web site to have. Since the Web site is modeled as a graph, integrity constraints should be able to express the existence of certain paths between pages in the site. We express such paths using regular-path expressions. A regular-path expression over the set of constants C is formed by the following grammar (R, R1 and R2 denote regular-path expressions) :

In the grammar, a denotes a constant in C; not (a) matches any constant in C different from a. An _ de­ notes any constant inC; a period denotes concatenation, and I denotes alternation. R+, denotes 1 or more rep­ etitions of R . For example, a.b._.c+ denotes the set of paths beginning with ab, then an arbitrary element of C and then any number of occurrences of c. We use * as a shorthand for (_)+ , meaning an arbitrary path of length 1 or more .

Regular-path expressions are used in path atoms of the form X -+ R-+ Y, where R is a regular-path expression, and X and Y are terms. The atom X -+ R -+ Y is satisfied in a labeled directed graph G by each pair of nodes X, Y for which there is path from X to Y that satisfies the regular path expression R.

In principle, we can express integrity constraints us­ ing arbitrary formulas in first-order logic. However, our main goal here is to identify a more restricted language for which it is possible to develop sound and complete verification algorithms and which is expressive enough to model integrity constraints that are of practical inter­ est. We consider integrity constraints that have the form <P ::::} 7/J, where <P and 7/J are conjunctions of path atoms, atoms of the relations of the raw data, and atoms of the relation Node . Variables that appear in both <P and 7/J are assumed to be universally quantified, while the oth­ ers are existentially quantified. The following sentences express the integrity constraints in our example.

Given a particular site graph, it is straightforward to test whether an integrity constraint holds. However, our goal is to verify at the intentional level whether an in­ tegrity constraint is guaranteed to hold, i.e., given a site definition n, test whether the integrity constraint will hold for all Web sites that can be generated by 1?, for any possible database state. Formally, our problem is the following.

Definition 1: Let E1, ... , En be the relations in the schema of the raw data, n be a site definition. Let IC be an integrity constraint. We say that 1? satisfies IC if, for any given extension I of the relations E1 , ... , En, I C is satisfied in the site graph resulting from n and I .

In our example, ICl is satisfied, because every arti­ cle has a year of publication, and therefore is reachable through the YearPage . Similarly, IC3 is also. satisfied. IC2 is not satisfied, because some articles may not have PostScript sources. Although IC4 is satisfied by the site graph in Fig. 3, it is not necessarily satisfied for every site graph.

Next, we describe a sound and complete verification algorithm, and show how the complexity of the verifi­ cation problem changes with the form of the integrity constraints considered.

4 Verification Algorithm

The crucial step of our verification algorithm is to trans­ late the integrity constraint <P ::::} 7/J into a pair of Dat­ alog programs Qq, and Q.p . Datalog [Ullman, 1997] is a database query language where queries are specified by sets of Horn rules, and the meaning of the query is given by the least fixpoint model of the database and the rules. Our translation has the property that the in­ tegrity constraint is satisfied if and only if the datalog program Q q, is contained in the program Q.p . Informally, given two queries Q1 and Q2 the query Q1 contains the query Q2 if Q1 's result is a superset of Q2 's result for any database instance. Algorithms for query contain­ ment have been studied extensively in the database liter­ ature [Ullman, 1997]. These algorithms can be viewed as logical-entailment algorithms for specific classes of logi­ cal sentences, which is why they are useful in our context.

Our algorithm has two steps.

1. Given the integrity constraint, <P => 7/J, and the site definition, n, create a pair of Datalog queries Qq, and Q.p .
2. We use an extended query containment algorithm to test whether Q q, is contained in Q.p . If the contain­ ment holds, then the integrity constraint is guar­ anteed to hold. If not, the containment algorithm returns a set of candidate fixes.

We describe each step in more detail.

The algorithm in Fig. 4 translates either <P or 7/J into a Datalog program. This step relies heavily on the possi­ ble paths specified in the structure of the site definition in order to generate Q q, and Q.p. The subtle part of the translation concerns the path atoms . Given a path atom X -+ R -+ Y, the translation builds in a bottom­ up fashion a Datalog program that defines a relation corresponding to each of the subexpressions of R. The translation varies slightly depending on whether X and Y are variables, functional terms, and whether there is another conjunct of the form Node(X) (Node(Y)) . In the figure, we show only the case when X and Y are unary functional terms.

If our extended query-containment algorithm reports that Q q, is contained in Q.p, then then the integrity con­ straint is guaranteed to hold. Otherwise the containment algorithm returns a set of candidate fixes. The algorithm considers four kinds of fixes:

• Add conditions to <P in the integrity constraint,
• Remove conditions from the rules in the site defini­ tion n,
• Modify n by adding back arcs in the site definition, and
• Suggest a set of integrity constraints to enforce on the raw data, which guarantee that the constraints on the site will hold.

The fixes are reported to the site designer, who can then decide how to proceed. Due to space limitations, we only illustrate this phase of the algorithm through the example below. Intuitively, the fixes are generated by searching through the possible modifications to Q ¢> and Q.p such that for the modified queries, the containment

holds. Algorithm re-translate( T , n, X) Input: T is either the LHS or RHS of an IC. n is the site definition. X are the universally quantified variables in the IC. Output: a Datalog program defining the relation QT(X). Let T be of the form A,, .. . , Am. For 1 :::; i :::; m, let P A; be the set of Horn rules returned by atomToProg(A;, R), with query predicate qA,, return atomToProg(A,, R) U ... U atomToProg(Am, R) and the rule QT(X): -qA1 (X!), . . . , qAm (Xm) where if A; is of the form p(Y) then X; = Y if A; is of the form f(X)-+ R-+ g(Y), then X; = (X, Y). end re-translate. I I A( X) is an atom; n is a site definition. Algorithm atomToProg(A, R) if A is of the form p( X) then return the Datalog program: qA(X): -p(X). if A is of the form f(X) -+ R-+ g(Y) then return the Datalog program constructed as follows: for every rule r E R of the form Link(/!(X,), h(X2), "a"): -body where the rules for /! and h have bodies body,, body2 respectively, add the following rule: a(f,, X,, /2, X2) : -body, body,, body2 Define an IDB predicate for R by structural induction on R: if R is of the form "a", then Qa(/!,X,,h,X2): -a(/!,X,,h,X2). if R is of the form R,.R2 then QR1.R2(/!,X,,/2,X2):- QR1 (/!, x,, h. x3), QR 1 (h. x3, h. X2) if R is of the form R, I R2 then QRtiR2(/!, x,, h. X2): -QRl (/!, x,, h. X2)· QRtiR2(/! ,X,,h,X2): -QR2(/!,X,,h,X2)· if R is of the form R* then QR'(/!,X,,h,X2): -QR(/!,X,,h,X2)· QR'(/!,X,,h,X2):- QR(/1, X1, fs, X3), QR' (fs. X3, h, X2). the query predicate of the Datalog program is defined by: qA(X, Y): -QR(f,X,g, Y).

end atomToProg

Figure 4: Algorithm for translating the LHS or RHS of an integrity constraint into a Datalog program.

Consider the constraint ICl in our example, that re­ quires a path from the root page to any article page. The translation step produces the following two Datalog programs, whose query predicates are Qlh· and Qrh·. Since the RHS of the constraint involves a path atom with the regular expression *, the Datalog program of Qrh· defines a predicate Q.(X1,!I,X2,h) (the transi­ tive closure of Q _), which describes the possible paths in the site graph between nodes of the form fi(Xl) and h(X2). We also use the rules defining Q. in the other parts of the example.

Qlh·(X) : -Article( X,_,-)·

Qrhs(X): -Q.("Root", 0, "Article Page", X). Q.(X, Y, Z, W) : -Q.(X, Y, T, R), Q_(T, R, Z, W). Q.(X, Y, Z, W): -Q_(X, Y, Z, W). Q _("Root", 0, "Publications", 0) : -true. Q _("Root", 0, "People", 0) : -true Q_( "Publications", 0, "Year Page", X) : -Article(~,_, X). Q_("People", 0, "PersonPage", X): -Person( X,_). Q_("YearPage", X, "ArticlePage", Y) : -Article(Y, _,X). Q_("PersonPage", X, "ArticlePage", Y): -Person(X, _), Author(X, Y), Article(Y, _, _). Q_( "Article Page", X, "PersonPage", Y) : -Person(Y, -), Author(Y, X), Article(X, _, _) .

Since the containment check will show that Qlh· is con­ tained in Qrh·, the verification test succeeds. For IC2, the algorithm produces the following two programs, for which the containment fails.

Qlhs(X) : -Article( X,_,_). Qrhs(X) : -Qp,( "ArticlePage", X,_, Y). Qps("ArticlePage", X,_, Y): -Article( X,_,-), PsFile(X, Y).

However, in this case, the algorithm will propose a cor­ rection to the integrity constraint, namely adding the conjunct PsFile(X, Y) to the left hand side (meaning that the constraint needs to hold only on articles that have a PostScript source).

Finally, IC4 would result in the two programs:

Q,h , (X, Y) : -Article( X,_, Z), Article(Y, _, Z). Qrhs(X, Y) : -Q.( "Article Page", X, "ArticlePage", Y) .

In this case, the containment does not hold because paths between article pages in the site only go through the author pages, not through the year pages. Hence, the algorithm will suggest to add a link from ArticlePage to either Root() , the Publications(), or to the corresponding YearPage , and would propose the appropriate query to put on the new link.

5 Complexity of Verification

The algorithm described in the previous section provides a sound and complete verification algorithm in many im­ portant cases. This section characterizes these cases and establishes the complexity of the algorithm and of the verification problem. Note that in all of the results, the complexity is measured in the size of the site definition and not the size of the underlying raw data.

The following theorem considers the case in which there are no cycles in the nodes in the site definition.

Theorem 1: Let R be a site definition and IC be an integrity constraint of the form </> => t/J . Assume that there are no cycles between nodes in the site definition. Then, our verification algorithm is sound and complete and runs in non-deterministic polynomial time. The ver­ ification problem under these conditions is NP-complete.

The following theorem permits cyclic site definitions, but requires that the left-hand side of the integrity con­ straint does not contain path atoms with Kleene star.

This is a common case, because the left-hand side usu­ ally refers to conditions on the raw data, not on the site graph.

Theorem 2: Let R be a site definition and IC be an integrity constraint of the form <P :::? '!/;, where ¢ does not contain path atoms with Kleene star. Then, our ver­ ification algorithm is sound and complete and it runs in non-deterministic polynomial time. The verification problem under these conditions is NP-complete.

The proof of the theorems is based on the fact that the size of Q</> and Q.p is polynomial in the size of R, and the complexity of the corresponding containment algorithms. Note that in general, containment of arbi­ trary recursive Datalog is undecidable [Shmueli , 1993], but in the cases considered above Q</> is always non­ recursive. Note that if R contains the interpreted pred­ icates ~, <, #, then the complexity of the problems in the theorems is n~-complete.

6 Conclusions and Related Work

Web-site management systems based on declarative rep­ resentations offer many opportunities for applying AI re­ search to improve the Web-site construction and main­ tenance process. This paper considered the first such problem, namely the specification and verification of in­ tegrity constraints. We described a language for specify­ ing a wide class of constraints and a sound and complete algorithm for verification. In addition, our algorithm suggests fixes to the site definition when the integrity constraint does not hold.

Our work can be viewed as an extension of verifi­ cation methods for rule-based knowledge-base systems. Of that work, the most related· to ours is [Levy and Rousset, 1998] which first showed how to use query con­ tainment techniques for knowledge-base verification. In contrast to that work, where there was a direct map­ ping from the knowledge base to a query containment problem, an added challenge in our context is to develop the translation to containment. [Schmolze and Snyder, 1997] considers the verification problem where rules may have side-effects, but those to not appear in our context. [Rousset, 1997] proposes an extensional approach to ver­ ifying constraints on snapshots of Web sites (i.e., directly on the site graphs).

Finally, we mention two additional opportunities for new AI problems in this context. The first , a general­ ization of the work we described here, is to specify the structure of Web sites at an even higher level. Whereas in our work we only checked whether certain integrity constraints hold for a given site definition, there may be cases that we would want to specify only integrity con­ straints for the site. The system would then consider the constraints and would propose a definition of the struc­ ture for the Web site. The challenge is to choose among multiple structures that satisfy the given constraints.

The second problem concerns automatically restruc­ turing Web sites. The short experience in building Web sites has already shown that it is a highly iterative pro­ cess. Even after the Web site is up, designers will fre­ quently want to restructure it after understanding the patterns with which users browse the site. Perkowitz and Etzioni [Perkowitz and Etzioni, 1997] have proposed the notion of adaptive Web sites that restructure them­ selves automatically. We argue that declarative repre­ sentations of Web sites provide a basis on which to build adaptive Web site techniques. In particular , once we have a model of a Web site, we can analyze the user browsing patterns and propose meaningful ways to re­ structure the model , and hence the site itself.