Interfaces to Data, Beyond Views

Abstract

We discuss diferent ways in which we can define interfaces to data, going beyond standard view definitions. One is based on specifying a query, and asking for the views within a class that give the minimal information that sufice to support the query. Another is based on specifying which instances should be indistinguishable to users via the interface.

1. Introduction

How can we define an interface to a relational structure? In databases, a standard means is via views – declarative queries whose output is made available to users as another structure: in the case of relational database queries, a table. A huge amount of study has gone into the properties of views and view languages. See e.g. [ 1 ].

There are other mechanisms for interfacing with data that difer from views. At certain times in the past, defining more flexible notions of “datasource capabilities” – one aspect of how queries can interface with a data source – represented quite a hot topic in data management [ 2 ]. One kind of data interface that has received continued attention are access methods [ 3, 4, 5, 6, 7 ]. Access methods give a functional interface allowing a user to look up matching rows in a table, providing as input a subset of the attributes. They restrict access in a mannar orthogonal to views, but one can add to their expressiveness by combining them with integrity constraints [ 8 ] or with views [ 9 ]. Or one can limit the expressiveness further by adding number restrictions on access outputs [ 10 ]. Cautis et. al [ 11 ] give an intriguing formalism for defining “infinite sets of views”, an interface limitation that is incomparable to access restrictions.

Since this kind of research has diminished over the last few years, in this article we want to overview a couple projects that might stimulate new thinking about interfaces to data beyond views, and how one might measure the expressiveness of interfaces. This will be based on work published previously [ 12 ], and also connected to work that is about to appear [ 13 ].

2. Distributed schemas and classical views

We first review some standard definitions in relational databases [ 14 ]. A schema consists of a ifnite set of relation names, each with an associated arity (a non-negative number). An instance of a schema is an assignment of each relation name in the schema of arity to a collection (finite or infinite) of -tuples of elements. We will often use ℐ for a generic instance. The active domain of an instance ℐ, denoted adom(ℐ), is the set of elements occurring in some tuple of some ℐ().

An -ary query is a function from instances of a fixed schema to -tuples. We assume the usual semantics for active-domain first-order logic, given by a relation ℐ |= for a sentence. A Conjunctive Query (CQ) is a logical formula of the form ∃y. ⋀︀ where are atoms over the schema. A Union of CQs (UCQ) is a disjunction of CQs where the free variables of each disjunct are the same. UCQs can be extended to relational algebra, the standard algebraic presentation of first-order relational queries: queries are build up from symbols for each relation name by union, diference, selection, and product [ 14 ]. Relational algebra queries can be expressed in ifrst-order logic. Unlike arbitrary first-order logic formulas, whose truth value may depend on an additional “universe” for the range of quantification, relational algebra queries are domain independent: the output on an instance depends on the interpretation of each relation symbol. A view is just a pairing of an -ary query with an -ary relation that names its output. Based on the kind of query, we can talk about a CQ view, a relational algebra view, etc.

We now come to some definitions that are specific to distributed query processing or data integration. A distributed schema (d-schema) consists of a finite set of sources Srcs, with each source s associated with a local schema s.

A query over a d-schema is simply a query over the relations occurring in some local schema. A distributed view (d-view) assigns to each local schema a set of views over that schema. Thus a d-view describes an interface where each local source exports some information. Example 1. We have a d-schema consisting of two sources, a data source representing papers submitted to VLDB VLDB(paperid, title, authorid, authorname) and another source with relation SIGMOD with the same attributes, containing papers submitted to SIGMOD.

A trivial -view might export the entire content of each relation. Another -view might have the VLDB source export the projection on paperid, and the SIGMOD source export authorids. Note that a query giving the intersection of VLDB and SIGMOD is not a d-view, since a d-view consists of views that are local to a source. ▷

3. Minimal information interfaces

We are ready to look at our first non-standard means of defining an interface, from [ 12 ]. Rather than having the data designer explicitly provide views, the idea is that they only specify a query, and then ask for the minimal information views (within a certain class) that can support answering that query. This is particularly interesting in the distributed setting. We want to formalize the notion of a set of views being useful for answering a query, and having minimal information among those that are useful. We use Segoufin and Vianu’s notion of determinacy, later developed jointly with Nash [ 15 ].

Definition 1. Two d-instances and ′ are indistinguishable by a d-view (or just indistinguishable) if () = (′) for each view ∈ .

Since each view ∈ s is defined only using relation names occurring in s, we can equivalently say that 1 and 2 are -indistinguishable if (1s) = (2s) for each ∈ s for each source s.

Definition 2. A d-view determines a query at a d-instance if (′) = () for each ′ that is -indistinguishable from .

The d-view is useful for if determines on every d-instance (for short, just “ determines ”).

We are now ready to formalize the idea of a d-view that is useful for but reveals as little as possible: Definition 3 (Minimally informative useful views). Given a class of views and a query , we say that a d-view is a minimally informative useful d-view for within if is useful for and, for any other d-view ′ useful for based on views in , ′ determines the view definition of each view in .

Example 2. Returning to Ex. 1, consider a query asking if there is a title and author name common to SIGMOD and VLDB, a possible double-submission: ∃paperid title authorid authorname authorid′ paperid′

VLDB(paperid, title, authorid, authorname)∧

SIGMOD(paperid′, title, authorid′, authorname)

Obviously there are many useful -views for : we could export all information from each source, which be more than suficient to answer . But intuitively there is an obvious candidate for the minimally informative useful view. From the VLDB source we should export ∃ authorid authorname

VLDB(paperid, title, authorid, authorname) and similarly for SIGMOD. That is, to minimally support the query that joins across sources, we should project out everything but the variables that cross sources.

This is called the canonical d-view of with respect to the distributed schema. It will follow from the results mentioned in the next section that this really is the minimally-informative dview for this example. From minimally-informativeness, it follows that if the interface designers want to support this double-submission query with any d-view, they will need to reveal all the paper titles submitted to each conference. ▷

All of these definitions can be additionally parameterized by integrity constraints Σ . Given d-instance satisfying Σ and a d-view , determines a query over the d-schema at relative to Σ if: for every ′ satisfying Σ that is -indistinguishable from , (′) = (). We say that is useful for a query relative to Σ if it determines on every d-instance satisfying Σ . In the results in the next section we will assume that any integrity constraints are traditional database constraints, like Tuple-Generating Dependencies [ 14 ]. In the distributed schema setting, our positive results will usually assume that constraints are local: each constraint involves relations on a single source.

4. Results on interfaces via minimally informative views

We now present some results from [ 12 ] concerning when minimally informative views exist. Theorem 3. [Minimally informative d-views exist] [ 12 ] For any query , there are minimally informative d-views. The same holds in the presence of local constraints.

The minimally informative d-view is not given constructively, but rather is defined via a Myhill-Nerode style equivalence, which we will discuss further in Section 5. Of course if is an arbitrary query, we cannot say much about what the minimally informative views are. But in the case where is a CQ, we can get a very simple minimally informative view. Theorem 4. [Minimally informative relational algebra d-views exist for CQs] [ 12 ] For any conjunctive query , there are minimally informative d-views, computable from and expressible in relational algebra. The same holds in the presence of local constraints.

Notice here that we mentioned relational algebra, rather than CQ or UCQ. Surprisingly, we may need to use relational algebra features beyond UCQs: Theorem 5. [ 12 ] There are CQs where the minimally informative d-views are not CQs or even UCQs.

Thus in particular there are queries where the minimally informative d-view is not the canonical d-view.

Example 6. Suppose we have two sources one with ternary relation , the other with unary relation . Consider the conjunctive query :

∃1, 2, .(1, 2, ) ∧ (, 2, 1) ∧ (1) ∧ (2)

The canonical view at the source is {1, 2|∃.(1, 2, ) ∧ (, 2, 1)} and at the source it is {1, 2|(1) ∧ (2)}: these are the “obvious” views to support the query. But they are not the minimally informative views!

Consider the views formed by replacing the view on with the view exporting the pairs 1, 2 such that

(∃.(1, 2, ) ∧ (, 2, 1)) ∨ (∃.(2, 1, ) ∧ (, 1, 2)) We reveal to an external user that either the pair 1, 2 or its reverse satisfies a certain pattern. This is strictly less informative than the canonical views, which reveal which of the two cases holds. But the reader can check that it is suficient to answer the query . ▷

What about d-views that are minimally informative within the class of CQs? These always exist as well, and it turns out that after minimizing (removing redundant conjuncts), they are indeed the canonical ones: Theorem 7 (Minimally informative CQ views exist). [ 12 ] Let a CQ that has no redundant conjuncts. Then the canonical d-view of is minimally informative useful within the class of CQ views. The same holds in the presence of local constraints.

Finally, notice that in Theorem 3 we required any integrity constraints to be local. Arguably the simplest kind of non-local constraint is a replication constraint, saying that a relation 1 in source 1 is identical to a relation 2 in source 2.

Theorem 8. [ 12 ] There is a CQ and a single replication constraint where no minimally informative d-view exists.

[ 12 ] shows that a weaker notion of minimally informative view exists in the presence of replication constraints, based on the “amount of disclosure”.

5. Indistinguishability relations

We now look at another way to define interfaces to data, based very roughly on work in [ 13 ]. An indistinguishabiity relation is an equivalence relation on instances of a schema. Clearly any kind of classical view gives an indistinguishability relation: two instances are indistinguishable if the views produce the same output. But it is natural to allow a data designer to define an interface by simply declaring which pairs of databases should be indistinguishable, and then let the system develop a method of querying – e.g. through translation to appropriate views. Indistinguishability relations play a role in [ 12 ], where often views are constructed implicitly via indistinguishability. For example, in the proof of Theorem 3 from the previous section, what one actually shows is: Theorem 9. For any query over a d-schema, there are minimally informative d-views, with each view given implicitly by an indistinguishability relation.

This is what we referred to in the last section when we said that the minimally informative views are given by a Myhill-Nerode style equivalence relation. We sketch the argument, since it gives the idea of how to implicitly define a view via an indistinguishability relation. For a source s in a d-schema, an s-context is an instance for each source other than s. Given a source s and a query , we say two s-instances ℐ, ℐ′ are (s, )-equivalent if for any s-context , (ℐ, ) |= ⇔ (ℐ′, ) |= We say two d-instances and ′ are globally -equivalent if for each source , the restrictions of and ′ over source , are (s, )-equivalent.

Global -equivalence is clearly an indistinguishability relation. It is also not dificult to see that the corresponding d-view is a minimally informative useful d-view for within the class of all views:

Now let us return to indistinguishability relations in general. It is particularly interesting to look at indistinguishability relations defined by logical sentences. For a schema , let 2 denote the vocabulary with two copies of each relation in , denoted and ′. Thus an instance for 2 is a pair of instances for , one using the primed relations and one using the unprimed relations. We write such a pair as (ℐ1, ℐ2). Thus 2 is the natural vocabulary for describing relationships between structures.

Definition 4. Let be a domain independent first-order logic sentence over 2. We say that is a first-order logic indistinguishability relation if • defines a transitive relationship on pairs of instances: for any instances ℐ1, ℐ2, ℐ3 (ℐ1, ℐ2) |= , and (ℐ2, ℐ3) |= implies (ℐ1, ℐ3) |= • is commutative: (ℐ1, ℐ2) |= if and only if (ℐ2, ℐ1) |= .

• is reflexive: for all ℐ1, (ℐ1, ℐ1) |=

We can similarly relativize this to constraints Σ on : need only define an equivalence relation on structures satisfying Σ . We can look at indistinguishability relations over all instances for Σ , or deal with sentences that define an indistinguishability relation only on finite instances.

The results in [ 13 ] do not restrict to the finite case, and have several other deviations from the formalism as we present it here. But as we explain below, many of the results apply to the setting of finite instances.

5.1. Indistinguishability relations and relational/nested relational views

We mentioned that the obvious way to get an indistingushability relation is via views. And if we use relational algebra views, we get a first-order logic indistinguishability relation. Let Γ = { 1 . . . } be a finite set of relational algebra views, or equivalently, active domain formulas. We let Γ be the ℐ2 sentence ⋀︀ ∀x [ (x) ↔ ′(x)]. Here, for any domainindependent logical formula over . ′ is the formula formed by priming every relation. For any such Γ , Γ is a first-order logic indistinguishability relation. We call this a relational algebra view indistinguishability relation. We now describe a generalization of the notion of relational algebra view to nested relations. We refer here to the notion of nested set in database theory [ 16, 17, 18 ], and we can consider views given by the nested relational calculus. We will not need the exact definitions of nested relational calculus here. The observation is that agreement on nested relational views is expressible as a first-order logic sentence over 2: even though we are dealing with nested sets, we do not need “higher order logic” for the corresponding indistinguishability relation.

Example 10. Let schema consist of binary relation . Consider the 2 sentence: ∀ ∃′ ∀. [(, ) ↔ ′(′, )]∧

∀′ ∃ ∀. [(, ) ↔ ′(′, )]

This is a first-order logic indistinguishability relation. It states that every adjacency set of an element in one instance is the adjacency set of a (possibly diferent) element in the other set. Informally, the family of adjacency sets in the instances are the same.

If schema consists of a ternary relation (, , ), in any instance ℐ containing and , we can let ℐ (, ) be the ’s such that (, , ) holds in ℐ. We let ℐ () be the set of sets ℐ (, ) as ranges over nodes in ℐ, for a given in ℐ. And we let ℐ be the set of sets of sets ℐ () as ranges over nodes in ℐ. Then there is a first-order logic indistinguishability relation corresponding to preserving the nested set ℐ . ▷

In general, a -nested view indistinguishability relation is given by a -partitioned formula; this an active domain first-order formula in which the free variables are partitioned into sets. We write such formulas (x1; . . . ; x). In the binary relation example above, the partitioned formula is just (; ), while in the ternary example it is (; ; ). The definition of the nested set and the equivalence relation corresponding to (x1; . . . ; x) is given by induction on , generalizing the example.

What kinds of first-order logic indistinguishability relations are there beyond nested relational views? Over infinite models, it is easy to arrive at logic-based indistinguishability relations that are not nested views.

Example 11. Let our vocabulary have binary relations < and let Σ state that < is a dense linear order. Let be the sentence over 2 stating: ∃. <′ <′ ∧ (∀. <′ <′ → < < )]∧ ∃. < < ∧ (∀. < < → <′ <′ )]

[∀. < < → [∀. <′ <′ → says that every open interval (, ) in one dataset is the union of open intervals (, ) in the other dataset, and vice versa. Then is a logic-based indistinguishability relation. One can show that it is not a -nested view for any . ▷ Note that we made use of an infinite linear order here.

The following natural question is open: Question 1. Is there a set of first-order integrity constraints and a first-order indistinguishability relation that is not given by a -nested relation view over finite structures?

A negative answer would be a kind of semantics-to syntax or preservation theorem over ifnite structures, and only a few such results are known [ 19 ].

5.2. Some results

We present some of the results from [ 13 ] that could be interesting in the database context, warning the reader that the terminology and the formalism here does not match that in [ 13 ], which uses classical model theory as a framework.

It is not so dificult to show that the indistinguishability relations based on nested relational views form a strict hierarchy: Proposition 1. [ 13 ] For every there are ( + 1) nested view indistinguishability relations that are not given by nested view indistinguishability relations.

For separation, we could use generalizations of the adjacency-based equivalence relation in Example 10: the set of adjacency sets of a binary relation, the set of sets of adjacency sets of a ternary relation, etc.

In [ 13 ] this is argued explicitly for general only over infinite structures, but in the finite is illustrated in the case of 2 vs. 1. To prove the separation, one uses dense structures. In fact, one can show that this is necessary: Theorem 12. [ 13 ] If is a class of sparse finite structures (e.g. graphs excluding a minor) then every equivalence relation given by a -nested view indistinguishability relation is equivalent to one given by a relational algebra view indistinguishability relation.

Example 13. Let us to the adjacency-based indistinguishability relation, the first one in Example 10. Suppose the datasources are restricted to be finite trees, where is the child relation. We can see that the only way two trees can have the same adjacency sets is if they are identical! Thus, over trees, this equivalence relation is presented by a relational algebra view. ▷

If we consider the 2 sentence corresponding to a relational algebra view indistinguishability relation, we only need a block of universal quantifiers that cross the two instances: it is of the form ∀ [ (x) ↔ ′(x)], where concerns only the unprimed instance and ′ the primed instance. Call such indistinguishability relations Π 1. In contrast, if we look at nested view indistinguishability, we see at least three quantifier blocks ∀x ∃y ∀z (. . .). In the first example within Example 10, the pattern was ∀ ∃′ ∀. In the second example, which involved ternary relation and sets of sets of sets, there would be an additional alternation of universal and existential. The following result (which is shown looking at indistinguishability over both finite and infinite structures), shows that the jump from one block to at least three blocks is essential: Theorem 14. [ 13 ] Suppose an indistinguishability relation is given by a Π 2 sentence: of the form ∀1 . . . ∃1 . . .. Then it is given by a Π 1 indistinguishability relation.

Although the canonical example of Π 1 relations are those given by relational algebra views, it is shown that there is an indistinguishability relation that is Π 1 that is not given by relational algebra vievws. As with Question 1, we do not know if Π 1 corresponds to relational algebra when only finite structures are considered.

6. Conclusion

The goal in this short article is to point to some work related to the expressiveness of mechanisms for interfacing with datasources. It is striking that the notion of interface design and the notion of indistinguishability appear so frequently in areas of computer science – see, for example [ 20 ] for a short survey on the latter – but relatively infrequently in the discussion of data management interfaces.

The particular formalizations we summarize are meant to be just examples of a broader set of questions. What are the diferent ways of defining datasource interfaces, and how can we compare their expressiveness? How can we answer queries against non-traditional interfaces like indistinguishability relations? What kind of disclosure vs. privacy trade-ofs can we achieve with diferent kinds of interfaces?

References

[1] F. N. Afrati , R. Chirkova , Answering Queries Using Views, Second Edition , Morgan & Claypool Publishers, 2019 .

[2] M. Tork Roth , M. Arya , L. M. Haas , M. J. Carey , W. F. Cody , R. Fagin , P. M. Schwarz , J. T. II , E. L. Wimmers , The Garlic Project, in: SIGMOD, 1996 .

[3] C. Li , Computing complete answers to queries in the presence of limited access patterns , VLDB Journal 12 ( 2003 ) 211 - 227 .

[4] C. Li , E. Chang , Query planning with limited source capabilities , in: ICDE , 2000 .

[5] A. Nash , B. Ludäscher , Processing union of conjunctive queries with negation under limited access patterns , in: EDBT , 2004 .

[6] J. D. Ullman , Principles of Database and Knowledge-Base Systems , V2, Comp. Sci. Press, 1989 .

[7] A. Rajaraman , Y. Sagiv , J. D. Ullman , Answering queries using templates with binding patterns , in: PODS , 1995 .

[8] A. Deutsch , B. Ludäscher , A. Nash , Rewriting queries using views with access patterns under integrity constraints , Theor. Comput. Sci . 371 ( 2007 ) 200 - 226 .

[9] J. Romero , N. Preda , A. Amarilli , F. M. Suchanek , Equivalent rewritings on path views with binding patterns , in: ESWC , 2020 .

[10] A. Amarilli , M. Benedikt , When can we answer queries using result-bounded data interfaces? , Log. Methods Comput. Sci . 18 ( 2022 ).

[11] B. Cautis , A. Deutsch , N. Onose , Querying data sources that export infinite sets of views , Theory Comput. Syst . 49 ( 2011 ) 367 - 428 .

[12] M. Benedikt , P. Bourhis , L. Jachiet , E. Tsamoura, Balancing expressiveness and inexpressivenes in view design , TODS ( 2021 ).

[13] M. Benedikt , E. Hrushovski, Model equivalences, 2024 . Arxiv.org/pdf/2406.15235.

[14] S. Abiteboul , R. Hull , V. Vianu , Foundations of Databases, Addison-Wesley, 1995 .

[15] A. Nash , L. Segoufin , V. Vianu , Views and queries: Determinacy and rewriting , TODS 35 ( 2010 ).

[16] M. Gyssens , D. V. Gucht , The expressiveness of query languages for nested relations , IEEE Data Eng. Bull . 11 ( 1988 ) 48 - 55 .

[17] J. Paredaens , D. V. Gucht , Possibilities and limitations of using flat operators in nested algebra expressions , in: PODS , 1988 .

[18] P. Buneman , S. Naqvi , V. Tannen , L. Wong , Principles of Programming with Complex Objects and Collection Types , Theoretical Computer Science 149 ( 1995 ) 3 - 48 .

[19] B. Rossman , Homomorphism preservation theorems, J. ACM 55 ( 2008 ).

[20] H. Attiya , S. Rajsbaum , Indistinguishability, Commun. ACM 63 ( 2020 ) 90 - 99 .